26 Symmetric Matrices, Spectral Theorem, Rayleigh Quotient

Lecture from 13.12.2024 | Video: Videos ETHZ

Recap of Previous Results

Last few lectures, we established key results concerning eigenvalues, eigenvectors, and diagonalization:

• Complete Set of Eigenvectors: We explored conditions under which a matrix possesses a complete set of eigenvectors that form a basis for the vector space.

  • We proved that matrices with distinct eigenvalues always have a complete set.
  • We also showed that diagonal matrices and projection matrices always have complete sets of eigenvectors.
  • A crucial concept introduced was that for a matrix to have a complete set of eigenvectors, the geometric multiplicity of each eigenvalue (dimension of its eigenspace) must equal its algebraic multiplicity (number of times it appears as a root of the characteristic polynomial).

• Diagonalization: If a matrix $A\in {\mathbb{R}}^{n\times n}$ has a complete set of eigenvectors, it can be diagonalized as $A=V\Lambda V^{-1}$, where $V$ is the matrix whose columns are the eigenvectors, and $\Lambda$ is a diagonal matrix with the corresponding eigenvalues.

• Similar Matrices: We defined similar matrices ($B=S^{-1}AS$ for some invertible $S$) and proved that similar matrices share the same eigenvalues.

Now, building upon these foundations, we delve into the specific and important case of symmetric matrices. We want to address the question: for which matrices $A\in {\mathbb{R}}^{n\times n}$ do we have:

1. All eigenvalues ${\lambda }_i$ are real.
2. The geometric multiplicity of each eigenvalue ${\lambda }_i$ is equal to its algebraic multiplicity $m_i$.

We’ve already seen that diagonal and projection matrices satisfy these conditions. While having distinct real eigenvalues guarantees real eigenvalues and equal algebraic and geometric multiplicities, this condition is not necessary. We are seeking a more general characterization. This leads us to the Singular Value Decomposition (SVD), a powerful factorization that applies to all matrices. However, before tackling the SVD, we’ll first analyze a crucial special case: symmetric matrices. Understanding the properties of symmetric matrices will provide essential building blocks for the SVD.

Symmetric Matrices: A Special Case

Definition: A matrix $A\in {\mathbb{R}}^{n\times n}$ is symmetric if $A^T=A$. That is, the entries of A are symmetric across the main diagonal: $a_{ij}=a_{ji}.$

Symmetric matrices possess remarkable properties that greatly simplify their eigenstructure and have profound implications in various applications.

Real Eigenvalues for Symmetric Matrices

Proposition: If $A$ is a real symmetric matrix ($A\in {\mathbb{R}}^{n\times n}$ and $A^T=A$), then all its eigenvalues are real.

2x2 Example:

Proof: Eigenvalues of Real Symmetric Matrices are Real

This is simpler than it seems! Here’s the key idea: we’ll use the properties of the conjugate transpose (denoted by $X^{\ast }$) to show that any eigenvalue must be equal to its own conjugate, which means it has to be real.

1. Conjugate Transpose: For any matrix (or vector) $X$ with complex entries, $X^{\ast }$ (also denoted as Hermitian of a matrix $X^H$) is formed by taking the transpose of $X$ and then taking the complex conjugate of each entry. For example:

   If $X=\left[\begin{array}{cc}1+i& 2\\ 3i& 4-i\end{array}\right]$, then $X^{\ast }=\left[\begin{array}{cc}1-i& -3i\\ 2& 4+i\end{array}\right]$

   Important properties of the conjugate transpose:

   • $(XY{)}^{\ast }=Y^{\ast }{X}^{\ast }$
   • For a real matrix $A$, $A^{\ast }=A^T$
   • For a scalar $c$, $c^{\ast }=\bar{c}$ is the complex conjugate
   • For a vector $\mathbf{v}$, ${\mathbf{v}}^{\ast }\mathbf{v}=||v|{|}^2$, the squared magnitude of $\mathbf{v}.$

