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 -algorithm for Hessenberg matrices. It is essential for the application of an implicit -algorithm that the corresponding Hessenberg matrix is unreduced, otherwise the algorithm would break down. Another feature of an unreduced Hessenberg matrix is that it has an essentially unique -factorization. Moreover also , with a shift has an essentially unique -factorization. This is straightforward because of the zero structure below the subdiagonal. Only the last column can be dependent of the first columns. Essentially unique means, only the sign of the columns of the orthogonal matrices can differ, and the signs of the elements in . Because the previous columns are linearly independent, the first columns of the matrix in the -factorization of , are linearly independent. is an orthogonal matrix, and the first columns are essentially unique. As the dimension is and we already have orthogonal columns, the last column is uniquely defined, orthogonal to the first columns. This means that the -factorization is essentially unique. Summarizing, this means that the -factorization of an unreduced Hessenberg matrix has the following form:

for which is an upper triangular matrix of dimension , is a column vector of length , and is an element in . We have that if and only if is singular, this means that the last column of depends on the previous .

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

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

Note 5   If an Hessenberg-like matrix is unreduced it is also nonsingular. This can be seen by calculating the -factorization of 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 in the -factorization of will be different from zero, implying the nonsingularity of the Hessenberg-like matrix .

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 -factorization:

Theorem 60   Suppose to be an unreduced Hessenberg-like matrix. Then the matrix , with as a shift has an essentially unique -factorization.

Proof. If the theorem is true because is nonsingular. Suppose . Because the Hessenberg-like matrix is unreduced, the first Givens transformations of Section 7.1 of this chapter are nontrivial. Applying them to the left of the matrix results therefore in an unreducible Hessenberg matrix. As this Hessenberg matrix has the first columns independent of each other also the matrix has the first columns independent. Hence, the -factorization of is essentially unique.

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

Note 7   The unreduced Hessenberg-like matrix is always nonsingular, but the matrix can be singular.

This demand of unreducedness will play an important role in the proof of the implicit -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 -algorithm, where the orthogonal matrix is designed as in Section 7.1, will maintain the structure of the Hessenberg-like matrices.

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