Spectral theorem
|
We can decompose any symmetric matrix [latex]A \in {\bf S}^n[/latex] with the symmetric eigenvalue decomposition (SED) [latex]\begin{align*} A &= \sum\limits_{i=1}^n \lambda_i u_i u_i^T = U\Lambda U^T, \quad \Lambda = \textbf{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n). \\ \end{align*}[/latex] where the matrix of [latex]U:=[u_1, \cdots, u_n][/latex] is orthogonal (that is, [latex]U^TU=UU^T=I_n[/latex]), and contains the eigenvectors of [latex]A[/latex], while the diagonal matrix [latex]\Lambda[/latex] contains the eigenvalues of [latex]A[/latex]. |
Proof: The proof is by induction on the size [latex]n[/latex] of the matrix [latex]A[/latex]. The result is trivial for [latex]n=1[/latex]. Now let [latex]n>1[/latex] and assume the result is true for any matrix of size [latex]n-1[/latex].
Consider the function of [latex]A[/latex], [latex]t\rightarrow p(t) = \det (tI-A)[/latex]. From the basic properties of the determinant, it is a polynomial of degree [latex]n[/latex], called the characteristic polynomial of [latex]A[/latex]. By the fundamental theorem of algebra, any polynomial of degree [latex]n[/latex] has [latex]n[/latex] (possibly not distinct) complex roots; these are called the eigenvalues of [latex]A[/latex]. We denote these eigenvalues by [latex]\lambda_1, \cdots, \lambda_n[/latex].
If [latex]\lambda[/latex] is an eigenvalue of [latex]A[/latex], that is, [latex]\det (\lambda I-A)=0[/latex], then [latex]\lambda I- A[/latex] must be non-invertible (see here). This means that there exists a non-zero real vector [latex]u[/latex] such that [latex]Au = \lambda u[/latex]. We can always normalize [latex]u[/latex] so that [latex]u^Tu=1[/latex]. Thus, [latex]\lambda = u^TAu[/latex] is real. That is, the eigenvalues of a symmetric matrix are always real.
Now consider the eigenvalue [latex]\lambda_1[/latex] and an associated eigenvector [latex]u_1[/latex]. Using the Gram-Schmidt orthogonalization procedure, we can compute a [latex]n \times (n-1)[/latex] matrix [latex]V_1[/latex] such that [latex][u_1, V_1][/latex] is orthogonal. By induction, we can write the [latex](n-1) \times (n-1)[/latex] symmetric matrix [latex]V_1^T A V_1[/latex] as, [latex]Q_1^T A Q_1[/latex] where [latex]Q_1[/latex] is a [latex](n-1) \times (n-1)[/latex] matrix of eigenvectors, and [latex]\Lambda_1 = {\bf diag}(\lambda_2, \cdots, \lambda_n)[/latex] are the [latex]n-1[/latex] eigenvalues of [latex]V_1^T A V_1[/latex]. Finally, we define the [latex]n \times (n-1)[/latex] matrix [latex]U_1:= V_1 Q_1[/latex]. By construction the matrix [latex]U:= [u_1, U_1][/latex] is orthogonal.
We have
[latex]\begin{align*} U^T A U &= \begin{pmatrix} u_1^T \\ U_1^T \end{pmatrix} A \begin{pmatrix} u_1 & U_1 \end{pmatrix} = \begin{pmatrix} u_1^T A u_1 & u_1^T A U_1 \\ U_1^T A u_1 & U_1^T A U_1 \end{pmatrix} = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \Lambda_1 \end{pmatrix}, \end{align*}[/latex]
where we have exploited the fact that [latex]U_1^T A u_1 = \lambda_1 U_1^T u_1 = 0[/latex], and [latex]U_1^T A U_1 =\Lambda_1[/latex].
We have exhibited an orthogonal [latex]n \times n[/latex] matrix [latex]U[/latex] such that [latex]U^TAU[/latex] is diagonal. This proves the theorem.