2. Setting Up: Let $\lambda$ be an eigenvalue of $A$ with a corresponding eigenvector $\mathbf{v}$ (which might be complex). This means: $A\mathbf{v}=\lambda \mathbf{v}$

3. Taking the Conjugate Transpose: Applying the conjugate transpose to both sides of the equation: $(A\mathbf{v}{)}^{\ast }=(\lambda \mathbf{v}{)}^{\ast }$ ${\mathbf{v}}^{\ast }{A}^{\ast }=\bar{\lambda }{\mathbf{v}}^{\ast }$ (Using properties from step 1).

4. Using Symmetry: Since A is real and symmetric, $A^{\ast }=A^T=A$. Substituting this into our equation: ${\mathbf{v}}^{\ast }A=\bar{\lambda }{\mathbf{v}}^{\ast }$

5. The Trick: Now, let’s be clever. Left-multiply the original eigenvector equation ($A\mathbf{v}=\lambda \mathbf{v}$) by ${\mathbf{v}}^{\ast }$: ${\mathbf{v}}^{\ast }A\mathbf{v}=\lambda {\mathbf{v}}^{\ast }\mathbf{v}$

6. Substituting: From step 4, we know ${\mathbf{v}}^{\ast }A=\bar{\lambda }{\mathbf{v}}^{\ast }$. Substitute this into the equation from step 5: $\bar{\lambda }{\mathbf{v}}^{\ast }\mathbf{v}=\lambda {\mathbf{v}}^{\ast }\mathbf{v}$

7. Conclusion: Since $\mathbf{v}$ is non-zero (it’s an eigenvector!), ${\mathbf{v}}^{\ast }\mathbf{v}=||\mathbf{v}|{|}^2>0$. We can safely divide both sides by ${\mathbf{v}}^{\ast }\mathbf{v}$:

   $\bar{\lambda }=\lambda$

   This means $\lambda$ equals its own conjugate. The only way a complex number can be equal to its conjugate is if it’s a real number! Therefore, $\lambda$ must be real.

Orthogonal Eigenvectors for Distinct Eigenvalues of Symmetric Matrices

Proposition: If $A$ is a symmetric matrix and ${\mathbf{v}}_1$ and ${\mathbf{v}}_2$ are eigenvectors corresponding to distinct eigenvalues ${\lambda }_1$ and ${\lambda }_2$, then ${\mathbf{v}}_1$ and ${\mathbf{v}}_2$ are orthogonal, i.e $v_1\perp v_2$.

Proof

We have $A{\mathbf{v}}_1={\lambda }_1{\mathbf{v}}_1$ and $A{\mathbf{v}}_2={\lambda }_2{\mathbf{v}}_2$.

1. Pre-multiply the first equation by ${\mathbf{v}}_2^T$: ${\mathbf{v}}_2^{T}A{\mathbf{v}}_1={\lambda }_1{\mathbf{v}}_2^T{\mathbf{v}}_1$.

2. Transpose the second equation and post-multiply by ${\mathbf{v}}_1$: $(A{\mathbf{v}}_2{)}^T=({\lambda }_2{\mathbf{v}}_2{)}^T⟹{\mathbf{v}}_2^T{A}^T={\lambda }_2{\mathbf{v}}_2^T.$ Then ${\mathbf{v}}_2^T{A}^T{\mathbf{v}}_1={\lambda }_2{\mathbf{v}}_2^T{\mathbf{v}}_1$.

3. Since $A$ is symmetric, $A=A^T$, so: ${\mathbf{v}}_2^{T}A{\mathbf{v}}_1={\lambda }_2{\mathbf{v}}_2^T{\mathbf{v}}_1$.

