Perturbation theory: Weyl and Davis–Kahan

Before this lesson: lesson 06 (spectral theorem, Rayleigh quotient, Courant–Fischer; Weyl is proved there), lesson 08 (the SVD) and lesson 09 (PCA); conditioning is in lesson 13. Time: about 70 minutes, plus the notebook.

---

Why this matters #

In practice every matrix is a noisy copy of the matrix we care about: a sample covariance instead of the population covariance, a graph Laplacian built from noisy similarities, a quantized weight matrix, the floating-point output of an eigensolver. Perturbation theory says which spectral quantities survive the noise. Eigenvalues of symmetric matrices are robust: they move at most as much as the noise (Weyl). Eigenvectors are only as robust as the eigengap, the distance from their eigenvalue to the rest of the spectrum (Davis–Kahan). This one idea tells you when principal components can be trusted, how spectral clustering picks the number of clusters, why climate scientists group nearly equal EOFs, and when a low-rank compression keeps its subspace.

1. Predict first #

2. The picture #

Simplest case. $A = \operatorname{diag}(a, b)$ with $a > b$ and gap $\delta = a - b$. Add the off-diagonal noise $E = \varepsilon\begin{pmatrix}0&1\\1&0\end{pmatrix}$, with $\|E\|_2 = \varepsilon$. The matrix $\begin{pmatrix}a&\varepsilon\\\varepsilon&b\end{pmatrix}$ has eigenvalues

and its top eigenvector makes an angle $\theta$ with $e_1$, where $\tan 2\theta = 2\varepsilon/\delta$ (section 3 derives this). There are two regimes:

• Large gap ($\varepsilon \ll \delta$): $\theta \approx \varepsilon/\delta$, and each eigenvalue moves by about $\varepsilon^2/\delta$, much less than $\varepsilon$.
• Small gap ($\delta \ll \varepsilon$): $2\theta \approx 90°$, so $\theta \approx 45°$, however small $\varepsilon$ is. The eigenvalues still move by at most $\varepsilon$.

So the eigenvalue error is controlled by $\varepsilon$ alone, and the eigenvector error by $\varepsilon/\delta$.

Why, as a picture. $A$ maps the unit circle to an ellipse with half-axes $a$ and $b$, and the eigenvectors are its axes. With a small gap the ellipse is almost a circle. Its axes are poorly defined, and a small bump can turn them anywhere. At $\delta = 0$ (a circle) every direction is an eigenvector.

Interactive figure: loading…

3. Definitions and main results #

Throughout, $A$ and $\hat A = A + E$ are real symmetric $n\times n$ matrices, with eigenvalues $\lambda_1 \ge \dots \ge \lambda_n$ and $\hat\lambda_1 \ge \dots \ge \hat\lambda_n$ and orthonormal eigenvectors $q_j$ and $\hat q_j$.

Eigenvalues: Weyl #

Theorem (Weyl). $|\hat\lambda_k - \lambda_k| \le \|E\|_2$ for every $k$.

Lesson 06 proves it from Courant–Fischer: the Rayleigh quotients add, $R_{A+E}(x) = R_A(x) + R_E(x)$, and $R_E(x)$ always lies in $[-\|E\|_2, \|E\|_2]$. So the eigenvalues of a symmetric matrix have condition number 1: an error of size $\|E\|_2$ in the matrix gives an error of at most $\|E\|_2$ in every eigenvalue.

Interactive figure: loading…

Frobenius version (Hoffman–Wielandt): $\sum_k (\hat\lambda_k - \lambda_k)^2 \le \|E\|_F^2$. It bounds all the moves together.

Singular values: Weyl for any matrix #

Theorem (Weyl for singular values). For any $A, E \in \mathbb{R}^{m\times n}$ and every $k$,

The matrices need not be square or symmetric. The trick is to build a symmetric matrix whose eigenvalues are the singular values.

The symmetric embedding. For $A \in \mathbb{R}^{m\times n}$, let

It is symmetric. Its eigenvalues are $\pm\sigma_1(A), \dots, \pm\sigma_p(A)$ with $p = \min(m, n)$, plus $|m - n|$ zeros.

Small example first. $A = \begin{pmatrix} 3 & 0 \\ 0 & 1 \\ 0 & 0 \end{pmatrix}$ ($3\times2$, singular values 3 and 1). $H(A)$ is $5\times5$, and its eigenvalues are $3, 1, 0, -1, -3$. The single 0 comes from $|m - n| = 1$.

Proof of the theorem.

1. Let $Av_i = \sigma_i u_i$ and $A^\top u_i = \sigma_i v_i$ (the SVD, lesson 08). Then $H\begin{pmatrix}u_i\\v_i\end{pmatrix} = \begin{pmatrix}Av_i\\A^\top u_i\end{pmatrix} = \sigma_i\begin{pmatrix}u_i\\v_i\end{pmatrix}$ and $H\begin{pmatrix}u_i\\-v_i\end{pmatrix} = -\sigma_i\begin{pmatrix}u_i\\-v_i\end{pmatrix}$.
2. These $2p$ vectors are orthogonal. The remaining $|m - n|$ eigenvectors come from the null space: if $m > n$, every unit $u \perp u_1, \dots, u_n$ has $A^\top u = 0$, so $H\begin{pmatrix}u\\0\end{pmatrix} = 0$ (the case $m < n$ is the same with $v$).
3. Sorted in decreasing order, the eigenvalues of $H(A)$ are

