376 CHAPTER 14. NUMERICAL METHODS, EIGENVALUES

that ΛU is an upper triangular matrix having positive diagonal entries. Note Λ2 = I andalso Λ commutes with a diagonal matrix. Thus

Q(k)R(k) = QQkRkRDkΛ2U = QQkRkRΛD

k (ΛU)

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

QQk

(ΛDk

) [(ΛDk

)−1RkRΛD

k](ΛU)

= Q (QkΛ)Dk[(ΛDk

)−1RkRΛD

k](ΛU)

= Q (QkΛ)

≡Gk︷ ︸︸ ︷Dk[(ΛDk

)−1RkRΛD

k](ΛU)

Now I claim the middle matrix in [·] is upper triangular and has all positive entries on thediagonal. 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

the matrix Gk ≡ Dk[(ΛDk

)−1RkRΛD

k](Λ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′

where Q′ is essentially equal to Q but might have some of the columns multiplied by −1.This is because Qk → I and so QkΛ → Λ. Now by Lemma 14.2.4, it follows

Q(k) → Q′, R(k)G−1k → I.

It remains to verify Ak converges to an upper triangular matrix. Recall that from 14.11and the definition below this (S = QR)

A = SDS−1 = (QR)D (QR)−1

= QRDR−1QT = QTQT

Where T is an upper triangular matrix. This is because it is the product of upper triangularmatrices R,D,R−1. Thus QTAQ = T. If you replace Q with Q′ in the above, it still resultsin an upper triangular matrix T ′ having the same diagonal entries as T. This is because

T = QTAQ = (Q′Λ)TA (Q′Λ) = ΛQ′TAQ′Λ

and considering the iith entry yields(QTAQ

)ii≡∑j,k

Λij

(Q′TAQ′)

jkΛki = ΛiiΛii

(Q′TAQ′)

ii=(Q′TAQ′)

ii

Recall from Lemma 14.2.3, Ak = Q(k)TAQ(k). Thus taking a limit and using the firstpart,

Ak = Q(k)TAQ(k) → Q′TAQ′ = T ′. ■

An easy case is for A symmetric. Recall Corollary 6.4.13. By this corollary, there existsan orthogonal (real unitary) matrix Q such that

QTAQ = D

where D is diagonal having the eigenvalues on the main diagonal decreasing in size from theupper left corner to the lower right.