4. Now we have two equations:

   • ${\mathbf{v}}_2^{T}A{\mathbf{v}}_1={\lambda }_1{\mathbf{v}}_2^T{\mathbf{v}}_1$
   • ${\mathbf{v}}_2^{T}A{\mathbf{v}}_1={\lambda }_2{\mathbf{v}}_2^T{\mathbf{v}}_1$

   Subtracting the second equation from the first:

   $0=({\lambda }_1-{\lambda }_2){\mathbf{v}}_2^T{\mathbf{v}}_1$

5. Since ${\lambda }_1\ne {\lambda }_2$, we must have ${\mathbf{v}}_2^T{\mathbf{v}}_1=0$, which means ${\mathbf{v}}_1$ and ${\mathbf{v}}_2$ are orthogonal.

The Spectral Theorem

The Spectral Theorem is a cornerstone result in linear algebra, revealing the profound connection between symmetric matrices and orthonormal bases. It states that real symmetric matrices are always diagonalizable by an orthogonal matrix and have real eigenvalues.

Theorem (Spectral Theorem): Every symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ possesses the following properties:

1. Real Eigenvalues: All eigenvalues of $A$ are real.
2. Orthogonal Eigenvectors: Eigenvectors corresponding to distinct eigenvalues are orthogonal.
3. Orthonormal Basis of Eigenvectors: There exists an orthonormal basis for ${\mathbb{R}}^n$ composed entirely of eigenvectors of $A$.
4. Diagonalization by an Orthogonal Matrix: $A$ can be factored as: $A=Q\Lambda Q^T$ where:
   • $Q\in {\mathbb{R}}^{n\times n}$ is an orthogonal matrix ($Q^{T}Q=I$) whose columns are the orthonormal eigenvectors of $A$.
   • $\Lambda \in {\mathbb{R}}^{n\times n}$ is a diagonal matrix whose diagonal entries are the corresponding eigenvalues of $A$.

Equivalent Formulation: Every symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ has $n$ real eigenvalues (counting multiplicities) and an orthonormal basis of ${\mathbb{R}}^n$ formed by the eigenvectors of $A.$

Symmetric Matrices and Positive Definiteness... (MIT)

Proof of the Spectral Theorem (by Induction)

For every $k\in \{1,\dots ,n\}$, there exist $k$ orthonormal eigenvectors of $A$.

Base Case ($k=1$)

We know that $A$ has at least one real eigenvalue ${\lambda }_1$ (this was proven earlier). Let ${\mathbf{v}}_1$ be a corresponding eigenvector. Since ${\mathbf{v}}_1$ is non-zero, we can normalize it to obtain an eigenvector of unit length: ${\mathbf{v}}_1^{\prime }=\frac{{\mathbf{v}}_1}{||{\mathbf{v}}_1||}$. This gives us one orthonormal eigenvector.

The Inductive Step

Inductive Hypothesis

Assume that for some $k$, where $1\le k<n$, there exist $k$ orthonormal eigenvectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k$ of the symmetric matrix $A\in {\mathbb{R}}^{n\times n}$, with corresponding real eigenvalues ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k$.

Construction

1. Subspace and its Orthogonal Complement:

   • Let $S=\text{span}\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k\}$ be the subspace spanned by the first $k$ orthonormal eigenvectors.
   • Let $S^{\perp }$ be the orthogonal complement of $S$. Since $\dim (S)+\dim (S^{\perp })=n$, we have $\dim (S^{\perp })=n-k$.

