436 CHAPTER 15. NUMERICAL METHODS, EIGENVALUES

Now let Q′2 be the n− 2× n− 2 matrix which does to the first column of A1 the samesort of thing that the n−1×n−1 matrix Q′1 did to the first column of A. Let

Q2 ≡

(I 00 Q′2

)where I is the 2×2 identity. Then applying block multiplication,

Q2Q1AQ∗1Q∗2 =



∗ ∗ · · · ∗ ∗∗ ∗ · · · ∗ ∗0 ∗...

... A2

0 0

where A2 is now an n−2×n−2 matrix. Continuing this way you eventually get a unitarymatrix Q which is a product of those discussed above such that

QAQT =



∗ ∗ · · · ∗ ∗∗ ∗ · · · ∗ ∗

0 ∗ ∗...

......

. . . . . . ∗0 0 ∗ ∗

This matrix equals zero below the subdiagonal. It is called an upper Hessenberg matrix.

It happens that in the QR algorithm, if Ak is upper Hessenberg, so is Ak+1. To see this,note that the matrix is upper Hessenberg means that Ai j = 0 whenever i− j ≥ 2.

Ak+1 = RkQk

where Ak = QkRk. Therefore as shown before,

Ak+1 = RkAkR−1k

Let the i jth entry of Ak be aki j. Then if i− j ≥ 2

ak+1i j =

n

∑p=i

j

∑q=1

ripakpqr−1

q j

It is given that akpq = 0 whenever p−q≥ 2. However, from the above sum,

p−q≥ i− j ≥ 2

and so the sum equals 0.Since upper Hessenberg matrices stay that way in the algorithm and it is closer to being

upper triangular, it is reasonable to suppose the QR algorithm will yield good results morequickly for this upper Hessenberg matrix than for the original matrix. This would be espe-cially true if the matrix is good sized. The other important thing to observe is that, startingwith an upper Hessenberg matrix, the algorithm will restrict the size of the blocks whichoccur to being 2×2 blocks which are easy to deal with. These blocks allow you to identifythe eigenvalues.