13.9. EXERCISES 331
56. Prove the Cayley Hamilton theorem as follows. First suppose A has a basis ofeigenvectors {vk}n
k=1 ,Avk = λ kvk. Let p(λ ) be the characteristic polynomial. Showp(A)vk = p(λ k)vk = 0. Then since {vk} is a basis, it follows p(A)x = 0 for all xand so p(A) = 0. Next in the general case, use Problem 55 to obtain a sequence {Ak}of matrices whose entries converge to the entries of A such that Ak has n distincteigenvalues and therefore by Theorem 12.1.15 Ak has a basis of eigenvectors. There-fore, from the first part and for pk (λ ) the characteristic polynomial for Ak, it followspk (Ak) = 0. Now explain why and the sense in which limk→∞ pk (Ak) = p(A) .
57. Show that the Moore Penrose inverse A+ satisfies the following conditions.
AA+A = A, A+AA+ = A+, A+A, AA+ are Hermitian.
Next show that if A0 satisfies the above conditions, then it must be the Moore Pen-rose inverse and that if A is an n× n invertible matrix, then A−1 satisfies the aboveconditions. Thus the Moore Penrose inverse generalizes the usual notion of inversebut does not contradict it. Hint: Let
U∗AV = Σ≡
(σ 00 0
)
and suppose
V+A0U =
(P QR S
)where P is the same size as σ . Now use the conditions to identify P = σ ,Q = 0 etc.
58. Find the least squares solution to 1 11 11 1+ ε
( xy
)=
abc
Next suppose ε is so small that all ε2 terms are ignored by the computer but the termsof order ε are not ignored. Show the least squares equations in this case reduce to(
3 3+ ε
3+ ε 3+2ε
)(xy
)=
(a+b+ c
a+b+(1+ ε)c
).
Find the solution to this and compare the y values of the two solutions. Show thatone of these is −2 times the other. This illustrates a problem with the technique forfinding least squares solutions presented as the solutions to A∗Ax = A∗y. One wayof dealing with this problem is to use the QR factorization. This is illustrated in thenext problem. It turns out that this helps alleviate some of the round off difficultiesof the above.
59. Show that the equations A∗Ax = A∗y can be written as R∗Rx = R∗Q∗y where R isupper triangular and R∗ is lower triangular. Explain how to solve this system effi-ciently. Hint: You first find Rx and then you find x which will not be hard because Ris upper triangular.