So $\lambda_k(H(A)) = \sigma_k(A)$ for $k = 1, \dots, p$. 4. $H$ is linear: $H(A + E) = H(A) + H(E)$. By steps 1–2 for $E$, the largest $|\lambda_i(H(E))|$ is $\sigma_1(E)$. So $\|H(E)\|_2 = \sigma_1(E) = \|E\|_2$. 5. Weyl for the symmetric matrices $H(A)$ and $H(E)$ gives

By step 3, for $k \le p$ the left side is $|\sigma_k(A + E) - \sigma_k(A)|$. $\blacksquare$

The same embedding turns other symmetric results into results about singular values. Wedin's theorem below is the singular-vector version of Davis–Kahan.

Non-symmetric matrices have no such bound #

For a non-symmetric matrix, a tiny $E$ can move the eigenvalues a lot. The extreme case is a Jordan block: the $n\times n$ matrix $J$ with zeros on the diagonal and ones just above it. Its only eigenvalue is 0. Put $\varepsilon$ in its bottom-left corner. The characteristic polynomial becomes $\lambda^n - \varepsilon$, so the eigenvalues are the $n$ points $\varepsilon^{1/n} e^{2\pi i j/n}$ on a circle of radius $\varepsilon^{1/n}$. For $n = 6$ and $\varepsilon = 10^{-4}$ that radius is $10^{-4/6} \approx 0.22$; for $n = 10$ and $\varepsilon = 10^{-10}$ the eigenvalues move by $0.1$, a billion times $\|E\|_2$.

Interactive figure: loading…

Bauer–Fike and near-defective matrices

Theorem (Bauer–Fike). Let $A = X\Lambda X^{-1}$ be diagonalizable. Every eigenvalue $\mu$ of $A + E$ satisfies $\min_i |\mu - \lambda_i| \le \kappa_2(X)\,\|E\|_2$, where $\kappa_2(X) = \|X\|_2\|X^{-1}\|_2$.

Proof.

1. If $\mu$ is an eigenvalue of $A$, there is nothing to prove. Otherwise $A - \mu I = X(\Lambda - \mu I)X^{-1}$ is invertible.
2. $A + E - \mu I = (A - \mu I)\big(I + (A - \mu I)^{-1}E\big)$ is singular, so $I + (A - \mu I)^{-1}E$ is singular. Then some unit $z$ has $(A - \mu I)^{-1}Ez = -z$, so $\|(A - \mu I)^{-1}E\|_2 \ge 1$.
3. $\|(A - \mu I)^{-1}\|_2 = \|X(\Lambda - \mu I)^{-1}X^{-1}\|_2 \le \kappa_2(X)/\min_i|\lambda_i - \mu|$.
4. So $1 \le \kappa_2(X)\,\|E\|_2/\min_i|\lambda_i - \mu|$. $\blacksquare$

The condition number of the eigenvector matrix $X$ is the amplifier. For symmetric $A$, $X = Q$ is orthogonal and $\kappa_2(Q) = 1$: the same constant 1 as in Weyl. The same holds for every normal matrix ($AA^\top = A^\top A$), which also has orthonormal eigenvectors (complex ones in general).

Ill-conditioned eigenvectors, not an ill-conditioned matrix. "Near-defective" means that the eigenvector matrix $X$ is ill-conditioned; $A$ itself can be well-conditioned. $A = \begin{pmatrix}1&1\\0&1.001\end{pmatrix}$ has $\kappa(A) \approx 2.6$ but $\kappa(X) \approx 2000$, and an entry $10^{-6}$ at position $(2,1)$ moves both eigenvalues by about $6\times10^{-4}$. A defective matrix (like the Jordan block) is the limit $\kappa(X) = \infty$; there the move is like $\|E\|_2^{1/n}$, not proportional to $\|E\|_2$.

Angles between subspaces #

To say how far an eigenvector or an eigenspace has moved, we need a distance between subspaces. Comparing vectors entry by entry does not work: $q$ and $-q$ are the same eigenvector, and inside an eigenspace any orthonormal basis is allowed. We use angles. Three cases in $\mathbb{R}^3$ show the idea.

Two lines. For unit vectors $u, v$, the angle $\theta \in [0°, 90°]$ is given by $\cos\theta = |u^\top v|$. The absolute value ignores the sign. Example: $u = (1, 0)$ and $v = (1, 1)/\sqrt2$ give $\cos\theta = 1/\sqrt2$, so $\theta = 45°$ and $\sin\theta = 0.707$. Two useful forms: $\sin\theta = \|(I - uu^\top)v\|$ (the part of $v$ that is not along $u$) and $\sin\theta = \|uu^\top - vv^\top\|_2$ (the distance between the two projectors).

