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

**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