2. Orthonormal Basis for $S^{\perp }$:

   • Let $\{{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_{n-k}\}$ be an orthonormal basis for $S^{\perp }$.

3. The Key Idea: To extend to $k+1$ orthonormal eigenvectors, we must find a new eigenvector in $S^{\perp }$. This ensures it’s orthogonal to the existing eigenvectors (by definition of $S^{\perp }$). The strategy involves showing that $A$ maps vectors from $S^{\perp }$ to $S^{\perp }$ which allows us to restrict the problem to a smaller subspace.

Showing that $A$ maps $S^{\perp }$ to $S^{\perp }$

Crucial Lemma: If $A$ is symmetric and $\mathbf{x}\in S^{\perp }$ then $A\mathbf{x}\in S^{\perp }$

Proof: Since $\mathbf{x}$ is in $S^{\perp }$, it’s orthogonal to each of the vectors ${\mathbf{v}}_1,...,{\mathbf{v}}_k.$ We must show that $A\mathbf{x}$ is also orthogonal to each ${\mathbf{v}}_i.$ Consider the dot product of $A\mathbf{x}$ with an arbitrary ${\mathbf{v}}_i$:

$(A\mathbf{x}{)}^T{\mathbf{v}}_i={\mathbf{x}}^T{A}^T{\mathbf{v}}_i={\mathbf{x}}^T(A{\mathbf{v}}_i)={\mathbf{x}}^T({\lambda }_i{\mathbf{v}}_i)={\lambda }_i({\mathbf{x}}^T{\mathbf{v}}_i)={\lambda }_i\cdot 0=0.$ (Recall that A is symmetric so $A^T=A$, and ${\mathbf{v}}_i$ is an eigenvector so $A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$, and $\mathbf{x}$ is orthogonal to ${\mathbf{v}}_i$ so their dot product is 0). Since $A\mathbf{x}$ is orthogonal to every basis vector of $S$, $A\mathbf{x}$ is in $S^{\perp }.$

Constructing the Matrix $B$

1. Matrix $V_k$ : Form a matrix $V_k\in {\mathbb{R}}^{n\times n}$ whose columns are the vectors $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k,{\mathbf{u}}_1,\dots ,{\mathbf{u}}_{n-k}\}$. Note that $V_k$ is orthogonal since its columns form an orthornormal basis for ${\mathbb{R}}^n.$ Consequently $V_k^{-1}=V_k^T.$

2. Matrix $B$ : Define $B=V_k^{T}A{V}_k$.

   $$B=\left[\begin{array}{c}{\mathbf{v}}_1^T\\ ⋮\\ {\mathbf{v}}_k^T\\ {\mathbf{u}}_1^T\\ ⋮\\ {\mathbf{u}}_{n-k}^T\end{array}\right]A\left[\begin{array}{cccccc}{\mathbf{v}}_1& \dots & {\mathbf{v}}_k& {\mathbf{u}}_1& \dots & {\mathbf{u}}_{n-k}\end{array}\right]$$

Then since $A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ and $(A{\mathbf{v}}_i{)}^T={\lambda }_i{\mathbf{v}}_i^T$, and ${\mathbf{v}}_i^T{\mathbf{u}}_j=0$ and ${\mathbf{u}}_i^T{\mathbf{v}}_j=0$ (because they are from orthogonal subspaces): $B=\left[\begin{array}{cc}{\Lambda }_k& 0\\ 0& C\end{array}\right]$ where ${\Lambda }_k$ is a $k\times k$ diagonal matrix with ${\lambda }_1,\dots ,{\lambda }_k$ on the diagonal, and $C$ is an $(n-k)\times (n-k)$ symmetric matrix representing the transformation of vectors in $S^{\perp }$ by A.

$C$ is diagonal because:

• $C_{ij}={\mathbf{u}}_i^{T}A{\mathbf{u}}_j$. Then $C_{ji}={\mathbf{u}}_j^{T}A{\mathbf{u}}_i={\mathbf{u}}_j^T{A}^T{\mathbf{u}}_i=(A{\mathbf{u}}_j{)}^T{\mathbf{u}}_i=({\mathbf{u}}_i^{T}A{\mathbf{u}}_j{)}^T$. Since these are scalars ($1\times 1$ matrices), the transpose is equal to the original value: $C_{ji}={\mathbf{u}}_i^{T}A{\mathbf{u}}_j=C_{ij}$. Thus $C$ is symmetric.

Finding the ($k+1$)-th Eigenvector

