15.3. THE QR ALGORITHM 433

To see this, suppose condition 15.16 is violated and λ j, · · · ,λ j+p are complex eigen-values having nonzero imaginary parts such that each has the same absolute value butthey are all distinct. Then let µ > 0 and consider the matrix A + µI. Thus the corre-sponding eigenvalues of A+ µI are λ j + µ, · · · ,λ j+p + µ . A short computation shows∣∣λ j +µ

∣∣ , · · · , ∣∣λ j+p +µ∣∣ are all distinct and so the above situation of 15.16 is obtained. Of

course, if there are repeated eigenvalues, it may not be possible to reduce to the case aboveand you would end up with large blocks on the main diagonal which could be difficult todeal with.

So how do you identify the eigenvalues? You know Ak and behold that it is close toa block upper triangular matrix T ′B. You know Ak is also similar to A. Therefore, T ′B haseigenvalues which are close to the eigenvalues of Ak and hence those of A provided k issufficiently large. See Theorem 13.4.2 which depends on complex analysis or the exerciseon Page 347 which gives another way to see this. Thus you find the eigenvalues of thisblock triangular matrix T ′B and assert that these are good approximations of the eigenvaluesof Ak and hence to those of A. How do you find the eigenvalues of a block triangularmatrix? This is easy from Lemma 13.1.4. Say

T ′B =

B1 · · · ∗

. . ....

0 Bm

Then forming λ I−T ′B and taking the determinant, it follows from Lemma 13.1.4 this equals

m

∏j=1

det(λ I j−B j)

and so all you have to do is take the union of the eigenvalues for each B j. 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 λ .

Example 15.3.8 Here is a matrix. 3 2 1−2 0 −1−2 −2 0

It happens that the eigenvalues of this matrix are 1,1+ i,1− i. Lets apply the QR algorithmas if the eigenvalues were not known.