14.2. THE QR ALGORITHM 381

assumption 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)TAQ(k) is approximately of the same form as that of

Q∗kAQk = T−1

B S−1ASTB = T−1B 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 were relaxedbut the matrix was still nondefective with appropriate matrices having an LU factorizationas above? It would mean the blocks on the diagonal would be larger. This immediatelymakes the problem more cumbersome to deal with. However, in the case that the eigenvaluesof A are distinct, the above situation really is typical of what occurs and in any case can bequickly reduced to this case.

To see this, suppose condition 14.18 is violated and λj , · · · , λj+p are complex eigenvalueshaving nonzero imaginary parts such that each has the same absolute value but they are alldistinct. Then let µ > 0 and consider the matrix A+µI. Thus the corresponding eigenvaluesof A+µI are λj +µ, · · · , λj+p+µ. A short computation shows |λj + µ| , · · · , |λj+p + µ| areall distinct and so the above situation of 14.18 is obtained. Of course, if there are repeatedeigenvalues, it may not be possible to reduce to the case above and you would end up withlarge blocks on the main diagonal which could be difficult to deal with.

So how do you identify the eigenvalues? You know Ak and behold that it is close to ablock upper triangular matrix T ′

B . You know Ak is also similar to A. Therefore, T ′B has

eigenvalues which are close to the eigenvalues of Ak and hence those of A provided k issufficiently large. See Theorem 6.9.2 which depends on complex analysis or the exercise onPage 184 which gives another way to see this. Thus you find the eigenvalues of this blocktriangular matrix T ′

B and assert that these are good approximations of the eigenvalues ofAk and hence to those of A. How do you find the eigenvalues of a block triangular matrix?This is easy from Lemma 6.4.6. Say

T ′B =

B1 · · · ∗

. . ....

0 Bm

Then forming λI −T ′

B and taking the determinant, it follows from Lemma 6.4.6 this equals

m∏j=1

det (λIj −Bj)

and so all you have to do is take the union of the eigenvalues for each Bj . In the caseemphasized here this is very easy because these blocks are just 2× 2 matrices.

How do you identify approximate eigenvectors from this? First try to find the approx-imate eigenvectors for Ak. Pick an approximate eigenvalue λ, an exact eigenvalue for T ′

B .Then find v solving T ′

Bv = λv. It follows since T ′B is close to Ak that Akv ≊ λv and so

Q(k)AQ(k)Tv = Akv ≊ λv

HenceAQ(k)Tv ≊ λQ(k)Tv

and so Q(k)Tv is an approximation to the eigenvector which goes with the eigenvalue of Awhich is close to λ.