14.2. THE QR ALGORITHM 379

if A is just an n×n matrix having possibly complex eigenvalues but A is nondefective? Whathappens with the QR algorithm in this case? The short answer to this question is that theAk of the algorithm typically cannot converge. However, this does not mean the algo-rithm is not useful in finding eigenvalues. It turns out the sequence of matrices {Ak} havethe appearance of a block upper triangular matrix for large k in the sense that the entriesbelow the blocks on the main diagonal are small. Then looking at these blocks gives a wayto approximate the eigenvalues. An important example of the concept of a block triangularmatrix is the real Schur form for a matrix discussed in Theorem 6.4.7 but the concept asdescribed here allows for any size block centered on the diagonal.

First it is important to note a simple fact about unitary diagonal matrices. In whatfollows Λ will denote a unitary matrix which is also a diagonal matrix. These matricesare just the identity matrix with some of the ones replaced with a number of the form eiθ

for some θ. The important property of multiplication of any matrix by Λ on either sideis that it leaves all the zero entries the same and also preserves the absolute values of theother entries. Thus a block triangular matrix multiplied by Λ on either side is still blocktriangular. If the matrix is close to being block triangular this property of being close to ablock triangular matrix is also preserved by multiplying on either side by Λ. Other patternsdepending only on the size of the absolute value occurring in the matrix are also preservedby multiplying on either side by Λ. In other words, in looking for a pattern in a matrix,multiplication by Λ is irrelevant.

Now let A be an n×n matrix having real or complex entries. By Lemma 14.2.3 and theassumption that A is nondefective, there exists an invertible S,

Ak = Q(k)R(k) = SDkS−1 (14.14)

where

D =

λ1 0

. . .

0 λn

and by rearranging the columns of S, D can be made such that

|λ1| ≥ |λ2| ≥ · · · ≥ |λn| .

Assume S−1 has an LU factorization. Then

Ak = SDkLU = SDkLD−kDkU.

Consider the matrix in the middle, DkLD−k. The ijth entry is of the form

(DkLD−k

)ij=

λki Lijλ

−kj if j < i

1 if i = j

0 if j > i

and these all converge to 0 whenever |λi| < |λj | . Thus

DkLD−k = (Lk + Ek)

where Lk is a lower triangular matrix which has all ones down the diagonal and somesubdiagonal terms of the form

λki Lijλ−kj (14.15)