Spectral Theorem

L. El Ghaoui

Spectral Theorem

Eigenvalues and eigenvectors of symmetric matrices
The symmetric eigenvalue decomposition theorem
Rayleigh quotients

Eigenvalues and eigenvectors of symmetric matrices

Let $A$ be a square, $n \times n$ symmetric matrix. A real scalar $\lambda$ is said to be an eigenvalue of $A$ if there exist a non-zero vector $u \in \mathbb{R}^n$ such that

$Au = \lambda u.$

The vector $u$ is then referred to as an eigenvector associated with the eigenvalue $\lambda$ . The eigenvector $u$ is said to be normalized if $||u||_2=1$ . In this case, we have

$u^TAu = \lambda u^Tu = \lambda.$

The interpretation of $u$ is that it defines a direction along $A$ behaves just like scalar multiplication. The amount of scaling is given by $\lambda$ . (In German, the root ‘‘eigen’’, means ‘‘self’’ or ‘‘proper’’). The eigenvalues of the matrix $A$ are characterized by the characteristic equation

$\det(\lambda I - A) = 0,$

where the notation $\det$ refers to the determinant of its matrix argument. The function with values $t \rightarrow p(t): = \det(tI-A)$ is a polynomial of degree $n$ called the characteristic polynomial.

From the fundamental theorem of algebra, any polynomial of degree $n$ has $n$ (possibly not distinct) complex roots. For symmetric matrices, the eigenvalues are real, since $\lambda =u^TAu$ when $A u =\lambda u$ , and $u$ is normalized.

Spectral theorem

An important result of linear algebra called the spectral theorem, or symmetric eigenvalue decomposition (SED) theorem, states that for any symmetric matrix, there are exactly $n$ (possibly not distinct) eigenvalues, and they are all real; further, that the associated eigenvectors can be chosen so as to form an orthonormal basis. The result offers a simple way to decompose the symmetric matrix as a product of simple transformations.

Theorem: Symmetric eigenvalue decomposition

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, \quad \Lambda=\operatorname{diag}\left(\lambda_1, \ldots, \lambda_n\right).$

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$ .

Here is a proof. The SED provides a decomposition of the matrix in simple terms, namely dyads.

We check that in the SED above, the scalars $\lambda_i$ are the eigenvalues, and $u_i$ ‘s are associated eigenvectors, since

$A u_j = \sum\limits_{i=1}^n \lambda_i u_i u_i^T u_j = \lambda_j u_j, \quad j = 1,\cdots,n.$

The eigenvalue decomposition of a symmetric matrix can be efficiently computed with standard software, in time that grows proportionately to its dimension $n$ as $n^3$ . Here is the MatLab syntax, where the first line ensures that MatLab knows that the matrix $A$ is exactly symmetric.

Matlab syntax

>> A = triu(A)+tril(A',-1);
>> [U,D] = eig(A);

Example:

Eigenvalue decomposition of a $2 \times 2$ symmetric matrix.

Rayleigh quotients

Given a symmetric matrix $A$ , we can express the smallest and largest eigenvalues of $A$ , denoted $\lambda_{\min}$ and $\lambda_{\max}$ respectively, in the so-called variational form

$\lambda_{\min }(A)=\min _x\left\{x^T A x: x^T x=1\right\}, \lambda_{\max }(A)=\max _x\left\{x^T A x: x^T x=1\right\}.$

For proof, see here.

The term ‘‘variational’’ refers to the fact that the eigenvalues are given as optimal values of optimization problems, which were referred to in the past as variational problems. Variational representations exist for all the eigenvalues but are more complicated to state.

The interpretation of the above identities is that the largest and smallest eigenvalues are a measure of the range of the quadratic function $x \rightarrow x^TAx$ over the unit Euclidean ball. The quantities above can be written as the minimum and maximum of the so-called Rayleigh quotient $x^TAx/x^Tx$ .

Historically, David Hilbert coined the term ‘‘spectrum’’ for the set of eigenvalues of a symmetric operator (roughly, a matrix of infinite dimensions). The fact that for symmetric matrices, every eigenvalue lies in the interval $[\lambda_{\min}, \lambda_{\max}]$ somewhat justifies the terminology.

Example: Largest singular value norm of a matrix.

Spectral Theorem

Eigenvalues and eigenvectors of symmetric matrices

Spectral theorem

Rayleigh quotients

License

Share This Book