14.2. THE QR ALGORITHM 373

Proof: LetQ = (q1, · · · ,qn) , Q

(k) =(qk1 , · · · ,qk

n

)where the q are the columns. Also denote by rkij the ijth entry of Rk. Thus

Q(k)Rk =(qk1 , · · · ,qk

n

)rk11 ∗

. . .

0 rknn

It follows

rk11qk1 → q1

and sork11 =

∣∣rk11qk1

∣∣→ 1

Therefore,qk1 → q1.

Next consider the second column.

rk12qk1 + rk22q

k2 → q2

Taking the inner product of both sides with qk1 it follows

limk→∞

rk12 = limk→∞

(q2 · qk

1

)= (q2 · q1) = 0.

Therefore,limk→∞

rk22qk2 = q2

and since rk22 > 0, it follows as in the first part that rk22 → 1. Hence

limk→∞

qk2 = q2.

Continuing this way, it followslimk→∞

rkij = 0

for all i ̸= j andlimk→∞

rkjj = 1, limk→∞

qkj = qj .

Thus Rk → I and Q(k) → Q. This proves the first part of the lemma.The second part follows immediately. If QR = Q′R′ = A where A−1 exists, then

Q∗Q′ = R (R′)−1

and I need to show both sides of the above are equal to I. The left side of the above isunitary and the right side is upper triangular having positive entries on the diagonal. Thisis because the inverse of such an upper triangular matrix having positive entries on themain diagonal is still upper triangular having positive entries on the main diagonal andthe product of two such upper triangular matrices gives another of the same form havingpositive entries on the main diagonal. Suppose then that Q = R where Q is unitary and Ris upper triangular having positive entries on the main diagonal. Let Qk = Q and Rk = R.It follows

IRk → R = Q