Page 187 - Matrices theory and applications

10. Approximation of Eigenvalues
170
to compute the spectrum of each diagonal block. This principle applies
as well to a Hessenberg matrix. Hence one may always assume that M is
Hessenberg and that the m j+1,j ’s are nonzero. In that case, the eigenspaces
¯
have dimension one. In fact, if λ ∈ K,let L be the matrix extracted from
M − λI n by deletion of the first row and the last column. It is a triangular
¯
matrix of M n−1 (K), invertible because its diagonal entries, the m j+1,j ’s,
are nonzero. Hence, M −λI n is of rank at least equal to n−1, which implies
that the dimension of ker(M − λI n ) equals at most one.
Proposition 10.1.1 If M ∈ M n (K) is a Hessenberg matrix with m j+1,j =
0 for every j, in particular if this matrix is irreducible, then the eigenvalues
of M are geometrically simple.
The example

1 1
M =
−1 −1
shows that the eigenvalues of an irreducible Hessenberg matrix are not
necessarily algebraically simple.
From the point of view of matrix reduction by conjugation, one can at-
tribute two advantages to the Hessenberg class, compared with the class of
triangular matrices. First of all, if K = IR, many matrices are not trigonal-
izable in IR, though all are trigonalizable in CC. Of course, computing with
complex numbers is more expensive than computing with real numbers.
But we shall see that every square matrix with real entries is similar to a
Hessenberg matrix over the real numbers. Next, if K is algebraically closed,
the trigonalization of M needs the effective computation of the eigenvalues,
which is impossible in view of Abel’s theorem. However, the computation of
a similar Hessenberg matrix is obtained after a finite number of operations.
Let us observe, finally, that as the trigonalization (see Theorem 3.1.3),
the Hessenberg form is obtained through unitary transformations, a well-
conditionned process. When K = IR, these transformation are obviously
real orthogonal.

Theorem 10.1.1 For every matrix M ∈ M n (CC) there exists a unitary
transformation U such that U −1 MU is a Hessenberg matrix. If M ∈
M n (IR),one may take U ∈ O n .
2
3
Moreover, the matrix U is computable in 5n /3+ O(n ) multiplications
2
3
and 4n /3+ O(n ) additions.
Proof
Let X ∈ CC m be a unit vector: X X = 1. The matrix of the unitary
∗
(orthogonal) symmetry with respect to the hyperplane X ⊥ is S = I m −
⊥
∗
2XX .Infact, SX = X − 2X = −X, while Y ∈ X ;thatis X Y =0,
∗
implies SY = Y .