A line and a plane. Project the line onto the plane. The angle is the angle between the line and its shadow. Example: the line through $(1, 1, 1)$ and the $xy$-plane. The shadow is along $(1, 1, 0)$, and $\cos\theta = \|(1, 1, 0)\|/\|(1, 1, 1)\| = \sqrt{2/3}$, so $\theta \approx 35.3°$.

Two planes in $\mathbb{R}^3$. They always share a line ($2 + 2 > 3$, as in lesson 06). So the first angle is $\theta_1 = 0$. The second angle $\theta_2$ is the opening angle between the planes, measured perpendicular to the shared line. Example: the $xy$-plane and the plane spanned by $e_1$ and $(0, 1, 1)/\sqrt2$ share the $x$-axis, and they open by $\theta_2 = 45°$.

Interactive figure: loading…

The general definition. Let $V, \hat V \in \mathbb{R}^{n\times d}$ have orthonormal columns. The principal angles $0 \le \theta_1 \le \dots \le \theta_d \le 90°$ between their column spaces are given by

and we collect their sines in the diagonal matrix $\sin\Theta = \operatorname{diag}(\sin\theta_1, \dots, \sin\theta_d)$.

In words: $\theta_1$ is the smallest angle between a vector of one subspace and a vector of the other. Remove these two directions; $\theta_2$ is the smallest angle between what is left, and so on. The result does not depend on the choice of bases: $\hat V^\top V$ changes to $R_1^\top \hat V^\top V R_2$ with orthogonal $R_1, R_2$, which has the same singular values. Two facts make $\sin\Theta$ a distance between subspaces:

For the two planes above: $\sigma(\hat V^\top V) = (1, 0.707)$, the angles are $0°$ and $45°$, and $\|VV^\top - \hat V\hat V^\top\|_2 = 0.707$.

First-order perturbation: where the gap comes from #

Step 1: the exact $2\times2$ answer. A symmetric $2\times2$ matrix $M = \begin{pmatrix}p&r\\r&q\end{pmatrix}$ has a unit eigenvector $(\cos\theta, \sin\theta)$. Write $Mv = \lambda v$ in both rows:

Multiply the first equation by $\sin\theta$, the second by $\cos\theta$, and subtract. $\lambda$ cancels:

With $2\sin\theta\cos\theta = \sin 2\theta$ and $\cos^2\theta - \sin^2\theta = \cos 2\theta$ this is $\tfrac{p - q}2\sin 2\theta = r\cos 2\theta$.

So $\tan 2\theta = 2r/(p - q)$. For $A + E = \begin{pmatrix}1 + \delta&\varepsilon\\\varepsilon&1\end{pmatrix}$ this gives

Step 2: compare with a first-order guess. For small $x$, $\tan x \approx x$, so $2\theta \approx 2\varepsilon/\delta$ and $\theta \approx \varepsilon/\delta$: (coupling)/(gap). The table compares the exact angle with $\varepsilon/\delta$ for $\delta = 1$.

$\varepsilon$	exact $\theta$	first order $\varepsilon/\delta$
0.01	0.573°	0.573°
0.1	5.65°	5.73°
0.5	22.5°	28.6°
1	31.7°	57.3°

The first-order answer is excellent while $\varepsilon \ll \delta$. When $\varepsilon$ is comparable to $\delta$, it is too large: the exact angle can never pass $45°$, but $\varepsilon/\delta$ grows without limit.

Step 3: the general formulas. Let $\lambda_k$ be a simple (not repeated) eigenvalue, and let $\lambda(t), q(t)$ be the eigenpair of $A + tE$ that starts at $(\lambda_k, q_k)$, with $\|q(t)\| = 1$. Then

Derivation.

1. Differentiate $(A + tE)\,q(t) = \lambda(t)\,q(t)$ at $t = 0$: $Eq_k + Aq' = \lambda' q_k + \lambda_k q'$.
2. Multiply on the left by $q_k^\top$. As $q_k^\top A = \lambda_k q_k^\top$, the terms with $q'$ cancel: $\lambda' = q_k^\top E q_k$.
3. Multiply by $q_j^\top$ with $j \ne k$: $q_j^\top E q_k + \lambda_j\, q_j^\top q' = \lambda_k\, q_j^\top q'$, so $q_j^\top q' = q_j^\top E q_k/(\lambda_k - \lambda_j)$.
4. From $\|q(t)\|^2 = 1$: $q_k^\top q' = 0$. Expand $q'$ in the eigenbasis. $\blacksquare$

For the $2\times2$ example, $q_2^\top E q_1 = e_2^\top E e_1 = \varepsilon$ and $\lambda_1 - \lambda_2 = \delta$, so $q'(0) = (\varepsilon/\delta)\,e_2$ and $q(1) \approx e_1 + (\varepsilon/\delta)\,e_2$: the same $\theta \approx \varepsilon/\delta$ as in step 2.

