Page 209 - Matrices theory and applications

10. Approximation of Eigenvalues
192
(a) For an upper triangular matrix T , compute explicitly KT and
TK.
(b) Let M ∈ M n (IR). Prove the equality
det(M − λI − µK)=(−1) µ det(M − λI) 1 +det(M − λI).
(c) Let A ∈ GL n (IR) be given, with factorization A = QR.Prove
that n
det R −1
det(A − λI) 1 = det(Q − λR ) 1 .
r nn

(d) Let A = RQ.Showthat

r nn det(A − λI) 1 = r 11 det(A − λI) 1 .
(e) Generalize the previous calculation by replacing the index 1 by
k. Deduce that the roots of the polynomial det(A − λI) k are
conserved throughout the QR algorithm. How many such roots
do we have for a general matrix? How many for a Hessenberg
matrix?
7. (Invariants; continuing) For M ∈ M n (IR), let us define P M (h; z):=
T
det((1 − h)M + hM − zI n ).
(a) Show that P M (h; z)= P M (1 − h; z). Deduce that there exists a
polynomial Q M such that P M (h; z)= Q M (h(1 − h); z).
(b) Show that Q M remains constant throughout the QR algorithm:
If Q ∈ O n (IR), R is upper triangular, and M = QR, N = RQ,
then Q M = Q N .
(c) Deduce that there exist polynomial functions J rk on M n (IR),
defined by

n [r/2]
k n−r
P M (h; z)= (h(1 − h)) z J rk (M),
r=0 k=0
that are invariant throughout the QR algorithm. Verify that the
J r0 ’s can be expressed in terms of invariants that we already
know.
(d) Compute explicitly J 21 when n = 2. Deduce that in the case
where Theorem 10.2.1 applies and det A> 0, the matrix A k
converges.
(e) Show that for n ≥ 2,
1
T 2
J 21 (M)= − Tr (M − M ) .
2
Deduce that if A k converges to a diagonal matrix, then A is
symmetric.