The Spectral Theorem

Overview & Motivation

Every machine learning algorithm that touches a covariance matrix, a kernel matrix, a graph Laplacian, or a Hessian is secretly relying on a single theorem: the Spectral Theorem.

The Spectral Theorem says that every real symmetric matrix $A \in \mathbb{R}^{n \times n}$ can be diagonalized by an orthogonal matrix:

$A = Q \Lambda Q^T$

where $Q$ is orthogonal ($Q^T Q = I$) and $\Lambda = \text{diag}(\lambda_1, \ldots, \lambda_n)$ is the diagonal matrix of real eigenvalues. This is not just a convenience — it’s a structural guarantee that underpins:

• PCA: the sample covariance matrix $\hat{\Sigma} = \frac{1}{n-1} X^T X$ is symmetric, so its eigenvectors are orthogonal principal directions.
• Spectral clustering: the graph Laplacian $L = D - W$ is symmetric positive semidefinite, so its smallest eigenvectors encode cluster structure.
• Optimization: the Hessian $\nabla^2 f$ is symmetric, and its eigenvalues determine convexity.
• Kernel methods: kernel matrices $K_{ij} = k(x_i, x_j)$ are symmetric PSD by construction.
• The Sheaf Laplacian: from the Sheaf Theory topic on the Topology & TDA track, $L_\mathcal{F} = \delta_0^T \delta_0$ is symmetric PSD, and the Spectral Theorem is what makes its eigendecomposition well-defined and interpretable.

This topic develops the Spectral Theorem from first principles, proves it, implements it, and applies it to spectral clustering — building the algebraic foundation that the rest of the Linear Algebra track depends on.

What We Cover

1. Eigenvalues & Eigenvectors — characteristic polynomials, eigenspaces, diagonalization.
2. Symmetric Matrices & Orthogonality — real eigenvalues, orthogonal eigenvectors, the key lemmas.
3. The Spectral Theorem — the full statement and proof, geometric interpretation.
4. The Rayleigh Quotient — variational characterization of eigenvalues, the Courant–Fischer min-max theorem.
5. Quadratic Forms & Definiteness — positive definiteness, Sylvester’s criterion.
6. Spectral Decomposition in Practice — power iteration, the QR algorithm.
7. Application: Spectral Clustering — from similarity graph to clusters via the graph Laplacian’s eigenvectors.
8. Application: PCA Preview — the Spectral Theorem applied to the covariance matrix.

---

Eigenvalues & Eigenvectors

The Eigenvalue Problem

Given a square matrix $A \in \mathbb{R}^{n \times n}$, a scalar $\lambda \in \mathbb{C}$ is an eigenvalue of $A$ if there exists a nonzero vector $v \in \mathbb{C}^n$ such that:

$Av = \lambda v$

The vector $v$ is the eigenvector corresponding to $\lambda$. Geometrically, $A$ acts on $v$ by simply scaling it — $v$ is a direction that $A$ preserves.

The Characteristic Polynomial

Rearranging $Av = \lambda v$ gives $(A - \lambda I)v = 0$, which has a nonzero solution if and only if:

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

Eigenspaces and Multiplicity

When $g(\lambda) < a(\lambda)$ for some $\lambda$, the matrix is defective and cannot be diagonalized. A central result of this topic is that symmetric matrices are never defective.

---

Symmetric Matrices & Orthogonality

A matrix $A \in \mathbb{R}^{n \times n}$ is symmetric if $A = A^T$, meaning $a_{ij} = a_{ji}$ for all $i, j$. Symmetric matrices appear everywhere in ML:

• Covariance matrices: $\hat{\Sigma} = \frac{1}{n-1} X^T X$
• Graph Laplacians: $L = D - W$
• Hessians: $\nabla^2 f(x)$ (by equality of mixed partials)
• Kernel matrices: $K_{ij} = k(x_i, x_j)$
• Gram matrices: $G_{ij} = \langle v_i, v_j \rangle$

The three lemmas below are the building blocks of the Spectral Theorem.

Real Eigenvalues

Orthogonal Eigenvectors

Invariant Complements

This lemma is the engine of the inductive proof: once we find one eigenvector, we can restrict $A$ to its orthogonal complement and repeat.

---

The Spectral Theorem

Statement

The second form — the spectral decomposition — writes $A$ as a sum of rank-1 projection matrices $q_i q_i^T$, each scaled by its eigenvalue. This is the form that directly gives PCA its interpretation.

Proof

Geometric Interpretation

The Spectral Theorem says that every symmetric linear transformation is, in the right coordinate system, just a stretch along orthogonal axes. The eigenvectors $q_i$ define the axes, and the eigenvalues $\lambda_i$ define the stretch factors.