How to read the formulas:

• The eigenvalue changes by $q_k^\top E q_k$, which is at most $\|E\|_2$: the same constant 1 as Weyl.
• The eigenvector mixes in each $q_j$ with weight (coupling)/(gap). The nearest eigenvalue dominates, and $\|q'\| \le \|E\|_2/\min_{j\ne k}|\lambda_k - \lambda_j|$. So the condition number of an eigenvector is 1/gap.
• At a repeated eigenvalue the formula divides by zero. Inside the eigenspace the eigenvectors are not unique, and an arbitrarily small $E$ picks the basis. The eigenspace itself stays stable if it is separated from the rest of the spectrum.

The Davis–Kahan $\sin\theta$ theorem #

The first-order formula holds only for small $E$. Davis–Kahan gives a bound for every $E$.

Theorem (one eigenvector, classical form). Let $Aq = \lambda q$ with $\|q\| = 1$, let $\hat q_k$ be the eigenvector of $\hat A$ that we compare with $q$, and let $\hat\delta = \min_{j \ne k}|\hat\lambda_j - \lambda|$, the distance from $\lambda$ to the other eigenvalues of $\hat A$. If $\hat\delta > 0$, then

Proof.

1. Residual: as $Aq = \lambda q$, we get $(\hat A - \lambda I)\,q = Eq$.
2. Write $q = \sum_j c_j \hat q_j$ in the orthonormal eigenbasis of $\hat A$ (here symmetry is used). Then $(\hat A - \lambda I)q = \sum_j (\hat\lambda_j - \lambda)\,c_j\,\hat q_j$.
3. Take norms (the $\hat q_j$ are orthonormal), drop the term $j = k$, and use $|\hat\lambda_j - \lambda| \ge \hat\delta$ for $j \ne k$:

4. $\sum_{j\ne k} c_j^2 = 1 - c_k^2 = 1 - \cos^2\theta = \sin^2\theta$. Hence $\sin\theta \le \|Eq\|/\hat\delta$. $\blacksquare$

The gap $\hat\delta$ uses the eigenvalues of the noisy matrix $\hat A$. In statistics we know $A$'s gap better, or we want a bound in terms of it. The next corollary uses only the gap of $A$, at the price of a factor 2.

Corollary (gap of $A$ only; Yu, Wang and Samworth). Let $\delta_k = \min(\lambda_{k-1} - \lambda_k,\ \lambda_k - \lambda_{k+1}) > 0$, with $\lambda_0 = +\infty$ and $\lambda_{n+1} = -\infty$. Then

Proof of the corollary

1. If $\|E\|_2 > \delta_k/2$, the right side is above 1, and $\sin\theta \le 1$ always. Nothing to prove.
2. If $\|E\|_2 \le \delta_k/2$, Weyl gives, for $j < k$, $\hat\lambda_j \ge \hat\lambda_{k-1} \ge \lambda_{k-1} - \|E\|_2 \ge \lambda_k + \delta_k - \|E\|_2$, and for $j > k$, $\hat\lambda_j \le \lambda_k - \delta_k + \|E\|_2$.
3. So every other eigenvalue of $\hat A$ is at distance at least $\delta_k - \|E\|_2 \ge \delta_k/2$ from $\lambda_k$: $\hat\delta \ge \delta_k/2$.
4. The theorem gives $\sin\theta \le \|E\|_2/\hat\delta \le \|E\|_2/(\delta_k/2)$. $\blacksquare$

Read the corollary in words: the eigenvector turns by at most about (noise)/(gap). When the bound is above 1, it says nothing; the vector may or may not turn.

Subspace version. Let $V = (q_r, \dots, q_s)$ hold $d = s - r + 1$ eigenvectors of $A$, $\hat V$ the matching eigenvectors of $\hat A$, and $\delta = \min(\lambda_{r-1} - \lambda_r,\ \lambda_s - \lambda_{s+1}) > 0$ the gap between this block of eigenvalues and the rest of the spectrum of $A$. Then (Yu, Wang, Samworth 2015)

Gaps inside the block do not matter: only the separation of the block from the rest. This is why a cluster of close eigenvalues has a stable subspace even when its single eigenvectors are unstable.

Sharpness, the classical subspace form, and singular vectors (Wedin)

The constant 2 cannot be improved in general: Yu, Wang and Samworth give an example where the bound is reached (there $\hat V$ is orthogonal to $V$). For small $E$ the first-order formula gives at most about $\min(\sqrt d\,\|E\|_2,\ \|E\|_F)/\delta$, half the bound. The classical Davis–Kahan form is $\|\sin\Theta\| \le \|EV\|/\hat\delta$ in the spectral or Frobenius norm, when the block eigenvalues of $A$ lie in an interval $[\alpha, \beta]$ and the other eigenvalues of $\hat A$ lie outside $(\alpha - \hat\delta, \beta + \hat\delta)$.

