13.5. EXERCISES 339

Corollary 13.4.7 Suppose one of the Gerschgorin discs, Di is disjoint from the union ofthe others. Then Di contains exactly one eigenvalue of A and this eigenvalue is a simpleroot to the characteristic polynomial of A.

Proof: In the proof of Corollary 13.4.5, note that aii is a simple root of A(0) sinceotherwise the ith Gerschgorin disc would not be disjoint from the others. Also, K, theconnected component determined by aii must be contained in Di because it is connectedand by Gerschgorin’s theorem above, K ∩σ (A(t)) must be contained in the union of theGerschgorin discs. Since all the other eigenvalues of A(0) , the a j j, are outside Di, itfollows that K ∩σ (A(0)) = aii. Therefore, by Lemma 13.4.6, K ∩σ (A(1)) = K ∩σ (A)consists of a single simple eigenvalue. ■

Example 13.4.8 Consider the matrix 5 1 01 1 10 1 0

The Gerschgorin discs are D(5,1) ,D(1,2) , and D(0,1) . Observe D(5,1) is disjoint

from the other discs. Therefore, there should be an eigenvalue in D(5,1) . The actualeigenvalues are not easy to find. They are the roots of the characteristic equation, t3−6t2+3t + 5 = 0. The numerical values of these are −.66966,1.4231, and 5.24655, verifyingthe predictions of Gerschgorin’s theorem.

13.5 Exercises1. Explain why it is typically impossible to compute the upper triangular matrix whose

existence is guaranteed by Schur’s theorem.

2. Now recall the QR factorization of Theorem 12.3.9 on Page 316. The QR algorithmis a technique which does compute the upper triangular matrix in Schur’s theoremsometimes. There is much more to the QR algorithm than will be presented here.In fact, what I am about to show you is not the way it is done in practice. One firstobtains what is called a Hessenburg matrix for which the algorithm will work better.However, the idea is as follows. Start with A an n×n matrix having real eigenvalues.Form A = QR where Q is orthogonal and R is upper triangular. (Right triangular.)This can be done using the technique of Theorem 12.3.9 using Householder matrices.Next take A1 ≡ RQ. Show that A = QA1QT . In other words these two matrices, A,A1are similar. Explain why they have the same eigenvalues. Continue by letting A1play the role of A. Thus the algorithm is of the form An = QRn and An+1 = Rn+1Q.Explain why A=QnAnQT

n for some Qn orthogonal. Thus An is a sequence of matriceseach similar to A. The remarkable thing is that often these matrices converge to anupper triangular matrix T and A = QT QT for some orthogonal matrix, the limit ofthe Qn where the limit means the entries converge. Then the process computes theupper triangular Schur form of the matrix A. Thus the eigenvalues of A appear on thediagonal of T. You will see approximately what these are as the process continues.

3. ↑Try the QR algorithm on (−1 −26 6

)