next up previous contents index
Next: A -step maintains the Up: Theoretical results for -algorithms Previous: The -factorization of Hessenberg-like   Contents   Index


Unreduced Hessenberg-like matrices

Unreduced Hessenberg matrices are very important for the development of an implicit $ QR$-algorithm for Hessenberg matrices. It is essential for the application of an implicit $ QR$-algorithm that the corresponding Hessenberg matrix is unreduced, otherwise the algorithm would break down. Another feature of an unreduced Hessenberg matrix $ H$ is that it has an essentially unique $ QR$-factorization. Moreover also $ H-\kappa I$, with $ \kappa $ a shift has an essentially unique $ QR$-factorization. This is straightforward because of the zero structure below the subdiagonal. Only the last column can be dependent of the first $ n-1$ columns. Essentially unique means, only the sign of the columns of the orthogonal matrices $ Q$ can differ, and the signs of the elements in $ R$. Because the previous $ n-1$ columns are linearly independent, the first $ n-1$ columns of the matrix $ Q$ in the $ QR$-factorization of $ H=QR$, are linearly independent. $ Q$ is an orthogonal matrix, and the first $ n-1$ columns are essentially unique. As the dimension is $ n$ and we already have $ n-1$ orthogonal columns, the last column is uniquely defined, orthogonal to the first $ n-1$ columns. This means that the $ QR$-factorization is essentially unique. Summarizing, this means that the $ QR$-factorization of an unreduced Hessenberg matrix $ H$ has the following form:

% latex2html id marker 35768
$\displaystyle H = Q \left( \begin{array}{c\vert c} R & w \\  \hline 0 & \alpha \end{array} \right),$    

for which $ R$ is an upper triangular matrix of dimension $ (n-1)\times (n-1)$, $ w$ is a column vector of length $ (n-1)$, and $ \alpha$ is an element in $ \mathbb{R}$. We have that $ \alpha=0$ if and only if $ H$ is singular, this means that the last column of $ H$ depends on the previous $ n-1$.

Let us define now an unreduced Hessenberg-like matrix, in the following way:

Definition 59   An Hessenberg-like matrix $ Z$ is said to be unreduced if
  1. all the blocks $ Z(i+1:n,1:i)$ (for $ i=1,\ldots,n-1$) have rank equal to $ 1$; this corresponds to the fact that there are no zero blocks below the diagonal;
  2. all the blocks $ Z(i:n,1:i+1)$ (for $ i=1,\ldots,n-1$) have rank strictly higher than $ 1$, this means that on the superdiagonal, no elements are includable in the semiseparable structure.

Note 5   If an Hessenberg-like matrix $ Z$ is unreduced it is also nonsingular. This can be seen by calculating the $ QR$-factorization of $ Z$ as described in Section 7.1 of this chapter. Because none of the elements above the diagonal is includable in the semiseparable structure below the diagonal, all the diagonal elements of the upper triangular matrix $ R$ in the $ QR$-factorization of $ Z$ will be different from zero, implying the nonsingularity of the Hessenberg-like matrix $ Z$.

When these demands are placed on the Hessenberg-like matrix, and they can be checked rather easily, we have the following theorem connected to the $ QR$-factorization:

Theorem 60   Suppose $ Z$ to be an unreduced Hessenberg-like matrix. Then the matrix $ Z-\kappa I$, with $ \kappa $ as a shift has an essentially unique $ QR$-factorization.

Proof. If $ \kappa=0$ the theorem is true because $ Z$ is nonsingular. Suppose $ \kappa \neq 0$. Because the Hessenberg-like matrix $ Z$ is unreduced, the first $ n-1$ Givens transformations $ G_i$ of Section 7.1 of this chapter are nontrivial. Applying them to the left of the matrix $ Z-\kappa I$ results therefore in an unreducible Hessenberg matrix. As this Hessenberg matrix has the first $ n-1$ columns independent of each other also the matrix $ Z-\kappa I$ has the first $ n-1$ columns independent. Hence, the $ QR$-factorization of $ Z-\kappa I$ is essentially unique. $ \qedsymbol$

Note 6   An unreduced Hessenberg-like matrix $ Z$ is always nonsingular, and has therefore, always an essentially unique $ QR$-factorization. If one however admits that the block $ Z(n-1:n,1:n)$ is of rank $ 1$, the matrix $ Z$ also will have an essentially unique $ QR$-factorization.

Note 7   The unreduced Hessenberg-like matrix $ Z$ is always nonsingular, but the matrix $ Z-\kappa I$ can be singular.

This demand of unreducedness will play an important role in the proof of the implicit $ Q$-theorem for semiseparable matrices. Before we will formulate and prove this theorem we investigate another, also very interesting property of Hessenberg-like matrices. We will prove that the application of each step of the $ QR$-algorithm, where the orthogonal matrix $ Q$ is designed as in Section 7.1, will maintain the structure of the Hessenberg-like matrices.


next up previous contents index
Next: A -step maintains the Up: Theoretical results for -algorithms Previous: The -factorization of Hessenberg-like   Contents   Index
Raf Vandebril 2004-05-03