Spectral theorem, Rayleigh quotient, Courant–Fischer and Weyl

Before this lesson: lesson 05 (eigenvalues, diagonalization) and lesson 04 ($Q^\top Q = I$); orthogonal projections are in lesson 03. Time: about 90 minutes, plus the notebook.

---

Why this matters #

Symmetric matrices are the most common matrices in ML: covariance matrices, Hessians, kernel (Gram) matrices, graph Laplacians, $A^\top A$. For them, the problems of lesson 05 cannot happen: eigenvalues are real, eigenvectors are orthogonal, and there are always enough of them. The Rayleigh quotient turns eigenvalues into optimization. PCA's first direction, the sharpness of a loss, the Fiedler vector of spectral clustering and the ground-state energy of a quantum system are all a max or a min of a Rayleigh quotient. Courant–Fischer does the same for every eigenvalue. Its corollary, Weyl's inequality, says that symmetric eigenvalues move at most as much as the noise you add.

1. Predict first #

2. The picture #

Start with a diagonal matrix. Take $S = \operatorname{diag}(3, 1)$ and a unit vector $x = (\cos\theta, \sin\theta)$. Then

This is a weighted average of the eigenvalues 3 and 1. The weights are $\cos^2\theta$ and $\sin^2\theta$; they are not negative and they sum to 1. So the value lies between 1 and 3. The max is on the $e_1$ axis, the min on the $e_2$ axis. $S$ maps the unit circle to an ellipse with half-axes 3 and 1.

A general symmetric matrix looks the same in the right axes. $S = Q\Lambda Q^\top$ means three steps: change to the orthonormal eigen-axes ($Q^\top$), scale each axis ($\Lambda$), change back ($Q$). There is no shear. So the axes of the ellipse are the eigenvectors, and they are perpendicular. In those axes, every value $x^\top S x$ of a unit vector is again a weighted average of eigenvalues. Almost every result of this lesson follows from this one fact.

Interactive figure: loading…

3. Definitions and main results #

Spectral theorem #

Theorem. Let $S \in \mathbb{R}^{n\times n}$ be symmetric: $S = S^\top$. Then

where $Q$ is orthogonal ($Q^\top Q = I$; its columns $q_i$ are orthonormal eigenvectors) and $\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ is real. Conversely, $(Q\Lambda Q^\top)^\top = Q\Lambda Q^\top$. So over $\mathbb{R}$: a matrix is orthogonally diagonalizable (diagonalizable with an orthogonal $Q$) exactly when it is symmetric.

The proof has three steps: (1) the eigenvalues are real, (2) eigenvectors for different eigenvalues are orthogonal, (3) there are always $n$ orthonormal eigenvectors, even when an eigenvalue repeats.

Step 1: the eigenvalues are real

First the $2\times2$ case. For $S = \begin{pmatrix} a & b \\ b & c \end{pmatrix}$ the characteristic polynomial is $p(\lambda) = \lambda^2 - (a + c)\lambda + (ac - b^2)$. Its discriminant is

A sum of squares is never negative, so both roots are real. The discriminant is 0 only when $a = c$ and $b = 0$, that is, when $S = aI$. Compare with the rotation $\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ (not symmetric): its polynomial is $\lambda^2 + 1$, with discriminant $-4$ and complex roots $\pm i$.

Now any size. A real matrix can have complex eigenvalues (a rotation does). So we cannot assume at the start that $\lambda$ is real. We allow a complex eigenpair and then show that $\lambda$ is real. Write $\bar x$ for the complex conjugate.

1. Let $Sx = \lambda x$ with $x \in \mathbb{C}^n$, $x \ne 0$.
2. Multiply on the left by $\bar x^\top$: $\ \bar x^\top S x = \lambda\, \bar x^\top x$.
3. $\bar x^\top x = \sum_i |x_i|^2$ is real and positive.
4. $\bar x^\top S x$ is real. Its conjugate is $x^\top S \bar x$ ($S$ is real). This is a $1\times1$ matrix, so it equals its transpose $\bar x^\top S^\top x = \bar x^\top S x$ (here $S^\top = S$ is used).
5. So $\lambda = \bar x^\top S x / \bar x^\top x$ is a real number divided by a positive number: real.
6. Then $S - \lambda I$ is a real singular matrix, so it has a real nonzero null vector: a real eigenvector.

Step 2: eigenvectors of different eigenvalues are orthogonal

Let $Sx = \lambda x$ and $Sy = \mu y$ with $\lambda \ne \mu$. Compute $y^\top S x$ in two ways:

So $(\lambda - \mu)\, y^\top x = 0$, and as $\lambda \ne \mu$, $y^\top x = 0$.

Step 3: there are always enough eigenvectors

Step 2 does not cover repeated eigenvalues. In lesson 05, $\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ has the eigenvalue 0 twice but only one eigenvector direction. A symmetric matrix never has this problem. The key fact is:

Key fact. If $Sq_1 = \lambda_1 q_1$, then $S$ maps the subspace $q_1^\perp$ (all vectors perpendicular to $q_1$) into itself. Such a subspace is called invariant.

Why. Let $x \perp q_1$. Then $q_1^\top (Sx) = (Sq_1)^\top x = \lambda_1\, q_1^\top x = 0$. So $Sx \perp q_1$ too. The first equality uses $S^\top = S$.

Interactive figure: loading…

So, inside the plane $q_1^\perp$, $S$ is again a symmetric map, now on a space with one dimension less. Repeat the argument there. For $n = 3$ the story is $3 \to 2 \to 1$:

1. Find one real unit eigenvector $q_1$ (step 1 says it exists).
2. The plane $q_1^\perp$ is mapped into itself. In an orthonormal basis $u_1, u_2$ of this plane, $S$ acts like the $2\times2$ symmetric matrix $B = U^\top S U$, with $U = [u_1\ u_2]$.
3. $B$ has a real unit eigenvector $c$ (step 1 again, now for size 2). Then $q_2 = Uc$ is an eigenvector of $S$ inside the plane.
4. The line in the plane perpendicular to $q_2$ is mapped into itself. Any unit vector $q_3$ on it is the third eigenvector. Now $q_1, q_2, q_3$ are orthonormal.

Example. $S = \begin{pmatrix} 2 & 1 & 0 \\ 1 & 2 & 0 \\ 0 & 0 & 5 \end{pmatrix}$. Here $Se_3 = 5e_3$, so $q_1 = e_3$ and $\lambda_1 = 5$. The plane $q_1^\perp$ is the $xy$-plane, with $U = [e_1\ e_2]$ and $B = U^\top S U = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$. Its eigenvectors are $(1, 1)/\sqrt2$ (eigenvalue 3) and $(1, -1)/\sqrt2$ (eigenvalue 1). So $q_2 = (1, 1, 0)/\sqrt2$ and $q_3 = (1, -1, 0)/\sqrt2$, and $S = 5q_1q_1^\top + 3q_2q_2^\top + 1q_3q_3^\top$.

Step 3 for every size (induction)

Induction on $n$; for $n = 1$ there is nothing to prove.

1. Take a real unit eigenvector $q_1$, $Sq_1 = \lambda_1 q_1$ (step 1). By the key fact, $W = q_1^\perp$ is invariant.
2. Let the columns of $U \in \mathbb{R}^{n\times(n-1)}$ be an orthonormal basis of $W$. The columns of $SU$ lie in $W$, and $UU^\top$ is the orthogonal projector onto $W$, so $SU = UU^\top SU = U(U^\top S U)$.
3. $B = U^\top S U$ is symmetric of size $n - 1$. By induction, $B = P\Lambda' P^\top$ with $P$ orthogonal.
4. Then $S(UP) = UBP = (UP)\Lambda'$: the $n - 1$ columns of $UP$ are orthonormal eigenvectors in $W$ ($(UP)^\top UP = P^\top P = I$).
5. With $q_1$ they form the orthogonal matrix $Q = [q_1,\ UP]$, and $SQ = Q\Lambda$. $\blacksquare$

So a symmetric matrix is never defective: for every eigenvalue, the geometric multiplicity equals the algebraic multiplicity. Inside an eigenspace of dimension $> 1$, any orthonormal basis works, so $Q$ is not unique.

The spectral decomposition: a sum of projectors

$S = Q\Lambda Q^\top$ can be read column by column (the outer-product view of lesson 01):

In words: project $x$ onto each eigenvector, scale each piece by its eigenvalue, add up. Each $P_i = q_i q_i^\top$ is the orthogonal projector onto the line of $q_i$ (lesson 03). The projectors satisfy $P_i^2 = P_i$, $P_iP_j = 0$ for $i \ne j$, and $\sum_i P_i = I$.

Check with numbers. $S = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$, with $q_1 = (1, 1)/\sqrt2$ for $\lambda_1 = 3$ and $q_2 = (1, -1)/\sqrt2$ for $\lambda_2 = 1$:

Also $P_1 + P_2 = I$ and $P_1P_2 = 0$, as promised.

Rayleigh quotient #

