15.5. THE QR ALGORITHM 361

15.5 The QR Algorithm15.5.1 Basic ConsiderationsThe QR algorithm is one of the most remarkable techniques for finding eigenvalues. In thissection, I will discuss this method. To see more on this algorithm, consult Golub and VanLoan [6]. For an explanation of why the algorithm works see Wilkinson [18]. There isalso more discussion in [13]. This will only discuss real matrices for the sake of simplicity.Also, there is a lot more to this algorithm than will be presented here. First here is anintroductory lemma.

Lemma 15.5.1 Suppose A is a block upper triangular matrix,

A =

B1 ∗

. . .

0 Br

This means that the Bi are ri×ri matrices whose diagonals are subsets of the main diagonalof A. Then σ (A) = ∪r

i=1σ (Bi).

Proof: Say Q∗i BiQi = Ti where Ti is upper triangular. Such unitary matrices exist bySchur’s theorem. Then consider the similarity transformation,

Q∗1 0. . .

0 Q∗r



B1 ∗. . .

0 Br



Q1 0. . .

0 Qr

By block multiplication this equals

Q∗1 0. . .

0 Q∗r



B1Q1 ∗. . .

0 BrQr



=

Q∗1B1Q1 ∗

. . .

0 Q∗r BrQr

=

T1 ∗

. . .

0 Tr

Now this is a real upper triangular matrix and the eigenvalues of A consist of the union ofthe eigenvalues of the Ti which is the same as the union of the eigenvalues of the Bi. ■

Here is the description of the great and glorious QR algorithm.

The QR Algorithm

Let A be an n×n real matrix. Let A0 = A. Suppose that Ak−1 has been found. To findAk let

Ak−1 = QkRk, Ak = RkQk,

where QkRk is a QR factorization of Ak−1. Thus R is upper triangular with nonnegativeentries on the main diagonal and Q is real and unitary (orthogonal).