Singular vectors (Wedin). For any $A$ and $A + E$ of the same shape, let $U_k, V_k$ hold the top $k$ left and right singular vectors of $A$, and $\hat U_k, \hat V_k$ those of $A + E$. If $\|E\|_2 < \sigma_k - \sigma_{k+1}$ (singular values of $A$), then the sines of the principal angles between $U_k$ and $\hat U_k$, and between $V_k$ and $\hat V_k$, are at most $\|E\|_2/(\sigma_k - \sigma_{k+1} - \|E\|_2)$. The singular-value gap plays the role of the eigengap.

Answers to section 1. (1) By Weyl, at most $0.01$; in fact both move by about $0.0095$ (to $1.0105$ and $0.9905$). For the eigenvector, $\tan 2\theta = 2\cdot0.01/0.001 = 20$, so $\theta \approx 43.6°$: almost the largest possible turn, $45°$. (2) The plane. The gap $\lambda_1 - \lambda_2 = 0.1$ is small, so $q_1$ alone can turn a lot. The gap between the pair and the rest is $\lambda_2 - \lambda_3 = 0.9$, so $\operatorname{span}(q_1, q_2)$ moves little. Section 4 has the numbers.

4. Worked example #

(a) Same noise, three gaps. $E = \varepsilon\begin{pmatrix}0&1\\1&0\end{pmatrix}$ with $\varepsilon = \|E\|_2 = 0.01$, and $A = \operatorname{diag}(1 + \delta, 1)$:

gap $\delta$	eigenvalues of $A + E$	eigenvalue move	angle of $\hat q_1$ ($\sin$)	bound $2\varepsilon/\delta$
1	2.0001, 0.9999	0.0001	0.57° (0.0100)	0.02
0.01	1.01618, 0.99382	0.0062	31.7° (0.526)	2 (no information)
0.001	1.01051, 0.99049	0.0095	43.6° (0.689)	20 (no information)

1. Weyl holds in every row: every move is below 0.01.
2. Row 1: the first-order formula predicts $\hat q_1 \approx e_1 + \frac{q_2^\top E q_1}{\lambda_1 - \lambda_2}e_2 = e_1 + 0.01\,e_2$, an angle of $0.01$ rad $= 0.57°$. Exact.
3. Rows 2 and 3: the bound is above 1, so it says nothing, and the angles really are large ($\tan 2\theta = 2$ and $20$).

(b) A cluster. $A = \operatorname{diag}(2, 1.9, 1)$ and $E = 0.05\,(\mathbf 1\mathbf 1^\top - I)$, that is, $0.05$ in every off-diagonal entry ($\mathbf 1$ is the all-ones vector). Then $\|E\|_2 = 0.1$ and $\|E\|_F \approx 0.122$.

1. $A + E$ has eigenvalues $2.0249, 1.8801, 0.9950$. Each moved by less than $0.1$ (Weyl).
2. $\hat q_1$ is $23.5°$ away from $q_1 = e_1$. The gap is $\delta_1 = 0.1$, so the bound $2\cdot0.1/0.1 = 2$ says nothing, and the vector really turned.
3. The top-2 plane has gap $\delta = \lambda_2 - \lambda_3 = 0.9$. Its principal angles are $4.04°$ and $0°$ (two planes in $\mathbb{R}^3$ always share a line), so $\|\sin\Theta\|_F = 0.0705$. The bound is $2\min(\sqrt2\cdot0.1,\ 0.122)/0.9 = 0.272$. The plane is stable, although the vectors inside it are not.
4. Why: the noise mostly rotates $q_1$ and $q_2$ inside their plane (the coupling $0.05$ is half the gap $0.1$). It tilts the plane only a little (the coupling $0.05$ is small compared with the gap $0.9$).
5. $q_3 = e_3$ also has gap $0.9$: it turns by $4.04°$ ($\sin = 0.070$), below its bound $2\cdot0.1/0.9 = 0.222$.

5. In code #

NumPy checks the numbers of sections 3 and 4, tests the corollary in random trials and shows the non-symmetric amplifier. The notebook for this lesson has these cells and the exercises.

import numpy as np
from scipy.linalg import subspace_angles

def eigh_desc(M):
    """Eigenvalues in DEcreasing order and matching eigenvectors (eigh sorts ascending)."""
    w, V = np.linalg.eigh(M)
    return w[::-1], V[:, ::-1]

# Weyl for singular values through the symmetric embedding H(A) = [[0, A], [A^T, 0]]
A = np.array([[3., 0.], [0., 1.], [0., 0.]])
H = np.block([[np.zeros((3, 3)), A], [A.T, np.zeros((2, 2))]])
print(np.round(np.sort(np.linalg.eigvalsh(H))[::-1], 6))              # [ 3.  1.  0. -1. -3.]

# principal angles: two planes in R^3 share a line
V = np.eye(3)[:, :2]                                                   # the xy-plane
Vh = np.column_stack([[1, 0, 0], np.array([0, 1, 1]) / np.sqrt(2)])    # span(e1, (e2+e3)/sqrt2)
print(np.round(np.linalg.svd(Vh.T @ V, compute_uv=False), 4))          # [1.     0.7071]
print(np.round(np.degrees(subspace_angles(Vh, V)), 2))                 # [45.  0.]