For symmetric $S$ and $x \ne 0$, the Rayleigh quotient is

It depends only on the direction of $x$: $R(cx) = R(x)$ for every $c \ne 0$. If $Sq = \lambda q$, then $R(q) = \lambda$. From now on the eigenvalues are sorted: $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$.

Theorem (Rayleigh). $\lambda_n \le R(x) \le \lambda_1$ for all $x \ne 0$. The max $\lambda_1$ is reached exactly at the nonzero vectors of the $\lambda_1$-eigenspace, and the min $\lambda_n$ exactly at those of the $\lambda_n$-eigenspace.

Proof.

1. Put $y = Q^\top x$ (the coordinates of $x$ in the eigenbasis). Then $x^\top x = y^\top y$ and $x^\top S x = y^\top \Lambda y$, so $R(x) = \sum_i \lambda_i y_i^2 / \sum_i y_i^2$.
2. This is a weighted average of the $\lambda_i$, with weights $w_i = y_i^2/\|y\|^2 \ge 0$ that sum to 1. So $\lambda_n \le R(x) \le \lambda_1$.
3. $R(x) = \lambda_1$ exactly when all the weight sits on indices with $\lambda_i = \lambda_1$, that is, when $x$ is in the $\lambda_1$-eigenspace. The same holds for $\lambda_n$. $\blacksquare$

When $\lambda_{\max}$ is repeated, the maximizers of $R$ are all nonzero vectors of the whole $\lambda_{\max}$-eigenspace, not one eigenvector direction (the same holds for $\lambda_{\min}$).

Theorem (critical points). The gradient of $R$ is

So the critical points of $R$ (the points with $\nabla R = 0$) are exactly the eigenvectors. An eigenvector $q$ with $\lambda_n < \lambda < \lambda_1$ is a saddle point: $R$ goes up in one direction and down in another.

Proof.

1. Quotient rule, with $\nabla(x^\top S x) = 2Sx$ and $\nabla(x^\top x) = 2x$:

2. $\nabla R(x) = 0 \iff Sx = R(x)\,x \iff$ $x$ is an eigenvector (with eigenvalue $R(x)$).
3. Saddle. Let $q, q_1, q_n$ be unit eigenvectors for $\lambda, \lambda_1, \lambda_n$; they are orthogonal. For $t \ne 0$: $R(q + tq_1) = (\lambda + t^2\lambda_1)/(1 + t^2) > \lambda$ and $R(q + tq_n) = (\lambda + t^2\lambda_n)/(1 + t^2) < \lambda$. $\blacksquare$

Interactive figure: loading…

More precisely, $R(q_k\cos t + q_i \sin t) = \lambda_k + (\lambda_i - \lambda_k)\sin^2 t$ for orthonormal eigenvectors $q_k, q_i$. So from $q_k$, $R$ goes up toward every eigenvector with a larger eigenvalue and down toward every one with a smaller eigenvalue.

The eigenvalue error is quadratic. Let $q$ be a unit eigenvector ($Sq = \lambda q$) and $d$ a unit vector with $d \perp q$. Then

because the cross term $d^\top S q = \lambda\, d^\top q$ is 0. So an eigenvector error of size $\varepsilon$ gives an eigenvalue error of size $\varepsilon^2$. This is why power iteration on a symmetric matrix gets the eigenvalue at the rate $|\lambda_2/\lambda_1|^{2k}$: twice as many correct digits as the vector.

Restriction to a subspace. Let $V$ have orthonormal columns that span a subspace $U$. For $x = Vc$, $R(x) = c^\top (V^\top S V) c / c^\top c$. So the min and the max of $R$ over $U$ are the smallest and the largest eigenvalues of the small symmetric matrix $V^\top S V$.

The generalized symmetric eigenproblem

In LDA, CCA and the vibration of structures, the problem is $Sx = \lambda Bx$ with $S$ symmetric and $B$ symmetric positive definite (lesson 07). The generalized Rayleigh quotient $x^\top S x / x^\top B x$ plays the role of $R$.

1. Factor $B = LL^\top$ (Cholesky, lesson 07) and put $y = L^\top x$. Then $Sx = \lambda Bx$ becomes $(L^{-1} S L^{-\top})\,y = \lambda y$, an ordinary symmetric eigenproblem.
2. So the eigenvalues are real, and the eigenvectors can be chosen $B$-orthonormal: $x_i^\top B x_j = 0$ for $i \ne j$ and $x_i^\top B x_i = 1$.
3. $\max_{x \ne 0} x^\top S x / x^\top B x = \lambda_{\max}$, the largest generalized eigenvalue.

