15.6. MATLAB AND THE QR ALGORITHM 365

15.6.1 The Upper Hessenberg FormActually, when using the QR algorithm, contrary to what is discussed above, you shouldalways deal with a matrix which is similar to the given matrix which is in upper Hessenbergform. This means all the entries below the sub diagonal equal 0. Here is an easy lemma.

Lemma 15.6.3 Let A be an n×n matrix. Then it is unitarily similar to a matrix in upperHessenberg form and this similarity can be computed.

Proof: Let A be an n×n matrix. Suppose n > 2. There is nothing to show otherwise.

A =

(a bd A1

)

where A1 is n− 1× n− 1. Consider the n− 1× 1 matrix d. Then let Q be a Householderreflection such that

Qb =

(c0

)≡ c

Then (1 00 Q

)(a bd A1

)(1 00 Q∗

)=

(a bQ∗

c QA1Q∗

)By similar reasoning, there exists an n−1×n−1 matrix

U =

(1 00 Q1

)

such that

(1 00 Q1

)QA1Q∗

(1 00 Q∗1

)=

∗ ∗ · · · ∗

∗ ∗. . .

.... . . . . . ∗

0 ∗ ∗

Thus (

1 00 U

)(a bQ∗

c QA1Q∗

)(1 00 U∗

)will have all zeros below the first two entries on the sub diagonal. Continuing this wayshows the result. ■

Not surprisingly, MATLAB can find a Hessenberg matrix for a given square matrix.Here is the syntax.

A=[2 1 3;-5,3,-2;1,2,3];[P,H]=hess(A)P’*A*P