This is why:

• Covariance matrices define ellipsoidal level sets (axes = principal components).
• Graph Laplacians have smooth eigenvectors that partition the graph.
• Hessians at critical points tell you whether you’re at a min, max, or saddle — by the signs of the eigenvalues along orthogonal curvature directions.

Try it yourself — drag the sliders to change the matrix entries and watch the eigenvectors and ellipse update in real time:

Matrix A

[3.000,1.000]

[1.000,2.000]

Eigenvalues

λ₁ = 1.382|λ₂ = 3.618

Eigenvectors

q₁ = [-0.526, 0.851]

q₂ = [0.851, 0.526]

Positive Definite

A = QΛQᵀ

a (top-left): 3.0

b (off-diagonal): 1.0

c (bottom-right): 2.0

The Hermitian Extension

The Spectral Theorem extends to Hermitian (complex self-adjoint) matrices. A matrix $A \in \mathbb{C}^{n \times n}$ with $A = A^* = \bar{A}^T$ has:

$A = U \Lambda U^*$

where $U$ is unitary ($U^* U = I$) and $\Lambda$ is real diagonal. The proof is identical, replacing transposes with conjugate transposes. Every real symmetric matrix is Hermitian, so the real version is a special case.

Numerical Verification

We can verify the Spectral Theorem in code. Here np.linalg.eigh is the dedicated function for symmetric/Hermitian matrices — it guarantees real eigenvalues and orthonormal eigenvectors:

import numpy as np

A = np.array([
    [5, 2, 0, 1],
    [2, 4, 1, 0],
    [0, 1, 3, 2],
    [1, 0, 2, 6]
], dtype=float)

# eigh is specifically for symmetric matrices
eigenvalues, Q = np.linalg.eigh(A)
Lambda = np.diag(eigenvalues)

# Verify A = Q Lambda Q^T
print(f"||A - Q Lambda Q^T||_F = {np.linalg.norm(A - Q @ Lambda @ Q.T):.2e}")
# Output: 1.01e-14

# Spectral decomposition: A = sum lambda_i q_i q_i^T
A_spectral = sum(eigenvalues[i] * np.outer(Q[:, i], Q[:, i]) for i in range(A.shape[0]))
print(f"||A - sum lambda_i q_i q_i^T||_F = {np.linalg.norm(A - A_spectral):.2e}")
# Output: 1.03e-14

---

The Rayleigh Quotient

Definition

The Rayleigh quotient is the bridge between eigenvalues and optimization. Its value tells you “how much $A$ stretches in the direction $x$” — and the eigenvectors are the directions where this stretch is extremal.

Extremal Characterization

The interactive visualization below shows the Rayleigh quotient $R(\theta) = x^T A x$ as $x$ traces the unit circle. The polar plot reveals how the quadratic form bulges in the eigenvector directions, and the Cartesian plot shows the extrema at $\lambda_1$ and $\lambda_2$:

A = [[3.0, 1.0], [1.0, 2.0]] — 1.38 ≤ R(x) ≤ 3.62

a = 3.0

b = 1.0

c = 2.0

The Courant–Fischer Min-Max Theorem

This characterizes the $k$-th eigenvalue as a min-max over subspaces. It is the theoretical foundation of PCA: the $k$-th principal component maximizes variance subject to orthogonality with the first $k-1$ components — exactly the Courant–Fischer characterization applied to the covariance matrix.

---

Quadratic Forms & Definiteness

Quadratic Forms

Why definiteness matters for ML: A covariance matrix is always PSD ($x^T \hat{\Sigma} x = \text{Var}(\text{linear combination}) \geq 0$). A graph Laplacian is PSD. A kernel matrix is PSD by Mercer’s theorem. The Hessian at a local minimum is PSD.

Sylvester’s Criterion

This gives a determinant-based test that avoids computing eigenvalues — useful for theoretical arguments and small matrices.

---

Spectral Decomposition in Practice

eig vs. eigh

Two functions for eigendecomposition:

Function	For	Algorithm	Guarantees
np.linalg.eig(A)	General square matrices	QR iteration (LAPACK dgeev)	May return complex values
np.linalg.eigh(A)	Symmetric/Hermitian	Divide-and-conquer (LAPACK dsyevd)	Real eigenvalues; orthonormal eigenvectors

Always use eigh for symmetric matrices. It is faster ($O(n^3/3)$ vs. $O(n^3)$), more numerically stable, and guarantees the Spectral Theorem’s output format.

Power Iteration

