432 CHAPTER 15. NUMERICAL METHODS, EIGENVALUES

Now let Λk be a diagonal unitary matrix which has the property that Λ∗kDkU is an uppertriangular matrix which has all the diagonal entries positive. Then

Q(k)R(k) = QkQ′kΛk(Λ∗kR′kRkΛk

)Λ∗kDkU

That matrix in the middle has all positive diagonal entries because it is itself an uppertriangular matrix, being the product of such, and is similar to the matrix R′kRk which isupper triangular with positive diagonal entries. By Lemma 15.3.4 again, this time using theuniqueness assertion,

Q(k) = QkQ′kΛk, R(k) =(Λ∗kR′kRkΛk

)Λ∗kDkU

Note the term QkQ′kΛk must be real because the algorithm gives all Q(k) as real matrices.By 15.15 it follows that for k large enough Q(k) ≊ QkΛk where ≊ means the two matricesare close. Recall Ak = Q(k)T AQ(k) and so for large k,

Ak ≊ (QkΛk)∗A(QkΛk) = Λ

∗kQ∗kAQkΛk

As noted above, the form of Λ∗kQ∗kAQkΛk in terms of which entries are large and small isnot affected by the presence of Λk and Λ∗k . Thus, in considering what form this is in, itsuffices to consider Q∗kAQk.

This could get pretty complicated but I will consider the case where

if |λ i|= |λ i+1| , then |λ i+2|< |λ i+1| . (15.16)

This is typical of the situation where the eigenvalues are all distinct and the matrix A isreal so the eigenvalues occur as conjugate pairs. Then in this case, Lk above is lowertriangular with some nonzero terms on the diagonal right below the main diagonal butzeros everywhere else. Thus maybe (Lk)s+1,s ̸= 0 Recall 15.14 which implies

Qk = SLkR−1k (15.17)

where R−1k is upper triangular. Also recall from the definition of S in 15.12, it follows that

S−1AS = D. Thus the columns of S are eigenvectors of A, the ith being an eigenvector forλ i. Now from the form of Lk, it follows LkR−1

k is a block upper triangular matrix denotedby TB and so Qk = STB. It follows from the above construction in 15.13 and the givenassumption on the sizes of the eigenvalues, there are finitely many 2× 2 blocks centeredon the main diagonal along with possibly some diagonal entries. Therefore, for large k thematrix Ak = Q(k)T AQ(k) is approximately of the same form as that of

Q∗kAQk = T−1B S−1ASTB = T−1

B DTB

which is a block upper triangular matrix. As explained above, multiplication by the variousdiagonal unitary matrices does not affect this form. Therefore, for large k, Ak is approxi-mately a block upper triangular matrix.

How would this change if the above assumption on the size of the eigenvalues wererelaxed but the matrix was still nondefective with appropriate matrices having an LU fac-torization as above? It would mean the blocks on the diagonal would be larger. Thisimmediately makes the problem more cumbersome to deal with. However, in the case thatthe eigenvalues of A are distinct, the above situation really is typical of what occurs and inany case can be quickly reduced to this case.