15.6. MATLAB AND THE QR ALGORITHM 363

eigenvalues of TB are the eigenvalues of the blocks Bi. Thus, the eigenvalues of A are thesame as those of Ak and these are close to the eigenvalues of TB.

In proving things about this algorithm and also for the sake of convenience, here is atechnical result.

Corollary 15.6.2 For Qk,Rk,Ak given in the QR algorithm,

A = Q1 · · ·QkAkQ∗k · · ·Q∗1 (15.3)

For Q(k) ≡ Q1 · · ·Qk and R(k) ≡ Rk · · ·R1, it follows that

Ak = Q(k)R(k)

Here Ak is the usual thing, A raised to the kth power.

Proof: From the algorithm,

A = A0 = Q1R1, Q∗1A0 = R1, A1 ≡ R1Q1 = Q∗1AQ1

HenceQ1A1Q∗1 = A

Suppose the formula 15.3 holds for k. Then from the algorithm,

Ak = Qk+1Rk+1, Rk+1 = Q∗k+1Ak, Ak+1 = Rk+1Qk+1 = Q∗k+1AkQk+1

Hence Qk+1Ak+1Q∗k+1 = Ak and so

A = Q1 · · ·QkAkQ∗k · · ·Q∗1 = Q1 · · ·QkQk+1Ak+1Q∗k+1Q∗k · · ·Q∗1

This shows the first part.The second part is clearly true from the algorithm if k = 1. Then from the first part and

the algorithm,

A = Q1 · · ·QkQk+1Ak+1Q∗k+1Q∗k · · ·Q∗1 = Q1 · · ·QkQk+1Rk+1

I︷ ︸︸ ︷Qk+1Q∗k+1Q∗k · · ·Q∗1

It follows that

Ak+1 = AAk = Q1 · · ·QkQk+1Rk+1Q∗k · · ·Q∗1Q(k)R(k)

= Q(k+1)Rk+1

(Q(k)

)∗Q(k)R(k)

HenceAk+1 = Q(k+1)Rk+1R(k) = Q(k+1)R(k+1) ■

Now suppose that A−1 exists. How do two QR factorizations compare? Since A−1

exists, it would require that if A=QR, then R−1 must exist. Now an upper triangular matrixhas inverse which is also upper triangular. This follows right away from the algorithmpresented early in the book for finding the inverse. If A = Q1R1 = Q2R2, then Q∗1Q2 =R1R−1

2 and so R1R−12 is an upper triangular matrix which is also unitary and in addition has

all positive entries down the diagonal. For simplicity, call it R. Thus R is upper triangular