14.2. THE QR ALGORITHM 375

and letA = SDS−1 (14.10)

where

D =

λ1 0

. . .

0 λn

and suppose S−1 has an LU factorization. Then the matrices Ak in the QR algorithmdescribed above converge to an upper triangular matrix T ′ having the eigenvalues of A,λ1, · · · , λn descending on the main diagonal. The matrices Q(k) converge to Q′, an orthog-onal matrix which equals Q except for possibly having some columns multiplied by −1 for Qthe unitary part of the QR factorization of S,

S = QR,

andlimk→∞

Ak = T ′ = Q′TAQ′

Proof: From Lemma 14.2.3

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

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 (14.12)

and soQ(k)R(k) = QRDkLU = QRDkLD−kDkU

That matrix in the middle, DkLD−k satisfies(DkLD−k

)ij= λki Lijλ

−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)RD

kU

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 14.2.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. Unfortunately, it is notknown that the diagonal entries of this matrix are nonnegative because of the U . Let Λ bejust like the identity matrix but having some of the ones replaced with −1 in such a way