1. Eigenvalue and Eigenvector of $C$

Since $C$ is a symmetric matrix, it has at least one real eigenvalue ${\lambda }_{k+1}$ and a corresponding eigenvector $\mathbf{y}\in {\mathbb{R}}^{n-k}$ (a consequence of $C$ being symmetric). This means:

$C\mathbf{y}={\lambda }_{k+1}\mathbf{y}.$

2. Constructing $w$

Now, construct a vector $\mathbf{w}\in {\mathbb{R}}^n$ as follows:

$\mathbf{w}=\left[\begin{array}{c}0\\ \mathbf{y}\end{array}\right]$

where $0$ is the zero vector in ${\mathbb{R}}^k$. Notice that $\mathbf{w}$ has its first $k$ components as 0 and its remaining $n-k$ components equal to the components of $\mathbf{y}.$ Importantly, since $\mathbf{y}$ is an eigenvector of $C$, it is non-zero. This means $\mathbf{w}$ is non-zero.

3. Showing w is an Eigenvector of B

Let’s compute $B\mathbf{w}$:

$B\mathbf{w}=\left[\begin{array}{cc}{\Lambda }_k& 0\\ 0& C\end{array}\right]\left[\begin{array}{c}0\\ \mathbf{y}\end{array}\right]=\left[\begin{array}{c}{\Lambda }_{k}0+0\mathbf{y}\\ 00+C\mathbf{y}\end{array}\right]=\left[\begin{array}{c}0\\ {\lambda }_{k+1}\mathbf{y}\end{array}\right]={\lambda }_{k+1}\left[\begin{array}{c}0\\ \mathbf{y}\end{array}\right]={\lambda }_{k+1}\mathbf{w}$

This demonstrates that $\mathbf{w}$ is an eigenvector of $B$ with eigenvalue ${\lambda }_{k+1}.$

4. Connecting back to $A$

Recall that $B=V_k^{T}A{V}_k$. Therefore, $V_{k}B=A{V}_k$. Now multiply both sides of the equation $B\mathbf{w}={\lambda }_{k+1}\mathbf{w}$ by $V_k$ on the left:

$V_{k}B\mathbf{w}={\lambda }_{k+1}{V}_k\mathbf{w}⟹A{V}_k\mathbf{w}={\lambda }_{k+1}{V}_k\mathbf{w}.$

Let ${\mathbf{v}}_{k+1}=V_k\mathbf{w}.$ The equation above becomes:

$A{\mathbf{v}}_{k+1}={\lambda }_{k+1}{\mathbf{v}}_{k+1}.$

This shows that ${\mathbf{v}}_{k+1}$ is an eigenvector of $A$ with eigenvalue ${\lambda }_{k+1}$!

5. Orthogonality of ${\mathbf{v}}_{k+1}$

Since $\mathbf{w}=\left[\begin{array}{c}0\\ \mathbf{y}\end{array}\right]$, and $V_k=\left[\begin{array}{cccccc}{\mathbf{v}}_1& ...& {\mathbf{v}}_k& {\mathbf{u}}_1& ...& {\mathbf{u}}_{n-k}\end{array}\right]$, we have:

${\mathbf{v}}_{k+1}=V_k\mathbf{w}={\sum }_{i=1}^{n-k}{y}_i{\mathbf{u}}_i.$

Since ${\mathbf{v}}_{k+1}$ is a linear combination of the vectors ${\mathbf{u}}_i$ which are in $S^{\perp }$, this confirms that ${\mathbf{v}}_{k+1}$ is orthogonal to all vectors in S and is therefore orthogonal to ${\mathbf{v}}_1,...{\mathbf{v}}_k.$ We can normalize ${\mathbf{v}}_{k+1}$ to obtain an orthonormal set of $k+1$ eigenvectors.

Completing the Induction