The power method is the simplest eigenvalue algorithm: repeatedly multiply by $A$ and normalize. This converges to the dominant eigenvector at a rate proportional to $|\lambda_{n-1}/\lambda_n|$ — the ratio of the two largest eigenvalues.

def power_iteration(A, max_iter=100, tol=1e-10):
    """Power iteration for the dominant eigenpair of a symmetric matrix."""
    n = A.shape[0]
    x = np.random.randn(n)
    x = x / np.linalg.norm(x)

    lam = 0.0
    for _ in range(max_iter):
        y = A @ x
        lam_new = x @ y  # Rayleigh quotient
        x_new = y / np.linalg.norm(y)

        if abs(lam_new - lam) < tol:
            lam = lam_new
            x = x_new
            break

        lam = lam_new
        x = x_new

    return lam, x

The QR Algorithm

The industry-standard eigenvalue algorithm is the QR algorithm: repeatedly factor $A_k = Q_k R_k$ and form $A_{k+1} = R_k Q_k$. This is a similarity transformation ($A_{k+1} = Q_k^T A_k Q_k$), so eigenvalues are preserved — but $A_k$ converges to diagonal form.

def qr_algorithm(A, max_iter=200, tol=1e-12):
    """Basic QR algorithm (without shifts) for a symmetric matrix."""
    Ak = A.copy()

    for k in range(max_iter):
        Q, R = np.linalg.qr(Ak)
        Ak = R @ Q  # similarity transform: same eigenvalues

        off_diag = np.linalg.norm(Ak - np.diag(np.diag(Ak)))
        if off_diag < tol:
            break

    return np.sort(np.diag(Ak))

With shifts, deflation, and Householder reductions, the production QR algorithm achieves $O(n^3)$ complexity. The basic version above converges at a rate determined by the eigenvalue ratios — similar to power iteration, but for all eigenvalues simultaneously.

---

Application: Spectral Clustering

Spectral clustering is the flagship application of the Spectral Theorem in unsupervised learning. The idea: transform data using the eigenvectors of a graph Laplacian, then cluster in the transformed space.

Why Spectral Clustering?

Standard k-means clustering fails on non-convex clusters (e.g., nested circles or interleaving moons). Spectral clustering handles these by:

1. Building a similarity graph from the data.
2. Computing the graph Laplacian (a symmetric PSD matrix).
3. Using the Spectral Theorem to find its smallest eigenvectors.
4. Clustering in the eigenvector embedding space.

The Graph Laplacian

Given a weighted adjacency matrix $W$ (with $W_{ij} = \exp(-\|x_i - x_j\|^2 / (2\sigma^2))$ for Gaussian similarity), the unnormalized graph Laplacian is:

$L = D - W$

where $D = \text{diag}(d_1, \ldots, d_n)$ with $d_i = \sum_j W_{ij}$.

Key properties (all from the Spectral Theorem):

• $L$ is symmetric (since $W$ is symmetric).
• $L$ is PSD: $x^T L x = \frac{1}{2} \sum_{i,j} W_{ij}(x_i - x_j)^2 \geq 0$.
• The number of zero eigenvalues of $L$ equals the number of connected components.
• The eigenvectors for the smallest eigenvalues encode cluster structure.

The Algorithm

1. Build the similarity matrix $W$ (e.g., Gaussian kernel with bandwidth $\sigma$).
2. Compute $L = D - W$.
3. Compute the $k$ smallest eigenvectors of $L$: $v_1, \ldots, v_k$.
4. Form the matrix $U \in \mathbb{R}^{n \times k}$ with columns $v_1, \ldots, v_k$.
5. Run k-means on the rows of $U$.

Interactive Demo

Step through the spectral clustering pipeline on a two-moons dataset. Watch how the Laplacian’s eigenvectors transform a non-convex clustering problem into a linearly separable one:

DatasetTwo MoonsTwo CirclesThree BlobsSpiralClusters k

234

Graph

k-NNε-ball

Noise 1.0

Implementation

from scipy.spatial.distance import pdist, squareform
from sklearn.cluster import KMeans

def spectral_clustering(X, k, sigma=1.0):
    """Spectral clustering using the unnormalized graph Laplacian."""
    # Step 1: Similarity matrix (Gaussian kernel)
    dists = squareform(pdist(X, 'sqeuclidean'))
    W = np.exp(-dists / (2 * sigma**2))
    np.fill_diagonal(W, 0)

    # Step 2: Graph Laplacian
    D = np.diag(W.sum(axis=1))
    L = D - W

    # Step 3: Smallest k eigenvectors (skip constant eigenvector)
    eigenvalues, eigenvectors = np.linalg.eigh(L)
    U = eigenvectors[:, 1:k+1]

    # Step 4: Normalize rows
    row_norms = np.linalg.norm(U, axis=1, keepdims=True)
    U_norm = U / np.where(row_norms < 1e-10, 1, row_norms)

    # Step 5: K-means on the embedding
    labels = KMeans(n_clusters=k, random_state=42, n_init=10).fit_predict(U_norm)
    return labels