# 2x2: the same noise and three gaps
F = np.array([[0., 1.], [1., 0.]]); eps = 0.01
for gap in (1.0, 0.01, 0.001):
    w, Vg = eigh_desc(np.diag([1 + gap, 1.0]) + eps * F)
    theta = np.degrees(np.arccos(abs(Vg[0, 0])))          # angle between q1_hat and e1
    print(gap, np.round(w, 5), round(theta, 2), round(2 * eps / gap, 3))
# 1.0 [2.0001 0.9999] 0.57 0.02
# 0.01 [1.01618 0.99382] 31.72 2.0
# 0.001 [1.01051 0.99049] 43.57 20.0

# a cluster: the top eigenvector turns a lot, the top-2 plane does not
A = np.diag([2.0, 1.9, 1.0]); E = 0.05 * (np.ones((3, 3)) - np.eye(3))
w0, V0 = eigh_desc(A); w, V = eigh_desc(A + E)
print(round(np.linalg.norm(E, 2), 6), np.round(w, 4))                  # 0.1 [2.0249 1.8801 0.995 ]
print(round(np.degrees(np.arccos(abs(V[:, 0] @ V0[:, 0]))), 2))         # 23.45
ang = subspace_angles(V[:, :2], V0[:, :2])                              # principal angles, largest first
print(np.round(np.degrees(ang), 2), round(np.linalg.norm(np.sin(ang)), 4))  # [4.04 0.  ] 0.0705
print(round(2 * min(np.sqrt(2) * 0.1, np.linalg.norm(E)) / 0.9, 3))     # 0.272 (the bound)
P, P0 = V[:, :2] @ V[:, :2].T, V0[:, :2] @ V0[:, :2].T
print(round(np.linalg.norm(P - P0, 2), 4))                              # 0.0705 = ||sin Theta||_2

# the corollary sin(theta) <= 2 ||E||_2 / delta_k in random trials
rng = np.random.default_rng(0); worst = 0.0
for _ in range(2000):
    lam = np.sort(rng.uniform(0, 5, 6))[::-1]
    Q, _ = np.linalg.qr(rng.standard_normal((6, 6)))
    G = rng.standard_normal((6, 6)); En = rng.uniform(1e-3, 0.3) * (G + G.T)
    _, Vh = eigh_desc(Q @ np.diag(lam) @ Q.T + En)
    k = rng.integers(6)
    delta = min(lam[k - 1] - lam[k] if k > 0 else np.inf, lam[k] - lam[k + 1] if k < 5 else np.inf)
    s = np.sqrt(max(0.0, 1 - (Vh[:, k] @ Q[:, k]) ** 2))
    worst = max(worst, s / (2 * np.linalg.norm(En, 2) / delta))
print(worst < 1)                                                        # True

# non-symmetric: the eigenvector matrix X amplifies (Bauer-Fike)
B = np.array([[1., 1.], [0., 1.001]])
_, X = np.linalg.eig(B)
print(round(np.linalg.cond(B), 2), round(np.linalg.cond(X)))            # 2.62 2000
print(np.round(np.linalg.eigvals(B + np.array([[0., 0.], [1e-6, 0.]])).real, 6))  # moved ~6e-4, not 1e-6

subspace_angles returns the principal angles in radians, largest first. Always compare eigenvectors through $|\hat q^\top q|$, angles or projectors, never entry by entry.

6. Where it shows up #

• PCA from samples. For $N$ samples of $d$-dimensional Gaussian data with $N \ge d$, the sample covariance has $\|\hat\Sigma - \Sigma\|_2$ of order $\|\Sigma\|_2\sqrt{d/N}$ (up to a constant). Weyl: the variances are that accurate. Davis–Kahan: principal component $k$ is reliable only when this is small compared with $\delta_k$, so roughly $N \gg d\,\|\Sigma\|_2^2/\delta_k^2$. When eigenvalues are nearly equal, report the subspace they span, not single components.
• Climate EOFs and ensemble PCA (ML for science). EOFs are the principal components of a climate field. North et al. (1982) give the rule of thumb: the sampling error of an eigenvalue is about $\lambda\sqrt{2/N}$ for $N$ independent samples. If it is comparable to the distance to a neighbouring eigenvalue, the two EOFs are mixed by sampling noise and must be read as a pair. For example, $\lambda = 2$ with $N = 100$ gives an error of about $0.28$.
• Spectral clustering. For $k$ disconnected clusters, the eigenvectors of the $k$ smallest Laplacian eigenvalues span the cluster indicators. Edges between clusters perturb the Laplacian; Davis–Kahan keeps this $k$-dimensional eigenspace close if the gap $\mu_{k+1} - \mu_k$ is large ($\mu$ sorted ascending). This is the eigengap heuristic for choosing $k$ (lesson 19).
• Compression and quantization. Quantization or pruning adds $E$ to a weight matrix. The singular values move by at most $\|E\|_2$ (Weyl), and the top-$k$ singular subspace stays put only if $\sigma_k - \sigma_{k+1}$ is large compared with $\|E\|_2$ (Wedin). With a small gap at the cut, an SVD-based compression can pick a different subspace after a tiny change.
• Numerics. LAPACK's error bound for a computed symmetric eigenvector is about $\varepsilon_{\text{mach}}\|A\|_2/\text{gap}_k$. Eigenvalues are accurate to $\varepsilon_{\text{mach}}\|A\|_2$; eigenvectors of close eigenvalues are individually unreliable, but their span is reliable.
• Physics. The first-order formulas are Rayleigh–Schrödinger perturbation theory: the energy shift is $q_k^\top E q_k$, and states mix with weights $1/(\lambda_k - \lambda_j)$. Degenerate levels need degenerate perturbation theory, for the same reason as above.