Fisher's LDA maximizes $w^\top S_B w / w^\top S_W w$ (between-class over within-class scatter): a generalized Rayleigh quotient. In SciPy: scipy.linalg.eigh(S, B).

Courant–Fischer #

The Rayleigh theorem gives $\lambda_1$ and $\lambda_n$. What about the eigenvalues in the middle?

First in words, for a $3\times3$ matrix. Take any plane $U$ through 0. On this plane, $R$ has a smallest value: the weakest direction of $U$. Different planes have different weakest values. Courant–Fischer says: $\lambda_2$ is the best worst value of $R$ over all planes,

Two facts give this.

• The plane $\operatorname{span}(q_1, q_2)$ reaches $\lambda_2$. On it, $R$ is a weighted average of $\lambda_1$ and $\lambda_2$, so $R \ge \lambda_2$, with equality at $q_2$.
• No plane does better. Let $W = \operatorname{span}(q_2, q_3)$. On $W$, $R$ is a weighted average of $\lambda_2$ and $\lambda_3$, so $R \le \lambda_2$. Two planes through 0 in $\mathbb{R}^3$ always share at least a line. Take $x \ne 0$ on that line: $\min_U R \le R(x) \le \lambda_2$.

Interactive figure: loading…

Why two subspaces must meet. For subspaces $U, W$ of $\mathbb{R}^n$, the dimension formula $\dim(U \cap W) = \dim U + \dim W - \dim(U + W)$ and $\dim(U + W) \le n$ give

If $\dim U + \dim W > n$, they share a nonzero vector. For two planes in $\mathbb{R}^3$: $2 + 2 - 3 = 1$.

Theorem (Courant–Fischer). For symmetric $S$ with $\lambda_1 \ge \dots \ge \lambda_n$ and $k = 1, \dots, n$:

The max–min is reached at $U = \operatorname{span}(q_1, \dots, q_k)$, the min–max at $U = \operatorname{span}(q_k, \dots, q_n)$. In words: every $k$-dimensional subspace has a weakest direction, and $\lambda_k$ is the best possible weakest value. For $k = 1$ and $k = n$ this is the Rayleigh theorem.

Proof of the max–min form

1. ($\ge$) Take $U_* = \operatorname{span}(q_1, \dots, q_k)$. For $x \in U_*$, $R(x)$ is a weighted average of $\lambda_1, \dots, \lambda_k$, which are all $\ge \lambda_k$, and $R(q_k) = \lambda_k$. So $\min_{U_*} R = \lambda_k$.
2. ($\le$) Let $U$ be any $k$-dimensional subspace, and $W = \operatorname{span}(q_k, \dots, q_n)$, of dimension $n - k + 1$. Then $\dim(U \cap W) \ge k + (n - k + 1) - n = 1$, so some $x \ne 0$ lies in both. As $x \in W$, $R(x)$ is a weighted average of $\lambda_k, \dots, \lambda_n$, so $R(x) \le \lambda_k$. Hence $\min_U R \le R(x) \le \lambda_k$ for every $U$.
3. Steps 1 and 2 give equality. $\blacksquare$

The min–max form, and Cauchy interlacing

The min–max form follows from the max–min form applied to $-S$.

1. The eigenvalues of $-S$ in decreasing order are $-\lambda_n \ge -\lambda_{n-1} \ge \dots \ge -\lambda_1$. So the $j$-th largest eigenvalue of $-S$ is $-\lambda_{n-j+1}$.
2. The Rayleigh quotient of $-S$ is $-R(x)$. The max–min form for $-S$ with $j = n - k + 1$ gives $-\lambda_k = \max_{\dim U = n-k+1} \min_{x \in U} \big(-R(x)\big)$.
3. $\min(-R) = -\max R$ and $\max(-f) = -\min f$, so $-\lambda_k = -\min_{\dim U = n-k+1} \max_{x \in U} R(x)$. Multiply by $-1$. $\blacksquare$

A corollary: Cauchy interlacing. Let $V \in \mathbb{R}^{n\times m}$ have orthonormal columns and $B = V^\top S V$ (for example, a principal $m\times m$ submatrix of $S$). Then $\lambda_k(S) \ge \lambda_k(B) \ge \lambda_{k+n-m}(S)$ for $k = 1, \dots, m$. The first inequality follows from the max–min form, because the subspaces $\{Vc\}$ are only some of the $k$-dimensional subspaces; the second from the min–max form in the same way.

Weyl's inequality #

