Spectral Theorem

THE SPECTRAL THEOREM Let A be an n × n symmetric real matrix. An amazing fact is that we can write A as     λ1 − ~v1 −   λ2 | | | |   − ~v2 −       λ ~v1 ~v2 ~v2 · · · ~vn   3   − ~v3 −      .. | | | |  − ··· −   . − ~vn − λn with ~v1 , ~v2 , . . . , ~vn orthonormal vectors. Here is how we compute1 the λ’s and the ~v ’s. The fact that this method works involves what seems to be some amazing pieces of good fortune. Step 1 Compute the characteristic polynomial det(A − kId). Factor this polynomial as (λ1 − k)(λ2 − k) · · · (λn − k). The Fundamental Theorem of Algebra2 promises us that such a factorization is possible if we use complex numbers. However, it turns out in our case that life is much better than this: Lucky Fact 1: All the roots of f are real. Step 2 For each eigenvalue λ, compute an orthonormal basis for Ker(A − λId). Putting all these bases together gives us a list of vectors: ~v1 , ~v2 , . . . . Lucky Fact 2: The geometric multiplicity of λ, meaning the dimension of this kernel, is equal to the number of times λ occurs as a root of f . Thus, the total number of vectors in our list is equal to the number of roots of f , which is n. Lucky Fact 3: These vectors form an orthonormal basis of Rn . In the rest of this note, we will explain why we got so lucky. A key fact We will use the following key fact twice below: Key Fact: Suppose that ~u and ~v are eigenvectors of A, with A~u = λ~u A~v = µ~v . Suppose that λ 6= µ. Then ~u and ~v are orthogonal. To see this, we compute ~uT A~v in two ways. We have ~uT A~v = ~uT (λ~v ) = λ~uT ~v . 1This is how to do the computation by hand. MATLAB uses a rather more sophisticated approach. 2The fundamental theorem of algebra is too hard for this course. The easiest exposition I know is at http://www.math.binghamton.edu/loya/papers/LoyaFTA.pdf. But, also, ~uT A~v = (~v T AT ~u)T = (~v T A~u)T , where we have replaced AT by A because A is symmetric. And (~v T A~u)T = (~v T µ~u)T = µ(~v T ~u)T = µ(~uT ~v ). Putting it all together, λ~uT ~v = µ~uT ~v . Since λ 6= µ, we get ~uT ~v = 0. In other words, the dot product ~u · ~v is 0 or, in still other words, ~u and ~v are orthogonal. We now start explaining the Lucky Facts. Lucky Fact 1 Suppose that f had a complex root, λ = a + bi. Let the corresponding eigenvector be ~x + i~y , with x and y each real vectors. So A(~x + i~y ) = (a + bi)(~x + i~y ). Taking complex conjugates of everything, we also have A(~x − i~y ) = (a − bi)(~x − i~y ). So ~x − i~y is also an eigenvector, with eigenvalue a − bi. Now, if λ is complex, then b 6= 0, and a + bi 6= a − bi. We can now use the Key Fact, with ~u = ~x + i~y and ~v = ~x − i~y . (You probably expected us to use the Key Fact for real vectors, but there is nothing about our argument that needed the entries to be real.) So we deduce that ~u · ~v = 0. Plugging in the formulas for ~u and ~v , that (~x + i~y ) · (~x − i~y ) = 0. But (~x + i~y ) · (~x − i~y ) = ~x · ~x − i~x · ~y + i~y · ~x + ~y · ~y = ~x · ~x + ~y · ~y = |~x|2 + |~y |2 . There is no way this is zero. (Remember that ~x and ~y have real entries.) More precisely, the only way it could be zero is if ~x = ~y = 0, but then ~x + i~y is 0 and is not an example of a nontrivial eigenvector. We started out supposing that f has a complex root, and reached the absurd conclusion that |~x|2 + |~y |2 = 0. The resolution is that, in fact, f doesn’t have any complex roots, and all its roots are real. (Here we are using the Fundamental Theorem of Algebra to know that there are n roots total – real and complex.) Lucky Fact 1 explained! Lucky Fact 2 Let λ be a root of f (k), so det(A − λId) = 0. Let r be the geometric multiplicity of λ, meaning that there is an r dimensional space of solutions to the equation A~v = λ~v . Let ~v1 , ~v2 , . . . , ~vr be an orthonormal basis for the space of solutions to A~v = λ~v . Find additional vectors ~vr+1 , . . . , ~vn so that ~v1 , ~v2 , . . . , ~vr , ~vr+1 , . . . ~vn is an orthonormal basis for Rn . For r + 1 ≤ i ≤ n, we can write A~vi = n X j=1 cij ~vj for some coefficients cij . We can organize these equations into a matrix. For concreteness, we take r = 2 and n = 5.      λ  | |  | | | | | | | | λ      ~v1 ~v2 ~v3 ~v4 ~v5  c31 c32 c33 c34 c35  = A · ~v1 ~v2 ~v3 ~v4 ~v5       | | | | | | | | | |  c41 c42 c43 c44 c45  c51 c52 c53 c54 c55 You may recognize this argument from the November 13 notes.  Let   | | | | |    S = ~v1 ~v2 ~v3 ~v4 ~v5  . | | | | | But ~v1 , ~v2 , . . . , ~vn is an orthonormal basis,  λ   S T AS =  c31 c41 c51 So SAS −1 λ    λ    = c31 c32 c33 c34 c35  . c41 c42 c43 c44 c45  c51 c52 c53 c54 c55 so S is orthogonal and S −1 = S T . So we have   λ  c32 c33 c34 c35  . c42 c43 c44 c45  c52 c53 c54 c55 Notice that (S T AS)T = S T AT S = S T AS, so the above matrix is symmetric. In particular, that lower left block is entirely zero and we have   λ   λ   S −1 AS =     C for some symmetric (n − r) × (n − r) matrix C. As in the November 13 notes, we see that     λ λ−k    λ  λ−k    det(A − k · Idn ) = det   − k · Idn  = det      C − k · Idn−r C     = (λ − k)r det(C − k · Idn−r ). Our goal is to show that λ − k divides det(A − k · Idn ) exactly r times. So we want to know that λ − k does not divide det(C − kIdn−r ). In other words, we want to know that λ is not an eigenvalue of C. Suppose, to the contrary that C~u = λ~u. Then   λ     0  0  λ       0 = 0 .    ~u λ~u C So 0 0 ~ u is another λ eigenvector for A, which should have been listed when we found the vi . Lucky Fact 3 We need to explain two things: Why the ~vi are orthonormal, and why they are a basis. If ~vi and ~vj both come from the same eigenvalue λ, then ~vi ·~vj = 0 because we chose an orthonormal basis for the λ-eigenspace. Also, the ~vi all have length 1 because we chose an orthonormal basis in this place. If ~vi and ~vj come from different eigenvalues, then the Key Fact tells us that ~vi and ~vj are perpendicular. So we also have perpendicularity between these vectors. Since the ~vi are orthonormal, they are linearly independent. From Lucky Fact 2, the number of ~vi coming from each λ is the same as the number of times (λ − k) divides f (k), and the polynomial f has degree n. So the total number of vectors ~vi is n. We have n linearly independent vectors in Rn , so we have a basis for Rn . We have now explained all of our Lucky Facts, and shown that every symmetric matrix has a basis of eigenvectors.