Spectral theorem: eigenvalue decomposition for symmetric matrices

L. El Ghaoui

Spectral theorem: eigenvalue decomposition for symmetric matrices

Spectral theorem

We can decompose any symmetric matrix $A \in {\bf S}^n$ with the symmetric eigenvalue decomposition (SED)

$A = \sum\limits_{i=1}^n \lambda_i u_i u_i^T = U\Lambda U^T, \Lambda = {\bf diag}(\lambda_1, \lambda_2, cdots, \lambda_n).$

where the matrix of $U:=[u_1, \cdots, u_n]$ is orthogonal (that is, $U^TU=UU^T=I_n$ ), and contains the eigenvectors of $A$ , while the diagonal matrix $\Lambda$ contains the eigenvalues of $A$ .

Proof: The proof is by induction on the size $n$ of the matrix $A$ . The result is trivial for $n=1$ . Now let $n>1$ and assume the result is true for any matrix of size $n-1$ .

Consider the function of $A$ , $t\rightarrow p(t) = \det (tI-A)$ . From the basic properties of the determinant, it is a polynomial of degree $n$ , called the characteristic polynomial of $A$ . By the fundamental theorem of algebra, any polynomial of degree $n$ has $n$ (possibly not distinct) complex roots; these are called the eigenvalues of $A$ . We denote these eigenvalues by $\lambda_1, \cdots, \lambda_n$ .

If $\lambda$ is an eigenvalue of $A$ , that is, $\det (\lambda I-A)=0$ , then $\lambda I- A$ must be non-invertible (see here). This means that there exists a non-zero real vector $u$ such that $Au = \lambda u$ . We can always normalize $u$ so that $u^Tu=1$ . Thus, $\lambda = u^TAu$ is real. That is, the eigenvalues of a symmetric matrix are always real.

Now consider the eigenvalue $\lambda_1$ and an associated eigenvector $u_1$ . Using the Gram-Schmidt orthogonalization procedure, we can compute a $n \times (n-1)$ matrix $V_1$ such that $[u_1, V_1]$ is orthogonal. By induction, we can write the $(n-1) \times (n-1)$ symmetric matrix $V_1^T A V_1$ as, $Q_1^T A Q_1$ where $Q_1$ is a $(n-1) \times (n-1)$ matrix of eigenvectors, and $\Lambda_1 = {\bf diag}(\lambda_2, \cdots, \lambda_n)$ are the $n-1$ eigenvalues of $V_1^T A V_1$ . Finally, we define the $n \times (n-1)$ matrix $U_1:= V_1 Q_1$ . By construction the matrix $U:= [u_1, U_1]$ is orthogonal.

We have

$U^T A U=\left(\begin{array}{c} u_1^T \\ U_1^T \end{array}\right) A\left(\begin{array}{cc} u_1 & U_1 \end{array}\right)=\left(\begin{array}{cc} 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{array}\right)=\left(\begin{array}{cc} \lambda_1 & 0 \\ 0 & \Lambda_1 \end{array}\right),$

where we have exploited the fact that $U_1^T A u_1 = \lambda_1 U_1^T u_1 = 0$ , and $U_1^T A U_1 =\Lambda_1$ .

We have exhibited an orthogonal $n \times n$ matrix $U$ such that $U^TAU$ is diagonal. This proves the theorem.

Spectral theorem: eigenvalue decomposition for symmetric matrices

License

Share This Book