The graph Laplacian is symmetric PSD, so the Spectral Theorem guarantees real eigenvalues, orthogonal eigenvectors, and a well-defined spectral gap — exactly the properties that make spectral clustering work.

---

Application: PCA Preview

Principal Component Analysis is the Spectral Theorem applied to the sample covariance matrix. The full development lives on the PCA & Low-Rank Approximation topic page — here we establish the connection.

The Covariance Matrix Is Symmetric PSD

Given centered data $X \in \mathbb{R}^{n \times d}$ (rows = observations, columns = features), the sample covariance matrix is:

$\hat{\Sigma} = \frac{1}{n-1} X^T X$

This is symmetric ($\hat{\Sigma}^T = \hat{\Sigma}$) and PSD ($v^T \hat{\Sigma} v = \frac{1}{n-1} \|Xv\|^2 \geq 0$).

PCA as the Spectral Theorem

By the Spectral Theorem, $\hat{\Sigma} = Q \Lambda Q^T$ with $Q$ orthogonal and $\Lambda$ diagonal (non-negative). The columns of $Q$ are the principal components — orthogonal directions of maximum variance. The eigenvalues are the variances along these directions.

# PCA via eigendecomposition of the covariance matrix
X_centered = X - X.mean(axis=0)
Sigma_hat = (X_centered.T @ X_centered) / (n - 1)

eigenvalues, Q = np.linalg.eigh(Sigma_hat)
# eigh returns ascending order; PCA wants descending
idx = np.argsort(eigenvalues)[::-1]
eigenvalues, Q = eigenvalues[idx], Q[:, idx]

# Project onto first k principal components
X_pca = X_centered @ Q[:, :k]

The Courant–Fischer theorem (Theorem 2) guarantees this is the optimal rank-$k$ variance-preserving projection.

The SVD Connection

PCA is also connected to the Singular Value Decomposition (the next topic in this track). If $X = U \Sigma V^T$ is the SVD, then $\hat{\Sigma} = \frac{1}{n-1} V \Sigma^2 V^T$, so the right singular vectors of $X$ are the eigenvectors of $\hat{\Sigma}$. The SVD generalizes the Spectral Theorem to rectangular matrices — the subject of the next topic.

---

Connections & Further Reading

The Spectral Theorem is the algebraic foundation that supports the entire Linear Algebra track and connects back to the Topology & TDA track.

Topic	Connection
Singular Value Decomposition	The SVD generalizes the Spectral Theorem to rectangular matrices. For symmetric $A$, the SVD reduces to the spectral decomposition.
PCA & Low-Rank Approximation	PCA is the Spectral Theorem applied to $\hat{\Sigma}$. The Eckart–Young theorem follows from the spectral decomposition.
Tensor Decompositions	The CP decomposition generalizes eigendecomposition to tensors. Symmetric tensor decomposition is the higher-order analog of the Spectral Theorem.
Sheaf Theory	The Sheaf Laplacian $L_\mathcal{F} = \delta_0^T \delta_0$ is symmetric PSD. The Spectral Theorem guarantees its eigendecomposition. $\ker(L_\mathcal{F}) = H^0$ is read from the zero eigenvalues.
Convex Analysis	The second-order convexity condition: $\nabla^2 f \succeq 0$ is verified through the eigendecomposition guaranteed by the Spectral Theorem. The PSD cone $\mathbb{S}^n_+$ is a fundamental convex set.
Graph Laplacians & Spectrum	The graph Laplacian $L = D - A$ is a real symmetric matrix. The Spectral Theorem guarantees its complete orthonormal eigenbasis — the foundation of spectral graph theory, spectral clustering, and graph neural networks.
Categories & Functors	The category Vec of finite-dimensional vector spaces and linear maps is the primary running example in category theory. The Spectral Theorem guarantees that symmetric endomorphisms in Vec have complete eigenbases. $\mathrm{Hom}(\mathbb{R}^m, \mathbb{R}^n) = \mathrm{Mat}(n \times m)$ illustrates the Hom functor concretely.

The Linear Algebra Track

The Spectral Theorem is the root of the track: everything that follows either extends it (SVD → rectangular matrices, tensors → higher order) or applies it (PCA → optimal projection).

Spectral Theorem (this topic)
    ├── Singular Value Decomposition
    │       └── PCA & Low-Rank Approximation
    └── Tensor Decompositions