15.3. THE QR ALGORITHM 423

15.3 The QR Algorithm15.3.1 Basic Properties And DefinitionRecall the theorem about the QR factorization in Theorem 12.3.9. It says that given an n×nreal matrix A, there exists a real orthogonal matrix Q and an upper triangular matrix R suchthat A = QR and that this factorization can be accomplished by a systematic procedure.One such procedure was given in proving this theorem.

Theorem 15.3.1 Let A be an n× n complex matrix. Then there exists a unitary Q andupper triangular R such that A = QR.

Proof: This is obvious if n = 1. Suppose true for n and let

A =(

a1 · · · an an+1

)Let Q1 be a unitary matrix such that Q1a1 = |a1|e1 in case a1 ̸= 0. If a1 = 0, let Q1 = I.Thus

Q1A =

(a b

0 A1

)where A1 is (n−1)× (n−1). By induction, there exists Q′2 an (n−1)× (n−1) unitarymatrix such that Q′2A1 = R′, an upper triangular matrix. Then(

1 0

0 Q′2

)Q1A =

(a b

0 R′

)= R

Since the product of unitary matrices is unitary, there exists Q unitary such that Q∗A = Rand so A = QR. ■ ▶ ▶

The QR algorithm is described in the following definition.

Definition 15.3.2 The QR algorithm is the following. In the description of this algorithm,Q is unitary and R is upper triangular having nonnegative entries on the main diagonal.Starting with A an n×n matrix, form

A0 ≡ A = Q1R1 (15.5)

ThenA1 ≡ R1Q1. (15.6)

In general givenAk = RkQk, (15.7)

obtain Ak+1 byAk = Qk+1Rk+1, Ak+1 = Rk+1Qk+1 (15.8)

This algorithm was proposed by Francis in 1961. The sequence {Ak} is the desiredsequence of iterates. Now with the above definition of the algorithm, here are its properties.The next lemma shows each of the Ak is unitarily similar to A and the amazing thing aboutthis algorithm is that often it becomes increasingly easy to find the eigenvalues of the Ak.