Theorem (Weyl). Let $A, E \in \mathbb{R}^{n\times n}$ be symmetric, with the eigenvalues of $A$, $E$ and $A + E$ each sorted in decreasing order. For every $k$:

and therefore

Here $\|E\|_2$ is the spectral norm, the largest stretch $\max_{x\ne0}\|Ex\|/\|x\|$. For symmetric $E$ it equals $\max_i |\lambda_i(E)|$.

Proof.

1. For every $x \ne 0$: $R_{A+E}(x) = R_A(x) + R_E(x)$, and $\lambda_n(E) \le R_E(x) \le \lambda_1(E)$ (Rayleigh theorem for $E$).
2. Fix a $k$-dimensional $U$ and take the min over $x \in U$ of each part: $\min_U R_A + \lambda_n(E) \le \min_U R_{A+E} \le \min_U R_A + \lambda_1(E)$.
3. This holds for every $U$, so it also holds after the max over all $k$-dimensional $U$ (if $f(U) \le g(U)$ for every $U$, then $\max f \le \max g$). Courant–Fischer turns the three max–mins into $\lambda_k(A) + \lambda_n(E)$, $\lambda_k(A + E)$ and $\lambda_k(A) + \lambda_1(E)$.
4. $-\|E\|_2 \le \lambda_n(E)$ and $\lambda_1(E) \le \|E\|_2$ give the bound with absolute values. $\blacksquare$

Four facts about the bound:

• It is tight: $E = \varepsilon I$ moves every eigenvalue by exactly $\varepsilon$.
• It needs symmetry: $\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 \\ \varepsilon & 0 \end{pmatrix}$ has eigenvalues $\pm\sqrt{\varepsilon}$ (the characteristic polynomial is $\lambda^2 - \varepsilon$), but $\|E\|_2 = \varepsilon$. For $\varepsilon = 10^{-6}$ the eigenvalues move by $10^{-3}$, a thousand times $\|E\|_2$.
• It says nothing about eigenvectors. With a small eigengap they can turn far (Davis–Kahan, lesson 17).
• Singular values: $|\sigma_k(A + E) - \sigma_k(A)| \le \|E\|_2$ holds for any matrices of the same shape, even rectangular. Lesson 17 proves it from this theorem.

Interactive figure: loading…

Answers to section 1. (1) The eigenvalues are 3, with $q_1 = (1, 1)/\sqrt2$, and 1, with $q_2 = (1, -1)/\sqrt2$. The max of $x^\top Sx$ over unit $x$ is 3, at $\pm q_1$; the min is 1, at $\pm q_2$. (2) Symmetric: no. Weyl allows a move of at most $0.01$. Not symmetric: yes. $A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ plus $E = \begin{pmatrix} 0 & 0 \\ 0.01 & 0 \end{pmatrix}$ has eigenvalues $\pm 0.1$.

4. Worked example #

(a) Spectral decomposition. $S = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$.

1. $p(\lambda) = \lambda^2 - 4\lambda + 3 = (\lambda - 3)(\lambda - 1)$, so $\lambda_1 = 3$, $\lambda_2 = 1$.
2. $S - 3I = \begin{pmatrix} -1 & 1 \\ 1 & -1 \end{pmatrix}$ has null vector $(1, 1)$, so $q_1 = (1, 1)/\sqrt2$. $S - I = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ has null vector $(1, -1)$, so $q_2 = (1, -1)/\sqrt2$.
3. $q_1 \cdot q_2 = (1 - 1)/2 = 0$: orthogonal, as step 2 of the proof promised.
4. Projector sum: $3P_1 + 1P_2 = S$ (computed in section 3).

(b) Rayleigh quotient. At $x = (1, 2)$:

1. $Sx = (2 + 2,\ 1 + 4) = (4, 5)$, so $x^\top S x = 1\cdot4 + 2\cdot5 = 14$ and $x^\top x = 5$. So $R = 14/5 = 2.8$.
2. In eigen-coordinates, $y = Q^\top x = \big((1 + 2)/\sqrt2,\ (1 - 2)/\sqrt2\big) = (3/\sqrt2, -1/\sqrt2)$.
3. The weights are $y_1^2/\|y\|^2 = 4.5/5 = 0.9$ and $y_2^2/\|y\|^2 = 0.5/5 = 0.1$.
4. $R = 0.9 \cdot 3 + 0.1 \cdot 1 = 2.8$. It is close to 3 because $x$ is close to $q_1$. (In the Rayleigh figure, $x = (1, 2)/\sqrt5$ is the direction $\theta \approx 63.4°$.)

