15.3. THE QR ALGORITHM 427

Let S = QR where this is just a QR factorization which is known to exist and let S−1 = LUwhich is assumed to exist. Thus

Q(k)R(k) = QRDkLU (15.10)

and so Q(k)R(k) = QRDkLU = QRDkLD−kDkU . That matrix in the middle, DkLD−k satis-fies (

DkLD−k)

i j= λ

ki Li jλ

−kj for j ≤ i, 0 if j > i.

Thus for j < i the expression converges to 0 because λ j > λ i when this happens. Wheni = j it reduces to 1. Thus the matrix in the middle is of the form I +Ek where Ek → 0.Then it follows

Ak = Q(k)R(k) = QR(I +Ek)DkU

= Q(I +REkR−1)RDkU ≡ Q(I +Fk)RDkU

where Fk → 0. Then let I +Fk = QkRk where this is another QR factorization. Then itreduces to

Q(k)R(k) = QQkRkRDkU

This looks really interesting because by Lemma 15.3.4 Qk → I and Rk → I becauseQkRk = (I +Fk)→ I. So it follows QQk is an orthogonal matrix converging to Q while

RkRDkU(

R(k))−1

is upper triangular, being the product of upper triangular matrices. Un-fortunately, it is not known that the diagonal entries of this matrix are nonnegative becauseof the U . Let Λ be just like the identity matrix but having some of the ones replaced with−1 in such a way that ΛU is an upper triangular matrix having positive diagonal entries.Note Λ2 = I and also Λ commutes with a diagonal matrix. Thus

Q(k)R(k) = QQkRkRDkΛ

2U = QQkRkRΛDk (ΛU)

At this point, one does some inspired massaging to write the above in the form

QQk

(ΛDk

)[(ΛDk

)−1RkRΛDk

](ΛU)

= Q(QkΛ)Dk[(

ΛDk)−1

RkRΛDk](ΛU)

= Q(QkΛ)

≡Gk︷ ︸︸ ︷Dk[(

ΛDk)−1

RkRΛDk](ΛU)

Now I claim the middle matrix in [·] is upper triangular and has all positive entries onthe diagonal. This is because it is an upper triangular matrix which is similar to the uppertriangular matrix RkR and so it has the same eigenvalues (diagonal entries) as RkR. Thus thematrix Gk ≡Dk

[(ΛDk

)−1 RkRΛDk](ΛU) is upper triangular and has all positive entries on

the diagonal. Multiply on the right by G−1k to get

Q(k)R(k)G−1k = QQkΛ→ Q′