7. Common mistakes #

• Comparing eigenvectors entry by entry. $q$ and $-q$ are the same eigenvector, and inside a repeated eigenspace any rotation is allowed. Compare $|\hat q^\top q|$, principal angles or projectors.
• "Small noise, so small eigenvector change." Only relative to the gap: $\sin\theta \le 2\|E\|_2/\delta_k$.
• The wrong gap. For $q_k$ the gap is to both neighbours. For a block, it is the gap between the block and the rest; gaps inside the block do not matter.
• Reading a bound above 1 as "large rotation". Such a bound says nothing. Davis–Kahan is an upper bound; the true angle can be small, for example when $E$ has the same eigenvectors as $A$.
• Using the first-order formula for large noise. $\theta \approx \varepsilon/\delta$ needs $\varepsilon \ll \delta$; in the $2\times2$ example the true angle never passes $45°$.
• Mismatched indices. $\hat q_k$ must be the $k$-th eigenvector of $\hat A$ in the same order as $q_k$ (np.linalg.eigh sorts ascending).
• Using Weyl or Davis–Kahan for non-symmetric matrices. Eigenvalues can move by much more than $\|E\|_2$ (Bauer–Fike allows $\kappa(X)\|E\|_2$). For general matrices use singular values and Wedin.

8. Check yourself #

1. $A$ has eigenvalues $5, 4.9, 1$ and $\|E\|_2 = 0.02$. Bound $\sin\theta$ for the top eigenvector, and $\|\sin\Theta\|_F$ for the top-2 eigenspace.
   Answer

   Top eigenvector: $\delta_1 = 0.1$, so $\sin\theta \le 2\cdot0.02/0.1 = 0.4$. Top-2 eigenspace: $\delta = 4.9 - 1 = 3.9$, so $\|\sin\Theta\|_F \le 2\sqrt2\cdot0.02/3.9 \approx 0.0145$.
2. From $(A + tE)\,q(t) = \lambda(t)\,q(t)$, derive $\lambda'(0)$ for a simple eigenvalue.
   Answer

   Differentiate at $t = 0$: $Eq_k + Aq' = \lambda'q_k + \lambda_kq'$. Multiply by $q_k^\top$ and use $q_k^\top A = \lambda_kq_k^\top$: the $q'$ terms cancel and $\lambda'(0) = q_k^\top Eq_k$.
3. $A = \operatorname{diag}(3, 1)$ and $E = \varepsilon\begin{pmatrix}0&1\\1&0\end{pmatrix}$. What is the top eigenvector to first order?
   Answer

   $\hat q_1 \approx e_1 + \frac{e_2^\top Ee_1}{3 - 1}e_2 = e_1 + \frac{\varepsilon}2 e_2$. (For $\varepsilon = 0.1$ the exact ratio of the entries is $0.0499$.)
4. Where does the Davis–Kahan proof use that $\hat A$ is symmetric?
   Answer

   In steps 2–3: $\hat A$ has an orthonormal eigenbasis, so $\|(\hat A - \lambda I)q\|^2 = \sum_j(\hat\lambda_j - \lambda)^2c_j^2$ and $\sum_j c_j^2 = 1$. For a non-normal $\hat A$ the eigenvectors are not orthogonal and this identity fails.
5. A noisy matrix $A + E$ has singular values $5, 3, 0.08, 0.05$, and you know $\|E\|_2 \le 0.1$. What can you say about $\operatorname{rank}(A)$ and its top-2 singular subspaces?
   Answer

   Weyl for singular values: $\sigma_1(A) \ge 4.9$ and $\sigma_2(A) \ge 2.9$, so $\operatorname{rank}A \ge 2$; but $\sigma_3(A) \le 0.18$ and $\sigma_4(A) \le 0.15$ can be zero or not, so the rank (2, 3 or 4) is not determined. The gap $\sigma_2(A) - \sigma_3(A) \ge 2.72$ is large, so by Wedin the top-2 singular subspaces are well determined: sines at most $0.1/(2.72 - 0.1) \approx 0.04$.