(c) Courant–Fischer in 3-D. $D = \operatorname{diag}(3, 2, 1)$, $k = 2$.

1. On the plane $\operatorname{span}(e_1, e_3)$, $R$ is an average of 3 and 1. Its min is 1, at $e_3$.
2. On $\operatorname{span}(e_1, e_2)$, $R$ is an average of 3 and 2. Its min is $2 = \lambda_2$, at $e_2$.
3. No plane does better: every plane meets $\operatorname{span}(e_2, e_3)$ in at least a line ($2 + 2 > 3$), and there $R \le 2$.

(d) Weyl, a tight case and a loose case, both with $\|E\|_2 = 0.1$:

• $E = \begin{pmatrix} 0 & 0.1 \\ 0.1 & 0 \end{pmatrix} = 0.1(q_1q_1^\top - q_2q_2^\top)$: $S + E = \begin{pmatrix} 2 & 1.1 \\ 1.1 & 2 \end{pmatrix}$ has eigenvalues $2 \pm 1.1$, that is, 3.1 and 0.9. Both moved by exactly 0.1, because $E$ has the same eigenvectors as $S$.
• $E = \operatorname{diag}(0.1, -0.1)$: $S + E = \begin{pmatrix} 2.1 & 1 \\ 1 & 1.9 \end{pmatrix}$ has eigenvalues $2 \pm \sqrt{0.1^2 + 1} = 2 \pm \sqrt{1.01}$, that is, $3.00499$ and $0.99501$. They moved by only $0.005$. To first order an eigenvalue moves by $q_k^\top E q_k$, which is 0 here ($q_1^\top E q_1 = (0.1 - 0.1)/2 = 0$). Weyl is a worst-case bound.

5. In code #

NumPy checks the hand computations above. The notebook for this lesson has these cells and the exercises.

import numpy as np

S = np.array([[2., 1.], [1., 2.]])
lam, Q = np.linalg.eigh(S)      # for symmetric matrices; eigenvalues in ASCENDING order
print(lam)                                                        # [1. 3.]
print(np.allclose(Q.T @ Q, np.eye(2)), np.allclose(Q @ np.diag(lam) @ Q.T, S))   # True True

# the spectral decomposition as a sum of projectors: S = 3 P1 + 1 P2
P1 = np.outer([1, 1], [1, 1]) / 2; P2 = np.outer([1, -1], [1, -1]) / 2
print(np.allclose(3 * P1 + 1 * P2, S), np.allclose(P1 + P2, np.eye(2)), np.allclose(P1 @ P2, 0))  # True True True

x = np.array([1., 2.])
print(x @ S @ x, x @ x)                        # 14.0 5.0, so R(x) = 2.8
y = Q.T @ x                                    # coordinates in the eigenbasis
w = y**2 / (y @ y)                             # weights, in the order of lam = [1, 3]
print(np.round(w, 12), round(lam @ w, 12))     # [0.1 0.9] 2.8

# Courant–Fischer in 3-D, for D = diag(3, 2, 1): R restricted to a plane is the
# Rayleigh quotient of V^T D V. Here it is diagonal, so its smallest entry is min R.
D = np.diag([3., 2., 1.])
for cols in ([0, 2], [0, 1]):
    V = np.eye(3)[:, cols]                     # orthonormal basis of the plane
    print(cols, np.diag(V.T @ D @ V))          # [0, 2] [3. 1.]   then   [0, 1] [3. 2.]

# Weyl: two perturbations with ||E||_2 = 0.1
for E in (np.array([[0, .1], [.1, 0]]), np.array([[.1, 0], [0, -.1]])):
    print(round(np.linalg.norm(E, 2), 12), np.round(np.linalg.eigvalsh(S + E), 5))
    # 0.1 [0.9 3.1]   then   0.1 [0.99501 3.00499]

# Without symmetry there is no such bound
N = np.array([[0., 1.], [1e-4, 0.]])           # [[0,1],[0,0]] + E with ||E||_2 = 1e-4
print(np.round(np.linalg.eigvals(N).real, 6))  # [ 0.01 -0.01]: moved 100 times ||E||_2

6. Where it shows up #

