15.3. THE QR ALGORITHM 431
other 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 15.3.3 and theassumption that A is nondefective, there exists an invertible S,
Ak = Q(k)R(k) = SDkS−1 (15.12)
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 i jth entry is of the form
(DkLD−k
)i j=
λ
ki Li jλ
−kj if j < i
1 if i = j0 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 some subdiagonal termsof the form
λki Li jλ
−kj (15.13)
for which |λ i|=∣∣λ j∣∣ while Ek→ 0. (Note the entries of Lk are all bounded independent of
k but some may fail to converge.) Then
Q(k)R(k) = S (Lk +Ek)DkU
LetSLk = QkRk (15.14)
where this is the QR factorization of SLk. Then
Q(k)R(k) = (QkRk +SEk)DkU
= Qk(I +Q∗kSEkR−1
k
)RkDkU
= Qk (I +Fk)RkDkU
where Fk→ 0. Let I +Fk = Q′kR′k. Then Q(k)R(k) = QkQ′kR′kRkDkU. By Lemma 15.3.4
Q′k→ I and R′k→ I. (15.15)