We have successfully found a ($k+1$)-th orthonormal eigenvector corresponding to a real eigenvalue. This completes the inductive step, proving that a symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ has $n$ orthonormal eigenvectors.

Conclusion

This inductive proof establishes the Spectral Theorem, demonstrating that real symmetric matrices have a complete set of orthonormal eigenvectors that form a basis for ${\mathbb{R}}^n$, and are therefore diagonalizable by an orthogonal matrix. This decomposition has significant implications for understanding the properties and behavior of symmetric matrices in various applications. The Spectral Theorem underlies many important techniques in data analysis, machine learning, physics, and engineering, highlighting its fundamental importance in linear algebra and related fields.

Consequences of the Spectral Theorem

Corollary:

• Orthogonal Diagonalization: For any symmetric matrix $A\in {\mathbb{R}}^{n\times n}$, there exists an orthogonal matrix $Q\in {\mathbb{R}}^{n\times n}$ (whose columns are eigenvectors of $A$) such that $A=Q\Lambda Q^T$, where $\Lambda$ is a diagonal matrix with the eigenvalues of $A$ on its diagonal. This is a direct consequence of the orthonormal basis property. Since the columns of Q are orthonormal, $Q^{-1}=Q^T$.

• Spectral Decomposition: Let $A$ be a real $n\times n$ symmetric matrix. Let ${\mathbf{q}}_1,\dots ,{\mathbf{q}}_n$ be an orthonormal basis of eigenvectors of $A$, and let ${\lambda }_1,\dots ,{\lambda }_n$ be the associated eigenvalues. Then $A$ can be written as a sum of rank-1 projections:

  $A={\sum }_{i=1}^n{\lambda }_i{\mathbf{q}}_i{\mathbf{q}}_i^T$

  This decomposition expresses $A$ as a weighted sum of projections onto the one-dimensional subspaces spanned by each eigenvector. This reveals how $A$ acts as a combination of scalings along orthogonal directions defined by its eigenvectors.

• Rank and Eigenvalues: The rank of a real symmetric matrix $A$ is equal to the number of non-zero eigenvalues (counting multiplicities). This follows directly from the diagonalization: the rank of $A$ is the same as the rank of $\Lambda$, which is the number of non-zero diagonal entries.

The Rayleigh Quotient

The Rayleigh quotient is a tool for analyzing the eigenvalues and eigenvectors of a symmetric matrix. It provides a way to estimate eigenvalues and characterize their extremal properties.

Definition

Let $A\in {\mathbb{R}}^{n\times n}$ be a symmetric matrix ($A=A^T$). The Rayleigh quotient $R(\mathbf{x})$ is a scalar-valued function defined for any non-zero vector $\mathbf{x}\in {\mathbb{R}}^n$ as:

$R(\mathbf{x})=\frac{{\mathbf{x}}^{T}A\mathbf{x}}{{\mathbf{x}}^T\mathbf{x}}$

The denominator ${\mathbf{x}}^T\mathbf{x}$ is the squared Euclidean norm of $\mathbf{x}$ ( $||\mathbf{x}|{|}^2$), representing the squared length of the vector. The numerator ${\mathbf{x}}^{T}A\mathbf{x}$ is a quadratic form associated with the matrix $A$.

Properties of the Rayleigh Quotient

Boundedness (for Symmetric Matrices): For a symmetric matrix $A$, the Rayleigh quotient is bounded by the minimum and maximum eigenvalues of $A$. Let ${\lambda }_{min}$ and ${\lambda }_{max}$ be the minimum and maximum eigenvalues of $A$, respectively. Then for any non-zero $\mathbf{x}$:

${\lambda }_{min}\le R(\mathbf{x})\le {\lambda }_{max}$

This is a crucial property. It tells us that the range of values the Rayleigh quotient can take is restricted by the eigenvalues of the matrix. We might prove this in the next lecture…

Continue here: 27 Positive (Semi)Definite Matrices, Gram Matrices, SVD