• PCA. The first principal direction maximizes the variance $u^\top \Sigma u$ over unit $u$. This is a Rayleigh quotient of the covariance $\Sigma$, so the answer is the top eigenvector. Weyl: for a sample covariance $\hat\Sigma = \Sigma + E$, each estimated variance $\lambda_k(\hat\Sigma)$ is within $\|E\|_2$ of the true one. Principal directions with close eigenvalues can still mix (lesson 17).
• Loss landscapes. The sharpness $\lambda_{\max}(H)$ of a Hessian is a max Rayleigh quotient. At a critical point of the loss, $\lambda_{\min}(H) < 0$ means it is not a minimum (it is a saddle or a maximum): along the eigenvector of $\lambda_{\min}$ the curvature is negative, so the loss decreases.
• Graphs. A graph Laplacian $L$ has eigenvalues $0 = \mu_1 \le \mu_2 \le \dots$ (sorted ascending, by convention) with $\mathbf{1}$ in the null space. Then $\mu_2 = \min R_L(x)$ over $x \perp \mathbf{1}$, and the minimizer (the Fiedler vector) splits the graph: spectral clustering and GNNs (lesson 19).
• Classification. Fisher's linear discriminant analysis (LDA) maximizes a generalized Rayleigh quotient $w^\top S_B w / w^\top S_W w$ (see the folded block in section 3).
• ML for science. Normal modes of a structure solve the generalized symmetric eigenproblem $Kx = \omega^2 Mx$ ($K$, $M$ symmetric, $M$ positive definite). In quantum mechanics the ground-state energy is $\min_\psi R_H(\psi)$ (the variational principle). Neural-network wavefunctions such as FermiNet minimize this Rayleigh quotient (estimated by Monte Carlo sampling), and every trial state gives an upper bound.
• Numerics. A backward-stable symmetric eigensolver returns the exact eigenvalues of $S + E$ with $\|E\|_2$ about $u\|S\|_2$ ($u \approx 1.1 \times 10^{-16}$) times a modest factor. By Weyl, every computed eigenvalue has an absolute error of that size: large eigenvalues are accurate, tiny ones may have no correct digits.

7. Common mistakes #

• Using the spectral theorem for a non-symmetric matrix. $\begin{pmatrix} 1 & 2 \\ 0 & 3 \end{pmatrix}$ has eigenvectors $(1, 0)$ and $(1, 1)$: not orthogonal.
• Maximizing $x^\top A x$ for non-symmetric $A$ with $\lambda_{\max}(A)$. Only the symmetric part counts: $x^\top A x = x^\top \tfrac12(A + A^\top) x$.
• Thinking the maximizer of $R$ is unique. It is the whole $\lambda_1$-eigenspace.
• Calling every critical point of $R$ a max or a min. Middle eigenvectors are saddles.
• Index conventions. Here $\lambda_1 \ge \dots \ge \lambda_n$, but np.linalg.eigh returns ascending order. In Courant–Fischer the min–max is over dimension $n - k + 1$, not $n - k$.
• Weyl misuse. Comparing eigenvalues without sorting both spectra the same way; applying it to non-symmetric matrices; concluding that eigenvectors are stable too.
• np.linalg.eig on a symmetric matrix. It does not use the symmetry: it may return complex dtype, and with a repeated eigenvalue the eigenvectors need not be orthogonal. Use eigh.

8. Check yourself #

1. Is $\begin{pmatrix} 1 & 2 \\ 0 & 3 \end{pmatrix}$ orthogonally diagonalizable?
   Answer

   No. $Q\Lambda Q^\top$ with real $\Lambda$ is always symmetric, and this matrix is not. Its eigenvectors $(1, 0)$ and $(1, 1)$ have dot product 1.
2. $S = \operatorname{diag}(4, 4, 1)$. Which $x$ maximize $R(x)$?
   Answer

   All nonzero $x \in \operatorname{span}(e_1, e_2)$, with $R = 4$: the whole $\lambda_{\max}$-eigenspace.
3. $S = \operatorname{diag}(3, 2, 1)$. Starting at $e_2$, in which directions does $R$ go up and down?
   Answer

   $R(e_2\cos t + e_1\sin t) = 2 + \sin^2 t$ goes up toward $e_1$; $R(e_2\cos t + e_3\sin t) = 2 - \sin^2 t$ goes down toward $e_3$. So $e_2$ is a saddle point.
4. $A$ is symmetric with eigenvalues $10, 5, 1$, and $E$ is symmetric with $\|E\|_2 = 0.3$. Where can $\lambda_2(A + E)$ be? Can it reach the ends?
   Answer

   In $[4.7, 5.3]$ by Weyl. Yes: $E = \pm 0.3 I$ reaches each end.
5. Why is the Rayleigh-quotient eigenvalue estimate more accurate than the eigenvector it uses?
   Answer

   $\nabla R = 0$ at eigenvectors, so the first-order error vanishes: $R(q + \varepsilon d) - \lambda = \varepsilon^2(R(d) - \lambda)/(1 + \varepsilon^2)$ for unit $d \perp q$.
