424 CHAPTER 15. NUMERICAL METHODS, EIGENVALUES

Lemma 15.3.3 Let A be an n×n matrix and let the Qk and Rk be as described in the algo-rithm. Then each Ak is unitarily similar to A and denoting by Q(k) the product Q1Q2 · · ·Qkand R(k) the product RkRk−1 · · ·R1, it follows that Ak = Q(k)R(k) (The matrix on the left is Araised to the kth power.)

A = Q(k)AkQ(k)∗, Ak = Q(k)∗AQ(k).

Proof: From the algorithm, Rk+1 = Ak+1Q∗k+1 and so

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

Now iterating this, it follows

Ak−1 = QkAkQ∗k = QkQk+1Ak+1Q∗k+1Q∗k

Ak−2 = Qk−1Ak−1Q∗k−1 = Qk−1QkQk+1Ak+1Q∗k+1Q∗kQ∗k−1

etc. Thus, after k−2 more iterations,

A = Q(k+1)Ak+1Q(k+1)∗

The product of unitary matrices is unitary and so this proves the first claim of the lemma.Now consider the part about Ak. From the algorithm, this is clearly true for k = 1.

(A1 = QR) Suppose then that

Ak = Q1Q2 · · ·QkRkRk−1 · · ·R1

What was just shown indicated

A = Q1Q2 · · ·Qk+1Ak+1Q∗k+1Q∗k · · ·Q∗1

and now from the algorithm, Ak+1 = Rk+1Qk+1 and so

A = Q1Q2 · · ·Qk+1Rk+1Qk+1Q∗k+1Q∗k · · ·Q∗1

ThenAk+1 = AAk =

A︷ ︸︸ ︷Q1Q2 · · ·Qk+1Rk+1Qk+1Q∗k+1Q∗k · · ·Q∗1Q1 · · ·QkRkRk−1 · · ·R1

= Q1Q2 · · ·Qk+1Rk+1RkRk−1 · · ·R1 ≡ Q(k+1)R(k+1) ■

Here is another very interesting lemma.

Lemma 15.3.4 Suppose Q(k),Q are unitary and Rk is upper triangular such that the diag-onal entries on Rk are all positive and

Q = limk→∞

Q(k)Rk

Thenlimk→∞

Q(k) = Q, limk→∞

Rk = I.

Also the QR factorization of A is unique.