6. A sample covariance has eigenvalues $2.00, 1.98, 0.50$, and $\|\hat\Sigma - \Sigma\|_2 \approx 0.05$. Can you report PC1? What can you report?
   Answer

   Not PC1. By Weyl, the population gap $\lambda_1 - \lambda_2$ is at most $0.02 + 2\cdot0.05 = 0.12$, so the bound $2\cdot0.05/\delta_1$ is at least $0.83$: PC1 and PC2 may mix. Report the plane of PC1 and PC2: by Weyl the population gap $\lambda_2 - \lambda_3$ is at least $1.98 - 0.50 - 2\cdot0.05 = 1.38$, so $\|\sin\Theta\|_F \le 2\sqrt2\cdot0.05/1.38 \approx 0.10$.
7. What are the eigenvalues of $H(A) = \begin{pmatrix} 0 & A \\ A^\top & 0 \end{pmatrix}$ for $A = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$?
   Answer

   $A$ is $2\times3$ with singular values 2 and 1, so $H(A)$ is $5\times5$ with eigenvalues $2, 1, 0, -1, -2$ (one zero, because $|m - n| = 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 Weyl's inequality for eigenvalues of symmetric matrices.

   Show answer

2. State Weyl's inequality for singular values. How is it proved?

   Show answer

3. State the Bauer–Fike theorem.

   Show answer

4. How are the principal angles between two subspaces computed?

   Show answer

5. What is $\|\sin\Theta\|_2$ in terms of projectors?

   Show answer

6. What is $\lambda'(0)$ for a simple eigenvalue of $A + tE$?

   Show answer

7. What is $q'(0)$ for the eigenvector of a simple eigenvalue $\lambda_k$ of $A + tE$?

   Show answer

8. Compute the angle of the top eigenvector of $\begin{pmatrix} 1.001 & 0.01 \\ 0.01 & 1 \end{pmatrix}$.

   Show answer

9. Davis–Kahan in words.

   Show answer

10. Why is the span of a cluster of close eigenvectors stable when its single eigenvectors are not?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Eigenvalues are stable but eigenvectors are not. Explain." — Weyl has constant 1; eigenvectors have condition number 1/gap (first-order formula, Davis–Kahan); give the $2\times2$ example.
• "How many samples do you need to estimate the top principal component?" — Enough that $\|\hat\Sigma - \Sigma\|_2 \approx \|\Sigma\|_2\sqrt{d/N}$ is small compared with $\lambda_1 - \lambda_2$.
• "Two eigenvalues of your covariance are almost equal. What do you report?" — The 2-D subspace they span; it is stable if it is separated from the rest of the spectrum.
• "Why does spectral clustering look at the eigengap?" — The $k$-dimensional eigenspace is stable when $\mu_{k+1} - \mu_k$ is large.
• "The eigenvectors from your solver change between machines. Bug?" — Not necessarily: sign flips and rotations inside a near-degenerate eigenspace are allowed. Compare subspaces.

10. Practice #

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

1. Weyl in practice: compute the largest eigenvalue move for random symmetric noise, check it against $\|E\|_2$, and find the noise that reaches the bound.
2. Write sin_theta for two vectors and sin_theta_subspaces for two subspaces (through projectors), and compare with scipy.linalg.subspace_angles.
3. Implement the first-order eigenvector formula and show that its error shrinks like $\|E\|_2^2$.
4. Davis–Kahan for PCA: for a covariance with a small and a large eigengap, compare the true angles of the sample eigenvectors with the bound $2\|E\|_2/\delta_k$.

11. Watch and read #

15. Matrices A(t) Depending on t, Derivative = dA/dtGilbert Strang · MIT 18.065, lecture 15 · 50 min

Derivatives of eigenvalues, as in the first-order formulas of section 3, and interlacing.

Can PCA Recover the True Eigenvalues? Matrix Perturbation Theory - RMT (6/7)Jingyuan Hu · 46 min

From 6:36, the proof of Weyl's inequality, then covariance concentration.

Can PCA Recover the True Eigenvectors? Davis–Kahan Theorem - RMT (7/7)Jingyuan Hu · 26 min

The proof of Davis–Kahan and the subspace version.

• Yi Yu, Tengyao Wang, Richard J. Samworth, A useful variant of the Davis–Kahan theorem for statisticians (Biometrika, 2015): Theorem 1 (the classical form), Theorem 2 (population gap only), Section 4 (singular vectors).
• Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Spectral Methods for Data Science: A Statistical Perspective (2021): §2.2 (distances and angles between subspaces), §2.3 (Davis–Kahan, with proof), §2.4 (Wedin), §3.3 (PCA).
• Paige Bright, Alan Edelman, Steven G. Johnson, Matrix Calculus (for Machine Learning and Beyond), ch. 13 "Derivatives of eigenproblems" (the first-order formulas).
• Alex Levis, "Weyl's inequality" (Harvard BST 235 note): a short proof of Weyl from Courant–Fischer.