6. In the Courant–Fischer proof, why must a $k$-dimensional $U$ meet $\operatorname{span}(q_k, \dots, q_n)$?
   Answer

   The dimensions add up to $k + (n - k + 1) = n + 1 > n$, so the intersection has dimension at least 1.
7. In the proof that $q_1^\perp$ is invariant, where is $S^\top = S$ used? Give a matrix where $q_1$ is an eigenvector but $q_1^\perp$ is not invariant.
   Answer

   In $q_1^\top (Sx) = (S^\top q_1)^\top x = (Sq_1)^\top x$. Example: $M = \begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}$ has $Me_1 = e_1$, but $e_2 \perp e_1$ goes to $Me_2 = (1, 2)$, which is not perpendicular to $e_1$.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. State the spectral theorem for a real symmetric matrix $S$.

   Show answer

2. Why are the eigenvalues of a symmetric $2\times2$ matrix $\begin{pmatrix} a & b \\ b & c \end{pmatrix}$ real?

   Show answer

3. Why are eigenvectors of a symmetric matrix for different eigenvalues orthogonal?

   Show answer

4. What is the key step that gives a symmetric matrix enough eigenvectors?

   Show answer

5. Write $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ as a sum of projectors.

   Show answer

6. What is the range of the Rayleigh quotient $R(x) = x^\top Sx/x^\top x$, and why?

   Show answer

7. What are the critical points of the Rayleigh quotient?

   Show answer

8. Courant–Fischer in words, for $\lambda_2$ of a $3\times3$ symmetric matrix.

   Show answer

9. State Weyl's inequality.

   Show answer

10. Why does Weyl's inequality need symmetry? Give the example.

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Why are the eigenvalues of a covariance matrix real and its principal components orthogonal?" — It is symmetric, so the spectral theorem applies.
• "Maximize $x^\top S x$ subject to $\|x\| = 1$." — Lagrangian: $2Sx - 2\mu x = 0$, so $Sx = \mu x$ and the value is $\mu$; take $\lambda_{\max}$ (symmetrize first if $S$ is not symmetric).
• "Your covariance estimate has error $\|E\|_2 = 0.05$. How far off can the top variance be? And the top PC?" — At most $0.05$ (Weyl); the PC depends on the eigengap (Davis–Kahan).
• "How does deflation find the second eigenvector?" — $S - \lambda_1 q_1 q_1^\top = \sum_{i \ge 2} \lambda_i q_i q_i^\top$.

10. Practice #

The notebook for this lesson runs in Colab. It has four exercises, each with a check cell and a folded solution:

1. Rayleigh sweep: compute $R$ on a grid of directions in the plane and recover $\lambda_{\max}$, $\lambda_{\min}$ and their eigenvectors.
2. Top-$k$ eigenpairs of a symmetric matrix by power iteration plus deflation $S \leftarrow S - \lambda q q^\top$.
3. Courant–Fischer by search: the best "weakest direction" over many random $k$-dimensional subspaces approaches $\lambda_k$ from below.
4. Weyl check: compare the eigenvalue shifts with $\|E\|_2$ for random symmetric perturbations, and find a non-symmetric case that breaks the bound.

11. Watch and read #

Symmetric Matrices and Positive DefinitenessGilbert Strang · MIT 18.06 (2010), lecture 25 · 44 min

The first half proves real eigenvalues and orthogonal eigenvectors, as in section 3.

Counting Parameters in SVD, LU, QR, Saddle PointsGilbert Strang · MIT 18.065 (2018), lecture 18 · 49 min

The second part covers saddle points and the Rayleigh quotient.

Derivatives of Inverse and Singular ValuesGilbert Strang · MIT 18.065 (2018), lecture 16 · 43 min

The end of the lecture shows interlacing and the Weyl inequalities.

• Sheldon Axler, Linear Algebra Done Right, 4th edition, free PDF: §7B "Spectral theorem" (the real spectral theorem is 7.29).
• Gilbert Strang, MIT 18.06 (2010), lecture 25: Symmetric matrices and positive definiteness, with notes and exercises.
• Alex Levis, "Weyl's inequality" (Harvard BST 235 note): Courant–Fischer and Weyl for singular values; the last section gives both for symmetric matrices.
• Terence Tao, "254A, Notes 3a: Eigenvalues and sums of Hermitian matrices", §1 (spectral theorem), §2 (Courant–Fischer, Theorem 2), §3 (Weyl and other inequalities).