20.9 The Davis–Kahan Theorem

Weyl’s inequality settled the eigenvalues of a Hermitian matrix: under a Hermitian perturbation $\mathbf{E}$ , each of them moves by at most $\left\| \mathbf{E} \right\|_2$ , whatever the matrix and however its eigenvalues are spaced. Eigenvectors are a different matter, and this section is about them. Section 8 supplied the yardstick, the principal angles between two subspaces, and Section 7 supplied the tool, bounds for the equation $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = \mathbf{Y}$ . The theorem of this section is what happens when the two meet: the perturbation of an invariant subspace satisfies a Sylvester equation, and the bounds of Section 7 then measure it.

Throughout, $\mathbf{A}$ and $\widetilde{\mathbf{A}} = \mathbf{A} + \mathbf{E}$ are Hermitian matrices in $M_n(\mathbb{C})$ , so $\mathbf{E} = \widetilde{\mathbf{A}} - \mathbf{A}$ is Hermitian too, and $1 \le k \le n - 1$ . As everywhere in this chapter, $\left\| \cdot \right\|_2$ is the spectral norm and $\left\| \cdot \right\|_F$ the Frobenius norm, and every bound names the norm it holds in. For a subspace we write $\operatorname{col}(\mathbf{Q})$ for the column space of a matrix $\mathbf{Q}$ whose columns span it.

20.9.1. Eigenvectors can move a long way

Before any theorem, here is what goes wrong. The example is as small as it can be, and every number in it is exact.

Example (A tiny perturbation that turns the eigenvectors through 45°)

Let $0 < \eta < 1$ and $\mathbf{A} = \begin{pmatrix} 1 + \eta & 0 \\ 0 & 1 - \eta \end{pmatrix}, \qquad \mathbf{E} = \eta\begin{pmatrix} -1 & 1 \\ 1 & 1 \end{pmatrix} .$ Compare the eigenvalues and the eigenvectors of $\mathbf{A}$ and of $\widetilde{\mathbf{A}} = \mathbf{A} + \mathbf{E}$ , and compute $\left\| \mathbf{E} \right\|_2$ .

Solution. Adding, $\widetilde{\mathbf{A}} = \begin{psmallmatrix} 1 & \eta \\ \eta & 1 \end{psmallmatrix}$ . Since $\widetilde{\mathbf{A}}\begin{pmatrix} 1 \\ 1 \end{pmatrix} = (1 + \eta)\begin{pmatrix} 1 \\ 1 \end{pmatrix}, \qquad \widetilde{\mathbf{A}}\begin{pmatrix} 1 \\ -1 \end{pmatrix} = (1 - \eta)\begin{pmatrix} 1 \\ -1 \end{pmatrix},$ the eigenvalues of $\widetilde{\mathbf{A}}$ are $1 + \eta$ and $1 - \eta$ : exactly those of $\mathbf{A}$ . The eigenvectors are another story. For the eigenvalue $1 + \eta$ , the matrix $\mathbf{A}$ has the unit eigenvector $\mathbf{e}_1$ and $\widetilde{\mathbf{A}}$ has $\tfrac{1}{\sqrt2}(1, 1)$ ; the two lines they span meet at the angle $\pi/4$ , because $\lvert\langle \mathbf{e}_1, \tfrac{1}{\sqrt2}(1,1) \rangle\rvert = \tfrac{1}{\sqrt2} = \cos\tfrac{\pi}{4}$ . The same happens for $1 - \eta$ , with $\mathbf{e}_2$ and $\tfrac{1}{\sqrt2}(1, -1)$ .

The matrix $\mathbf{E}/\eta$ is Hermitian and squares to $2\mathbf{I}_2$ , so its eigenvalues are $\pm\sqrt2$ (it has trace $0$ ), and by Lemma 17.3.5 $\left\| \mathbf{E} \right\|_2 = \sqrt2\,\eta .$ So as $\eta \to 0^{+}$ the perturbation vanishes, the eigenvalues do not move at all, and yet the eigenvectors of $\widetilde{\mathbf{A}}$ stay a full $45^\circ$ away from those of $\mathbf{A}$ .

The rotation does not shrink with $\eta$ . What does shrink with $\eta$ is the distance $2\eta$ between the two eigenvalues of $\mathbf{A}$ , and that is the whole story: the two eigenvalues are so close that a perturbation of their own size can mix their eigenvectors freely. An eigenvector bound must therefore divide by a gap, and the natural guess is “angle $\lesssim$ perturbation / gap”. Here that ratio is $\sqrt2\eta/2\eta = 1/\sqrt2 = \sin(\pi/4)$ , which is exactly the sine of the angle. The theorem below turns the guess into an inequality, and this example will turn out to attain it.

Warning. Well-conditioned eigenvalues do not make well-conditioned eigenvectors. Corollary 17.3.6 guarantees that every eigenvalue of a Hermitian matrix moves by at most $\left\| \mathbf{E} \right\|_2$ , with no mention of gaps, and it is tempting to expect the same of eigenvectors. Example (A tiny perturbation that turns the eigenvectors through 45°) refutes this: a perturbation of size $\sqrt2\,\eta$ leaves every eigenvalue fixed and turns every eigenvector through $\pi/4$ , however small $\eta$ is. No inequality of the form $\sin\theta \le C\left\| \mathbf{E} \right\|_2$ , with $C$ depending only on $n$ , can hold.

20.9.2. Two norms, three facts

The proofs of this section and the next shuffle unitary factors and matrices with orthonormal columns in and out of norms, sometimes the spectral one and sometimes the Frobenius one. The facts needed are elementary, but they are needed so often that they are worth collecting once. Part (c) is mostly quoted: its norm identities for a matrix with orthonormal columns are Lemma 20.8.1 (b) of Section 8, read with $U = \operatorname{col}(\mathbf{X})$ , and for the Frobenius norm the unitary invariance is Lemma 11.7.5. The rest — (a), (b), and the inequality $\left\| \mathbf{X}^{*}\mathbf{N} \right\| \le \left\| \mathbf{N} \right\|$ — is proved below, and what the lemma is really for is to have all of it, in both norms, in one place.

Lemma 20.9.1 (Moving Factors in and out of the Two Norms)

(a) $\left\| \mathbf{M}^{*} \right\| = \left\| \mathbf{M} \right\|$ for every $\mathbf{M} \in M_{m \times n}(\mathbb{C})$ .
(b) $\left\| \mathbf{X}\mathbf{M}\mathbf{Y} \right\| \le \left\| \mathbf{X} \right\|_2\,\left\| \mathbf{M} \right\|\,\left\| \mathbf{Y} \right\|_2$ whenever the product is defined.
(c) If $\mathbf{X} \in M_{m \times k}(\mathbb{C})$ has orthonormal columns, that is $\mathbf{X}^{*}\mathbf{X} = \mathbf{I}_k$ , then $\left\| \mathbf{X} \right\|_2 = 1$ , $\left\| \mathbf{X}\mathbf{M} \right\| = \left\| \mathbf{M} \right\|$ , and $\left\| \mathbf{X}^{*}\mathbf{N} \right\| \le \left\| \mathbf{N} \right\|$ for all $\mathbf{M} \in M_{k \times n}(\mathbb{C})$ and $\mathbf{N} \in M_{m \times n}(\mathbb{C})$ . In particular $\left\| \mathbf{U}\mathbf{M}\mathbf{V} \right\| = \left\| \mathbf{M} \right\|$ for unitary $\mathbf{U}$ and $\mathbf{V}$ .

Proof.

(a) For $\left\| \cdot \right\|_F$ this holds because $\mathbf{M}^{*}$ has the same entries as $\mathbf{M}$ up to position and conjugation. For $\left\| \cdot \right\|_2$ , let $\mathbf{x} \in \mathbb{C}^n$ . By Theorem 11.1.5 and Theorem 16.3.2 (a), applied twice, $\left\| \mathbf{M}\mathbf{x} \right\|^2 = \langle \mathbf{M}^{*}\mathbf{M}\mathbf{x}, \mathbf{x} \rangle \le \left\| \mathbf{M}^{*}\mathbf{M}\mathbf{x} \right\|\,\left\| \mathbf{x} \right\| \le \left\| \mathbf{M}^{*} \right\|_2\left\| \mathbf{M} \right\|_2\left\| \mathbf{x} \right\|^2 .$ Taking the maximum over unit $\mathbf{x}$ gives $\left\| \mathbf{M} \right\|_2^2 \le \left\| \mathbf{M}^{*} \right\|_2\left\| \mathbf{M} \right\|_2$ , hence $\left\| \mathbf{M} \right\|_2 \le \left\| \mathbf{M}^{*} \right\|_2$ when $\mathbf{M} \ne \mathbf{O}$ (and trivially when $\mathbf{M} = \mathbf{O}$ ). Applying this to $\mathbf{M}^{*}$ , whose conjugate transpose is $\mathbf{M}$ , gives the reverse inequality.
(b) For $\left\| \cdot \right\|_2$ this is Theorem 16.3.2 (d) used twice. For $\left\| \cdot \right\|_F$ , let $\mathbf{m}_1, \dots, \mathbf{m}_n$ be the columns of $\mathbf{M}$ . The columns of $\mathbf{X}\mathbf{M}$ are the $\mathbf{X}\mathbf{m}_j$ , and the squared Frobenius norm is the sum of the squared lengths of the columns, so $\left\| \mathbf{X}\mathbf{M} \right\|_F^2 = \sum_j \left\| \mathbf{X}\mathbf{m}_j \right\|^2 \le \left\| \mathbf{X} \right\|_2^2\sum_j\left\| \mathbf{m}_j \right\|^2 = \left\| \mathbf{X} \right\|_2^2\left\| \mathbf{M} \right\|_F^2 .$ For a factor on the right, (a) and the left-hand case give $\left\| \mathbf{M}\mathbf{Y} \right\|_F = \left\| \mathbf{Y}^{*}\mathbf{M}^{*} \right\|_F \le \left\| \mathbf{Y}^{*} \right\|_2\left\| \mathbf{M}^{*} \right\|_F = \left\| \mathbf{Y} \right\|_2\left\| \mathbf{M} \right\|_F$ . Combining the two cases gives (b).
(c) For every $\mathbf{v} \in \mathbb{C}^k$ , $\left\| \mathbf{X}\mathbf{v} \right\|^2 = \mathbf{v}^{*}\mathbf{X}^{*}\mathbf{X}\mathbf{v} = \left\| \mathbf{v} \right\|^2$ . Hence $\left\| \mathbf{X} \right\|_2 = 1$ , and multiplying by $\mathbf{X}$ changes the length of no column, so $\left\| \mathbf{X}\mathbf{M} \right\|_F = \left\| \mathbf{M} \right\|_F$ and $\left\| \mathbf{X}\mathbf{M}\mathbf{v} \right\| = \left\| \mathbf{M}\mathbf{v} \right\|$ for every $\mathbf{v}$ , which gives $\left\| \mathbf{X}\mathbf{M} \right\|_2 = \left\| \mathbf{M} \right\|_2$ . Next, $\left\| \mathbf{X}^{*} \right\|_2 = \left\| \mathbf{X} \right\|_2 = 1$ by (a), so $\left\| \mathbf{X}^{*}\mathbf{N} \right\| \le \left\| \mathbf{N} \right\|$ by (b). Finally, for unitary $\mathbf{U}$ and $\mathbf{V}$ both $\mathbf{U}$ and $\mathbf{V}^{*}$ have orthonormal columns, so $\left\| \mathbf{U}\mathbf{M}\mathbf{V} \right\| = \left\| \mathbf{M}\mathbf{V} \right\| = \left\| \mathbf{V}^{*}\mathbf{M}^{*} \right\| = \left\| \mathbf{M}^{*} \right\| = \left\| \mathbf{M} \right\|$ , using (a) twice.

Part (c) is the one used most. Its inequality $\left\| \mathbf{X}^{*}\mathbf{N} \right\| \le \left\| \mathbf{N} \right\|$ says that reading $\mathbf{N}$ in only some of the coordinates of an orthonormal basis can only lose mass, never gain it.

20.9.3. The perturbation of a subspace is a Sylvester equation

Fix the data. A Hermitian matrix is normal, so by Corollary 12.4.3 there is a unitary $\mathbf{Q} \in M_n(\mathbb{C})$ with $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ diagonal, the eigenvalues appearing in any order we like, and they are real by Theorem 12.2.1. Choose $k$ of them, list them first, and split the columns accordingly: $\mathbf{Q} = \begin{pmatrix} \mathbf{Q}_1 & \mathbf{Q}_2 \end{pmatrix}, \qquad \mathbf{Q}^{*}\mathbf{A}\mathbf{Q} = \begin{pmatrix} \boldsymbol{\Lambda}_1 & \mathbf{O} \\ \mathbf{O} & \boldsymbol{\Lambda}_2 \end{pmatrix},$ with $\mathbf{Q}_1 \in M_{n \times k}(\mathbb{C})$ and $\boldsymbol{\Lambda}_1 \in M_k(\mathbb{R})$ , $\boldsymbol{\Lambda}_2 \in M_{n-k}(\mathbb{R})$ diagonal. Do the same for $\widetilde{\mathbf{A}}$ , producing $\widetilde{\mathbf{Q}} = \begin{pmatrix} \widetilde{\mathbf{Q}}_1 & \widetilde{\mathbf{Q}}_2 \end{pmatrix}$ , $\widetilde{\boldsymbol{\Lambda}}_1$ , and $\widetilde{\boldsymbol{\Lambda}}_2$ . Reading $\mathbf{A}\mathbf{Q} = \mathbf{Q}(\boldsymbol{\Lambda}_1 \oplus \boldsymbol{\Lambda}_2)$ column by column, $\mathbf{A}\mathbf{Q}_1 = \mathbf{Q}_1\boldsymbol{\Lambda}_1, \qquad \widetilde{\mathbf{A}}\widetilde{\mathbf{Q}}_2 = \widetilde{\mathbf{Q}}_2\widetilde{\boldsymbol{\Lambda}}_2 ,$ so the columns of $\mathbf{Q}_1$ are orthonormal eigenvectors of $\mathbf{A}$ , and $U = \operatorname{col}(\mathbf{Q}_1)$ is a $k$ -dimensional subspace invariant under $\mathbf{A}$ . Likewise $W = \operatorname{col}(\widetilde{\mathbf{Q}}_1)$ is a $k$ -dimensional subspace invariant under $\widetilde{\mathbf{A}}$ . The question is how far apart $U$ and $W$ are, and Section 8 answers “measure the principal angles $\theta_1 \le \dots \le \theta_k$ of Definition 20.8.1”.

Put $\mathbf{X} \mathrel{:=} \widetilde{\mathbf{Q}}_2^{*}\mathbf{Q}_1 \in M_{(n-k) \times k}(\mathbb{C}) .$ It measures the angles, and it satisfies an equation.

The unperturbed subspace, read in the perturbed complement, solves a Sylvester equation whose coefficients are the two spectra and whose right-hand side is the perturbation.

Lemma 20.9.2 (The Subspace Perturbation Equation)

In the notation above,

\widetilde{\boldsymbol{\Lambda}}_2\mathbf{X} - \mathbf{X}\boldsymbol{\Lambda}_1 = \widetilde{\mathbf{Q}}_2^{*}\mathbf{E}\mathbf{Q}_1 ,

(20.9.1)

and the nonzero singular values of $\mathbf{X}$ are the nonzero sines $\sin\theta_i$ of the principal angles between $U = \operatorname{col}(\mathbf{Q}_1)$ and $W = \operatorname{col}(\widetilde{\mathbf{Q}}_1)$ , with multiplicity. In particular $\left\| \mathbf{X} \right\|_F = \left\| \sin\Theta(U, W) \right\|_F , \qquad \left\| \mathbf{X} \right\|_2 = \sin\theta_k = \left\| \sin\Theta(U, W) \right\|_2 ,$ where $\sin\Theta(U, W) = \operatorname{diag}(\sin\theta_1, \dots, \sin\theta_k)$ .

Idea. Compute $\widetilde{\mathbf{Q}}_2^{*}\widetilde{\mathbf{A}}\mathbf{Q}_1$ twice. Letting $\widetilde{\mathbf{A}}$ act to the left, on the perturbed eigenvectors, produces $\widetilde{\boldsymbol{\Lambda}}_2$ . Writing $\widetilde{\mathbf{A}} = \mathbf{A} + \mathbf{E}$ and letting $\mathbf{A}$ act to the right, on the unperturbed ones, produces $\boldsymbol{\Lambda}_1$ , plus an error term that carries $\mathbf{E}$ . The difference of the two computations is the identity.

Proof. Taking conjugate transposes in $\widetilde{\mathbf{A}}\widetilde{\mathbf{Q}}_2 = \widetilde{\mathbf{Q}}_2\widetilde{\boldsymbol{\Lambda}}_2$ , and using $\widetilde{\mathbf{A}}^{*} = \widetilde{\mathbf{A}}$ and $\widetilde{\boldsymbol{\Lambda}}_2^{*} = \widetilde{\boldsymbol{\Lambda}}_2$ (a real diagonal matrix), gives $\widetilde{\mathbf{Q}}_2^{*}\widetilde{\mathbf{A}} = \widetilde{\boldsymbol{\Lambda}}_2\widetilde{\mathbf{Q}}_2^{*}$ . Hence $\widetilde{\mathbf{Q}}_2^{*}\widetilde{\mathbf{A}}\mathbf{Q}_1 = \widetilde{\boldsymbol{\Lambda}}_2\widetilde{\mathbf{Q}}_2^{*}\mathbf{Q}_1 = \widetilde{\boldsymbol{\Lambda}}_2\mathbf{X} .$ On the other hand $\widetilde{\mathbf{A}} = \mathbf{A} + \mathbf{E}$ and $\mathbf{A}\mathbf{Q}_1 = \mathbf{Q}_1\boldsymbol{\Lambda}_1$ , so $\begin{aligned} \widetilde{\mathbf{Q}}_2^{*}\widetilde{\mathbf{A}}\mathbf{Q}_1 &= \widetilde{\mathbf{Q}}_2^{*}\mathbf{Q}_1\boldsymbol{\Lambda}_1 + \widetilde{\mathbf{Q}}_2^{*}\mathbf{E}\mathbf{Q}_1 \\ &= \mathbf{X}\boldsymbol{\Lambda}_1 + \widetilde{\mathbf{Q}}_2^{*}\mathbf{E}\mathbf{Q}_1 . \end{aligned}$ Subtracting the two expressions gives Eq. 20.9.1.

For the angles: the columns of the unitary $\widetilde{\mathbf{Q}}$ form an orthonormal basis of $\mathbb{C}^n$ (Theorem 11.7.3), so the $n - k$ columns of $\widetilde{\mathbf{Q}}_2$ are orthonormal and orthogonal to every column of $\widetilde{\mathbf{Q}}_1$ . They therefore span a subspace of $W^{\perp}$ of dimension $n - k$ , which is all of $W^{\perp}$ because $\dim W^{\perp} = n - k$ by Theorem 11.3.2 (c). So $\widetilde{\mathbf{Q}}_2$ is a matrix whose columns are an orthonormal basis of $W^{\perp}$ , and Theorem 20.8.4 (a) says that the singular values of $\widetilde{\mathbf{Q}}_2^{*}\mathbf{Q}_1 = \mathbf{X}$ are the $\sin\theta_i$ , as a multiset completed by zeros; zeros change neither a sum of squares nor a maximum of nonnegative numbers. For the two norms, $\mathbf{I} - P_W = P_{W^{\perp}} = \widetilde{\mathbf{Q}}_2\widetilde{\mathbf{Q}}_2^{*}$ by Lemma 20.8.1 (d) and (a), so $(\mathbf{I} - P_W)\mathbf{Q}_1 = \widetilde{\mathbf{Q}}_2\mathbf{X}$ , and Lemma 20.9.1 (c) removes the factor $\widetilde{\mathbf{Q}}_2$ : $\left\| \mathbf{X} \right\|_F = \left\| (\mathbf{I} - P_W)\mathbf{Q}_1 \right\|_F, \qquad \left\| \mathbf{X} \right\|_2 = \left\| (\mathbf{I} - P_W)\mathbf{Q}_1 \right\|_2 .$ By Theorem 20.8.4 (b), applied with $U$ and $W$ , these are $\left\| \sin\Theta(U, W) \right\|_F$ and $\sin\theta_k = \left\| \sin\Theta(U, W) \right\|_2$ . This proves the lemma.

Quick check. Take $\mathbf{A} = \widetilde{\mathbf{A}} = \mathbf{I}_2$ , so $\mathbf{E} = \mathbf{O}$ , with $k = 1$ , $\mathbf{Q}_1 = \mathbf{e}_1$ , and $\widetilde{\mathbf{Q}}_1 = \tfrac{1}{\sqrt2}(1, 1)$ ; both are legitimate choices of unit eigenvector. The subspaces $U$ and $W$ are $45^\circ$ apart, although the matrices are equal. What does Eq. 20.9.1 say here, and why is there no contradiction?

Solution. Here $\boldsymbol{\Lambda}_1 = (1)$ and $\widetilde{\boldsymbol{\Lambda}}_2 = (1)$ , so the equation reads $1\cdot\mathbf{X} - \mathbf{X}\cdot 1 = \mathbf{O}$ , which every $1 \times 1$ matrix satisfies. The equation holds, as it must, but it does not determine $\mathbf{X}$ , and $\mathbf{X} = \widetilde{\mathbf{Q}}_2^{*}\mathbf{Q}_1 = \tfrac{1}{\sqrt2}(1, -1)\cdot\mathbf{e}_1 = \tfrac{1}{\sqrt2} = \sin\tfrac{\pi}{4}$ is one of its many solutions. The trouble is that the spectra of $\widetilde{\boldsymbol{\Lambda}}_2$ and $\boldsymbol{\Lambda}_1$ overlap. The theorems below assume that they are separated, and then the equation has exactly one solution (Theorem 12.10.2), which is small when the right-hand side is.

20.9.4. The $\sin\Theta$ theorem in the Frobenius norm

With the identity in hand, the theorem is a matter of dividing by the gap. The gap that matters compares perturbed eigenvalues outside the subspace with unperturbed eigenvalues inside it, because those are the two coefficient matrices of the equation.

Theorem 20.9.3 (The Davis–Kahan

\sin\Theta

Theorem)

Let $\mathbf{A}, \widetilde{\mathbf{A}} = \mathbf{A} + \mathbf{E} \in M_n(\mathbb{C})$ be Hermitian, let $1 \le k \le n-1$ , and let $\mathbf{Q} = \begin{pmatrix} \mathbf{Q}_1 & \mathbf{Q}_2 \end{pmatrix}$ and $\widetilde{\mathbf{Q}} = \begin{pmatrix} \widetilde{\mathbf{Q}}_1 & \widetilde{\mathbf{Q}}_2 \end{pmatrix}$ be unitary, with $\mathbf{Q}_1, \widetilde{\mathbf{Q}}_1 \in M_{n \times k}(\mathbb{C})$ , such that $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q} = \boldsymbol{\Lambda}_1 \oplus \boldsymbol{\Lambda}_2, \qquad \widetilde{\mathbf{Q}}^{*}\widetilde{\mathbf{A}}\widetilde{\mathbf{Q}} = \widetilde{\boldsymbol{\Lambda}}_1 \oplus \widetilde{\boldsymbol{\Lambda}}_2$ are real diagonal. Suppose there is a $\delta > 0$ such that $\lvert\mu - \lambda\rvert \ge \delta$ for every diagonal entry $\mu$ of $\widetilde{\boldsymbol{\Lambda}}_2$ and every diagonal entry $\lambda$ of $\boldsymbol{\Lambda}_1$ . Then the principal angles $\Theta = \Theta(\operatorname{col}(\mathbf{Q}_1), \operatorname{col}(\widetilde{\mathbf{Q}}_1))$ satisfy $\left\| \sin\Theta \right\|_F \ \le\ \frac{\left\| \mathbf{E}\mathbf{Q}_1 \right\|_F}{\delta} \ \le\ \frac{\sqrt{k}\,\left\| \mathbf{E} \right\|_2}{\delta} .$

Idea. Eq. 20.9.1 is a Sylvester equation whose two coefficient matrices are diagonal, hence normal, and for a normal pair the separation of Section 7 is exactly the distance between the two spectra. The hypothesis says that this distance is at least $\delta$ , so Section 7’s bound divides the right-hand side by $\delta$ . What is left is Lemma 20.9.2, which reads the size of $\mathbf{X}$ as the size of $\sin\Theta$ .

Proof. Write $\mu_1, \dots, \mu_{n-k}$ for the diagonal entries of $\widetilde{\boldsymbol{\Lambda}}_2$ , $\lambda_1, \dots, \lambda_k$ for those of $\boldsymbol{\Lambda}_1$ , and $\mathbf{Y} = \widetilde{\mathbf{Q}}_2^{*}\mathbf{E}\mathbf{Q}_1$ , so that $\widetilde{\boldsymbol{\Lambda}}_2\mathbf{X} - \mathbf{X}\boldsymbol{\Lambda}_1 = \mathbf{Y}$ by Lemma 20.9.2. A diagonal matrix is normal, and its eigenvalues are its diagonal entries, so Theorem 20.7.2 gives $\operatorname{sep}_F(\widetilde{\boldsymbol{\Lambda}}_2, \boldsymbol{\Lambda}_1) = \min_{i,j}\lvert\mu_i - \lambda_j\rvert \ \ge\ \delta > 0 .$ In particular the two spectra are disjoint, so $\mathbf{X}$ is the unique solution of that equation (Theorem 12.10.2), and Proposition 20.7.1 (d) applies to it: $\left\| \mathbf{X} \right\|_F \ \le\ \frac{\left\| \mathbf{Y} \right\|_F}{\operatorname{sep}_F(\widetilde{\boldsymbol{\Lambda}}_2, \boldsymbol{\Lambda}_1)} \ \le\ \frac{\left\| \mathbf{Y} \right\|_F}{\delta} .$

The columns of $\widetilde{\mathbf{Q}}_2$ are orthonormal, so Lemma 20.9.1 (c) gives $\left\| \mathbf{Y} \right\|_F = \left\| \widetilde{\mathbf{Q}}_2^{*}(\mathbf{E}\mathbf{Q}_1) \right\|_F \le \left\| \mathbf{E}\mathbf{Q}_1 \right\|_F$ . By Lemma 20.9.1 (b), $\left\| \mathbf{E}\mathbf{Q}_1 \right\|_F \le \left\| \mathbf{E} \right\|_2\left\| \mathbf{Q}_1 \right\|_F$ , and $\left\| \mathbf{Q}_1 \right\|_F = \sqrt{k}$ because $\mathbf{Q}_1$ has $k$ unit columns. Finally $\left\| \mathbf{X} \right\|_F = \left\| \sin\Theta \right\|_F$ by Lemma 20.9.2. Chaining the three inequalities proves the theorem.

The right-hand side is a Lipschitz bound with constant $1/\delta$ , and it is sharp. In Example (A tiny perturbation that turns the eigenvectors through 45°), take $k = 1$ , $\mathbf{Q}_1 = \mathbf{e}_1$ with $\boldsymbol{\Lambda}_1 = (1 + \eta)$ , and $\widetilde{\mathbf{Q}}_2 = \tfrac{1}{\sqrt2}(1, -1)$ with $\widetilde{\boldsymbol{\Lambda}}_2 = (1 - \eta)$ . Then $\delta = 2\eta$ and $\mathbf{E}\mathbf{e}_1 = \eta(-1, 1)$ has length $\sqrt2\,\eta$ , so the theorem gives $\sin\theta_1 \le \frac{\sqrt2\,\eta}{2\eta} = \frac{1}{\sqrt2} ,$ and the true angle is $\pi/4$ , whose sine is exactly $1/\sqrt2$ . The large rotation there was not a failure of the theorem. It is what the theorem predicts when the gap is no bigger than the perturbation.

Remark. The roles of $\mathbf{A}$ and $\widetilde{\mathbf{A}}$ may be exchanged, since $\mathbf{A} = \widetilde{\mathbf{A}} + (-\mathbf{E})$ and the principal angles between $U$ and $W$ are those between $W$ and $U$ (a matrix and its conjugate transpose have the same singular values). This gives the companion bound $\left\| \sin\Theta \right\|_F \le \left\| \mathbf{E}\widetilde{\mathbf{Q}}_1 \right\|_F/\delta'$ , where $\delta'$ separates the diagonal of $\boldsymbol{\Lambda}_2$ from that of $\widetilde{\boldsymbol{\Lambda}}_1$ . Use whichever one’s data are at hand.

20.9.5. A one-sided version in the spectral norm

The Frobenius theorem controls all $k$ angles at once. Often only the largest angle matters, $\left\| \sin\Theta \right\|_2 = \sin\theta_k$ , and the Frobenius theorem bounds it too, since $\left\| \sin\Theta \right\|_2 \le \left\| \sin\Theta \right\|_F$ . But its right-hand side $\left\| \mathbf{E}\mathbf{Q}_1 \right\|_F$ can be $\sqrt{k}$ times $\left\| \mathbf{E}\mathbf{Q}_1 \right\|_2$ , and for large $k$ that factor is a real loss. When the two spectra are separated by a single point, one entirely above it and the other entirely below, the one-sided bound of Section 7 removes it.

Theorem 20.9.4 (The

\sin\Theta

Theorem, One-Sided Case)

In the setting of Theorem 20.9.3, suppose instead that there are $a \in \mathbb{R}$ and $\delta > 0$ such that either

(i) every eigenvalue in $\boldsymbol{\Lambda}_1$ is $\ge a$ and every eigenvalue in $\widetilde{\boldsymbol{\Lambda}}_2$ is $\le a - \delta$ , or
(ii) every eigenvalue in $\boldsymbol{\Lambda}_1$ is $\le a$ and every eigenvalue in $\widetilde{\boldsymbol{\Lambda}}_2$ is $\ge a + \delta$ .

Then $\left\| \sin\Theta \right\|_2 = \sin\theta_k \ \le\ \frac{\left\| \mathbf{E}\mathbf{Q}_1 \right\|_2}{\delta} \ \le\ \frac{\left\| \mathbf{E} \right\|_2}{\delta} .$

Proof. Let $\mathbf{X} = \widetilde{\mathbf{Q}}_2^{*}\mathbf{Q}_1$ and $\mathbf{Y} = \widetilde{\mathbf{Q}}_2^{*}\mathbf{E}\mathbf{Q}_1$ , so that $\widetilde{\boldsymbol{\Lambda}}_2\mathbf{X} - \mathbf{X}\boldsymbol{\Lambda}_1 = \mathbf{Y}$ by Lemma 20.9.2. For a real diagonal matrix, $\boldsymbol{\Lambda} \succeq \alpha\mathbf{I}$ means that every diagonal entry is at least $\alpha$ (Theorem 13.1.4 (b), applied to $\boldsymbol{\Lambda} - \alpha\mathbf{I}$ ).

Case (ii). Here $\widetilde{\boldsymbol{\Lambda}}_2 \succeq (a + \delta)\mathbf{I}$ and $\boldsymbol{\Lambda}_1 \preceq a\mathbf{I}$ , with $a + \delta > a$ . By Theorem 20.7.3, applied with $\widetilde{\boldsymbol{\Lambda}}_2$ and $\boldsymbol{\Lambda}_1$ in the roles of its two Hermitian coefficients, the solution of $\widetilde{\boldsymbol{\Lambda}}_2\mathbf{X} - \mathbf{X}\boldsymbol{\Lambda}_1 = \mathbf{Y}$ , which is unique because the two spectra are disjoint, satisfies $\left\| \mathbf{X} \right\|_2 \le \left\| \mathbf{Y} \right\|_2/\delta$ .

Case (i). Multiply the equation by $-1$ : $(-\widetilde{\boldsymbol{\Lambda}}_2)\mathbf{X} - \mathbf{X}(-\boldsymbol{\Lambda}_1) = -\mathbf{Y}$ , where now $-\widetilde{\boldsymbol{\Lambda}}_2 \succeq (\delta - a)\mathbf{I}$ and $-\boldsymbol{\Lambda}_1 \preceq -a\mathbf{I}$ , and $(\delta - a) - (-a) = \delta > 0$ . So case (ii)’s argument applies and gives $\left\| \mathbf{X} \right\|_2 \le \left\| -\mathbf{Y} \right\|_2/\delta = \left\| \mathbf{Y} \right\|_2/\delta$ .

In both cases, Lemma 20.9.1 (c) and (b) give $\left\| \mathbf{Y} \right\|_2 \le \left\| \mathbf{E}\mathbf{Q}_1 \right\|_2 \le \left\| \mathbf{E} \right\|_2\left\| \mathbf{Q}_1 \right\|_2 = \left\| \mathbf{E} \right\|_2$ , and $\left\| \mathbf{X} \right\|_2 = \sin\theta_k$ by Lemma 20.9.2. This proves the theorem.

The typical use is the top of the spectrum: $\boldsymbol{\Lambda}_1$ holds the $k$ largest eigenvalues of $\mathbf{A}$ , and $\widetilde{\boldsymbol{\Lambda}}_2$ the $n - k$ smallest of $\widetilde{\mathbf{A}}$ . Then (i) holds with $a = \lambda_k(\mathbf{A})$ and $\delta = \lambda_k(\mathbf{A}) - \lambda_{k+1}(\widetilde{\mathbf{A}})$ , provided that number is positive.

Remark. Davis and Kahan proved more. If the eigenvalues in $\boldsymbol{\Lambda}_1$ lie in an interval $[a, b]$ and every eigenvalue in $\widetilde{\boldsymbol{\Lambda}}_2$ lies outside $(a - \delta, b + \delta)$ , on either side, then the spectral bound $\sin\theta_k \le \left\| \mathbf{E}\mathbf{Q}_1 \right\|_2/\delta$ still holds. The proof needs more than the one-sided Sylvester bound, and we do not give it. Nothing in this book depends on it. When the two spectra merely avoid each other by $\delta$ , interleaved in any pattern, what we have proved is the Frobenius theorem, and through $\left\| \sin\Theta \right\|_2 \le \left\| \sin\Theta \right\|_F$ the spectral consequence $\sin\theta_k \le \left\| \mathbf{E}\mathbf{Q}_1 \right\|_F/\delta$ .

20.9.6. Single eigenvectors

The most common question is about one eigenvector. A simple eigenvalue has a one-dimensional eigenspace, so its unit eigenvector is determined up to a unimodular factor, and the right measure of how far it moves is the angle between the two lines. For unit vectors $\mathbf{x}$ and $\widetilde{\mathbf{x}}$ we write $\theta(\mathbf{x}, \widetilde{\mathbf{x}}) \in [0, \pi/2]$ for that angle, so that $\cos\theta(\mathbf{x}, \widetilde{\mathbf{x}}) = \lvert\langle \widetilde{\mathbf{x}}, \mathbf{x} \rangle\rvert$ . This is the single principal angle between $\operatorname{span}(\mathbf{x})$ and $\operatorname{span}(\widetilde{\mathbf{x}})$ , since the $1 \times 1$ matrix $\mathbf{x}^{*}\widetilde{\mathbf{x}}$ has the singular value $\lvert\mathbf{x}^{*}\widetilde{\mathbf{x}}\rvert$ .

The theorem needs a separation between the perturbed eigenvalues of $\widetilde{\mathbf{A}}$ and the unperturbed one of $\mathbf{A}$ . In practice only $\mathbf{A}$ is known, and Weyl’s inequality converts a gap in the spectrum of $\mathbf{A}$ into the separation the theorem wants.

Corollary 20.9.5 (Perturbation of a Single Eigenvector)

Let $\mathbf{A}, \widetilde{\mathbf{A}} = \mathbf{A} + \mathbf{E} \in M_n(\mathbb{C})$ be Hermitian, let $\lambda_i(\mathbf{A})$ be a simple eigenvalue of $\mathbf{A}$ with unit eigenvector $\mathbf{x}$ , and put $\gamma \mathrel{:=} \min_{j \ne i}\ \lvert\lambda_i(\mathbf{A}) - \lambda_j(\mathbf{A})\rvert > 0 .$ If $\left\| \mathbf{E} \right\|_2 < \gamma/2$ , then $\lambda_i(\widetilde{\mathbf{A}})$ is a simple eigenvalue of $\widetilde{\mathbf{A}}$ , and every unit eigenvector $\widetilde{\mathbf{x}}$ of $\widetilde{\mathbf{A}}$ for it satisfies $\sin\theta(\mathbf{x}, \widetilde{\mathbf{x}}) \ \le\ \frac{\left\| \mathbf{E} \right\|_2}{\gamma - \left\| \mathbf{E} \right\|_2} \ \le\ \frac{2\left\| \mathbf{E} \right\|_2}{\gamma} .$

Idea. Apply the theorem with $k = 1$ . The only thing to supply is $\delta$ : every eigenvalue $\lambda_j(\widetilde{\mathbf{A}})$ with $j \ne i$ sits within $\left\| \mathbf{E} \right\|_2$ of $\lambda_j(\mathbf{A})$ by Weyl, which is at least $\gamma$ away from $\lambda_i(\mathbf{A})$ . So the separation is at least $\gamma - \left\| \mathbf{E} \right\|_2$ , by the triangle inequality. The hypothesis $\left\| \mathbf{E} \right\|_2 < \gamma/2$ keeps $\lambda_i(\widetilde{\mathbf{A}})$ away from its neighbors too, so that “the” eigenvector makes sense.

Proof. Put $\varepsilon = \left\| \mathbf{E} \right\|_2$ . By Corollary 17.3.6, $\lvert\lambda_j(\widetilde{\mathbf{A}}) - \lambda_j(\mathbf{A})\rvert \le \varepsilon$ for every $j$ . Hence for $j \ne i$ , by the triangle inequality in $\mathbb{R}$ (Theorem 0.6.4), $\begin{aligned} \lvert\lambda_j(\widetilde{\mathbf{A}}) - \lambda_i(\mathbf{A})\rvert &\ge \lvert\lambda_j(\mathbf{A}) - \lambda_i(\mathbf{A})\rvert - \lvert\lambda_j(\widetilde{\mathbf{A}}) - \lambda_j(\mathbf{A})\rvert \\ &\ge \gamma - \varepsilon , \end{aligned}$ and similarly $\lvert\lambda_j(\widetilde{\mathbf{A}}) - \lambda_i(\widetilde{\mathbf{A}})\rvert \ge \gamma - 2\varepsilon > 0$ . So $\lambda_i(\widetilde{\mathbf{A}})$ differs from every other $\lambda_j(\widetilde{\mathbf{A}})$ , and it is a simple eigenvalue of $\widetilde{\mathbf{A}}$ .

By Corollary 12.4.3 there is a unitary matrix whose columns are eigenvectors of $\widetilde{\mathbf{A}}$ , with the eigenvalue $\lambda_i(\widetilde{\mathbf{A}})$ first. That eigenspace is one-dimensional, so the first column is $c\widetilde{\mathbf{x}}$ with $\lvert c\rvert = 1$ , and replacing it by $\widetilde{\mathbf{x}}$ keeps the columns orthonormal eigenvectors. Call the result $\widetilde{\mathbf{Q}} = \begin{pmatrix} \widetilde{\mathbf{x}} & \widetilde{\mathbf{Q}}_2 \end{pmatrix}$ . Then $\widetilde{\boldsymbol{\Lambda}}_2$ is diagonal with entries $\lambda_j(\widetilde{\mathbf{A}})$ , $j \ne i$ . In the same way build $\mathbf{Q} = \begin{pmatrix} \mathbf{x} & \mathbf{Q}_2 \end{pmatrix}$ for $\mathbf{A}$ , with $\boldsymbol{\Lambda}_1 = (\lambda_i(\mathbf{A}))$ . By the display, the hypothesis of Theorem 20.9.3 holds with $k = 1$ and $\delta = \gamma - \varepsilon > 0$ , so $\sin\theta(\mathbf{x}, \widetilde{\mathbf{x}}) = \left\| \sin\Theta \right\|_F \le \frac{\left\| \mathbf{E}\mathbf{x} \right\|}{\gamma - \varepsilon} \le \frac{\varepsilon}{\gamma - \varepsilon} ,$ using $\left\| \mathbf{E}\mathbf{x} \right\| \le \left\| \mathbf{E} \right\|_2\left\| \mathbf{x} \right\| = \varepsilon$ . Finally $\varepsilon < \gamma/2$ gives $\gamma - \varepsilon > \gamma/2$ , so $\varepsilon/(\gamma - \varepsilon) \le 2\varepsilon/\gamma$ . This proves the corollary.

To first order in $\left\| \mathbf{E} \right\|_2$ the bound reads $\sin\theta \lesssim \left\| \mathbf{E} \right\|_2/\gamma$ : an eigenvector is as well conditioned as its eigenvalue is isolated. The constant cannot be improved, and Exercise (C2: The constant in the eigenvector bound is sharp) shows it. The factor $2$ in the cruder form is the price of the hypothesis $\left\| \mathbf{E} \right\|_2 < \gamma/2$ , nothing more. In Example (A tiny perturbation that turns the eigenvectors through 45°), $\gamma = 2\eta$ and $\left\| \mathbf{E} \right\|_2 = \sqrt2\,\eta > \gamma/2$ , so the corollary does not apply there.

Example (The theorem and the corollary, side by side)

Let $\mathbf{A} = \operatorname{diag}(2, 0)$ and $\mathbf{E} = \tfrac34\begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ . Find the exact angle between the eigenvectors of $\mathbf{A}$ and of $\widetilde{\mathbf{A}} = \mathbf{A} + \mathbf{E}$ for the larger eigenvalue, and compare it with the bounds of Theorem 20.9.3 and Corollary 20.9.5.

Solution. Exact. $\widetilde{\mathbf{A}} = \begin{psmallmatrix} 2 & 3/4 \\ 3/4 & 0 \end{psmallmatrix}$ has trace $2$ and determinant $-\tfrac{9}{16}$ , so its eigenvalues are $1 \pm \sqrt{1 + 9/16} = 1 \pm \tfrac54$ , that is $\tfrac94$ and $-\tfrac14$ . For $\tfrac94$ , the first row of $\widetilde{\mathbf{A}} - \tfrac94\mathbf{I}$ is $(-\tfrac14, \tfrac34)$ , which is orthogonal to $(3, 1)$ , and the second row $(\tfrac34, -\tfrac94)$ is a multiple of the first; so $\widetilde{\mathbf{x}} = \tfrac{1}{\sqrt{10}}(3, 1)$ . With $\mathbf{x} = \mathbf{e}_1$ , $\cos\theta = \tfrac{3}{\sqrt{10}}, \qquad \sin\theta = \tfrac{1}{\sqrt{10}} \approx 0.316 .$

The theorem. Take $\boldsymbol{\Lambda}_1 = (2)$ and $\widetilde{\boldsymbol{\Lambda}}_2 = (-\tfrac14)$ , so $\delta = \tfrac94$ . Since $\mathbf{E}\mathbf{e}_1 = (0, \tfrac34)$ , the bound is $\tfrac34 / \tfrac94 = \tfrac13 \approx 0.333$ , within six percent of the truth.

The corollary. The gap is $\gamma = 2$ , and $\mathbf{E}$ is $\tfrac34$ times a Hermitian matrix with eigenvalues $\pm1$ , so $\left\| \mathbf{E} \right\|_2 = \tfrac34 < 1 = \gamma/2$ . The bound is $\tfrac{3/4}{2 - 3/4} = \tfrac35 = 0.6$ , and its cruder form is $2 \cdot \tfrac34/2 = \tfrac34$ .

The theorem is nearly exact because it uses the perturbed eigenvalue $-\tfrac14$ itself. The corollary knows only that this eigenvalue lies within $\tfrac34$ of $0$ , and it must allow for the worst case $\tfrac34$ , which would leave a separation of only $\tfrac54$ .

20.9.7. Clusters: the subspace is stable when the vectors are not

Example (A tiny perturbation that turns the eigenvectors through 45°) looks like bad news for eigenvectors, and it is, for individual eigenvectors of close eigenvalues. But the theorem was stated for subspaces, and that is its real strength. The subspace spanned by the eigenvectors of a cluster of eigenvalues is governed by the gap between the cluster and the rest of the spectrum. The gaps inside the cluster do not enter.

Example (A stable plane with unstable lines inside it)

Let $0 < \eta < 1$ and $\mathbf{A} = \begin{pmatrix} 1 + \eta & 0 & 0 \\ 0 & 1 - \eta & 0 \\ 0 & 0 & -2 \end{pmatrix}, \qquad \mathbf{E} = \eta\begin{pmatrix} -1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} .$ Compare what happens to the eigenvectors for $1 \pm \eta$ with what happens to the plane they span. Then bound the motion of that plane under any Hermitian perturbation $\mathbf{E}'$ with $\left\| \mathbf{E}' \right\|_2 = \varepsilon < 3 - \eta$ .

Solution. The upper-left $2 \times 2$ block is Example (A tiny perturbation that turns the eigenvectors through 45°). So the eigenvalues of $\widetilde{\mathbf{A}} = \mathbf{A} + \mathbf{E}$ are again $1 + \eta, 1 - \eta, -2$ , and the eigenvectors for $1 \pm \eta$ turn through $\pi/4$ , to $\tfrac{1}{\sqrt2}(1, \pm1, 0)$ . But they turn inside the plane $U = \operatorname{span}(\mathbf{e}_1, \mathbf{e}_2)$ , which is invariant under both matrices. So the plane has not moved at all: both principal angles between $U$ and the new plane $W = U$ are $0$ .

Theorem 20.9.3 with $k = 2$ sees this. Take $\mathbf{Q}_1 = \begin{pmatrix} \mathbf{e}_1 & \mathbf{e}_2 \end{pmatrix}$ , $\boldsymbol{\Lambda}_1 = \operatorname{diag}(1 + \eta, 1 - \eta)$ , and $\widetilde{\boldsymbol{\Lambda}}_2 = (-2)$ . The separation is $\delta = (1 - \eta) - (-2) = 3 - \eta$ , and $\left\| \mathbf{E}\mathbf{Q}_1 \right\|_F = \left\| \mathbf{E} \right\|_F = 2\eta$ , so $\left\| \sin\Theta \right\|_F \le \frac{2\eta}{3 - \eta} .$ This is small with $\eta$ , and it has no $2\eta$ in its denominator. (The true value is $0$ ; the theorem does not know that $\mathbf{E}$ happens to preserve $U$ .)

For a general Hermitian $\mathbf{E}'$ with $\left\| \mathbf{E}' \right\|_2 = \varepsilon$ , Corollary 17.3.6 puts the smallest eigenvalue of $\mathbf{A} + \mathbf{E}'$ at most $-2 + \varepsilon$ , while the eigenvalues of $\boldsymbol{\Lambda}_1$ are at least $1 - \eta$ . So case (i) of Theorem 20.9.4 holds with $a = 1 - \eta$ and $\delta = 3 - \eta - \varepsilon > 0$ , and the plane moves by $\sin\theta_2 \le \frac{\varepsilon}{3 - \eta - \varepsilon} .$ The individual eigenvectors are covered by Corollary 20.9.5 only when $\varepsilon < \eta$ , and then only with a bound of order $\varepsilon/(2\eta)$ .

This is the practical lesson of the section. When a matrix has a cluster of close eigenvalues, do not ask for the individual eigenvectors of the cluster. They are ill-conditioned and may be meaningless at the precision of the data. Ask for an orthonormal basis of the invariant subspace of the whole cluster, which is as stable as the cluster is isolated. Numerical eigensolvers act on this advice.

20.9.8. Exercises

A. Check your understanding

Exercise (A1)

(a) State the subspace perturbation equation Eq. 20.9.1, and say which matrix in it measures the principal angles.
(b) In Theorem 20.9.3, which two lists of eigenvalues must be separated by $\delta$ ? Why not the eigenvalues of $\mathbf{A}$ inside and outside the subspace?
(c) True or false: “if $\left\| \mathbf{E} \right\|_2$ is tiny compared with $\left\| \mathbf{A} \right\|_2$ , then every unit eigenvector of $\mathbf{A} + \mathbf{E}$ is close to a unit eigenvector of $\mathbf{A}$ ”. Justify.
(d) Why is $\left\| \sin\Theta \right\|_2 \le \left\| \sin\Theta \right\|_F$ , and when does Theorem 20.9.4 improve on what the Frobenius theorem gives for $\left\| \sin\Theta \right\|_2$ ?
(e) Which earlier result turns the bound on the matrix $\mathbf{X} = \widetilde{\mathbf{Q}}_2^{*}\mathbf{Q}_1$ into a bound on angles?

Solution.

(a) $\widetilde{\boldsymbol{\Lambda}}_2\mathbf{X} - \mathbf{X}\boldsymbol{\Lambda}_1 = \widetilde{\mathbf{Q}}_2^{*}\mathbf{E}\mathbf{Q}_1$ , with $\mathbf{X} = \widetilde{\mathbf{Q}}_2^{*}\mathbf{Q}_1$ ; by Lemma 20.9.2 the singular values of $\mathbf{X}$ are the sines of the principal angles between $\operatorname{col}(\mathbf{Q}_1)$ and $\operatorname{col}(\widetilde{\mathbf{Q}}_1)$ , together with zeros.
(b) The diagonal of $\widetilde{\boldsymbol{\Lambda}}_2$ , the eigenvalues of the perturbed matrix belonging to the complement, against the diagonal of $\boldsymbol{\Lambda}_1$ , the eigenvalues of the unperturbed matrix belonging to the subspace. These are the two coefficient matrices of the Sylvester equation, and the proof divides by their separation, which Theorem 20.7.2 computes as the smallest of those differences. A gap inside the spectrum of $\mathbf{A}$ alone is useful only after Corollary 17.3.6 converts it, as in Corollary 20.9.5.
(c) False. In Example (A tiny perturbation that turns the eigenvectors through 45°), $\left\| \mathbf{E} \right\|_2 = \sqrt2\,\eta$ can be as small as we like compared with $\left\| \mathbf{A} \right\|_2 = 1 + \eta$ , yet each unit eigenvector of $\mathbf{A} + \mathbf{E}$ makes the angle $\pi/4$ with every unit eigenvector of $\mathbf{A}$ , which are the multiples of $\mathbf{e}_1$ and $\mathbf{e}_2$ . What controls eigenvectors is the perturbation relative to the gap, not relative to the matrix.
(d) $\left\| \sin\Theta \right\|_2 = \sin\theta_k$ is one of the numbers whose squares sum to $\left\| \sin\Theta \right\|_F^2$ . The Frobenius theorem gives $\sin\theta_k \le \left\| \mathbf{E}\mathbf{Q}_1 \right\|_F/\delta$ , and $\left\| \mathbf{E}\mathbf{Q}_1 \right\|_F$ can be as large as $\sqrt{k}\,\left\| \mathbf{E}\mathbf{Q}_1 \right\|_2$ . When the two spectra lie on opposite sides of a gap of width $\delta$ , Theorem 20.9.4 replaces it by $\left\| \mathbf{E}\mathbf{Q}_1 \right\|_2$ , which is never worse and can be $\sqrt{k}$ times smaller.
(e) Theorem 20.8.4, applied with $W = \operatorname{col}(\widetilde{\mathbf{Q}}_1)$ and the orthonormal basis $\widetilde{\mathbf{Q}}_2$ of $W^{\perp}$ .

B. Practice

Exercise (B1: How far does the top eigenvector move?)

Let $\mathbf{A} = \begin{pmatrix} 5 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & -1 \end{pmatrix}, \qquad \mathbf{E} = \frac12\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix},$ and let $\widetilde{\mathbf{x}}$ be a unit eigenvector of $\widetilde{\mathbf{A}} = \mathbf{A} + \mathbf{E}$ for its largest eigenvalue.

(a) Compute $\left\| \mathbf{E} \right\|_2$ and the gap $\gamma$ of $\lambda_1(\mathbf{A}) = 5$ .
(b) Use Corollary 20.9.5 to bound $\sin\theta(\mathbf{e}_1, \widetilde{\mathbf{x}})$ .
(c) Use Theorem 20.9.3, with the separation estimated by Corollary 17.3.6, to obtain a better bound. Hence show that the angle is less than $13^\circ$ .
(d) Check that $2$ is an eigenvalue of $\widetilde{\mathbf{A}}$ and find the other two. Recompute the bound of (c) with the exact separation.

Solution.

(a) The matrix $\mathbf{M} = 2\mathbf{E}$ is symmetric with characteristic polynomial $t^3 - 2t = t(t^2 - 2)$ , so its eigenvalues are $0, \pm\sqrt2$ and $\left\| \mathbf{E} \right\|_2 = \tfrac12\sqrt2 = \tfrac{\sqrt2}{2} \approx 0.707$ by Lemma 17.3.5. The eigenvalues of $\mathbf{A}$ are $5, 2, -1$ , so $\gamma = 5 - 2 = 3$ .
(b) $\left\| \mathbf{E} \right\|_2 \approx 0.707 < 1.5 = \gamma/2$ , so the corollary applies: $\sin\theta \le \frac{\sqrt2/2}{3 - \sqrt2/2} \approx 0.308 .$
(c) By Corollary 17.3.6, $\lambda_2(\widetilde{\mathbf{A}}) \le 2 + \tfrac{\sqrt2}{2}$ and $\lambda_3(\widetilde{\mathbf{A}}) \le -1 + \tfrac{\sqrt2}{2}$ , so both lie at distance at least $\delta = 3 - \tfrac{\sqrt2}{2} \approx 2.293$ from $5$ . Apply Theorem 20.9.3 with $k = 1$ , $\mathbf{Q}_1 = \mathbf{e}_1$ , $\boldsymbol{\Lambda}_1 = (5)$ , and $\widetilde{\boldsymbol{\Lambda}}_2 = \operatorname{diag}(\lambda_2(\widetilde{\mathbf{A}}), \lambda_3(\widetilde{\mathbf{A}}))$ . Since $\mathbf{E}\mathbf{e}_1 = (0, \tfrac12, 0)$ , $\sin\theta \le \frac{\left\| \mathbf{E}\mathbf{e}_1 \right\|}{\delta} = \frac{1/2}{3 - \sqrt2/2} \approx 0.218 .$ The gain over (b) comes from $\left\| \mathbf{E}\mathbf{e}_1 \right\| = \tfrac12$ replacing $\left\| \mathbf{E} \right\|_2 \approx 0.707$ . Since $\sin 13^\circ \approx 0.225 > 0.218$ and $\sin$ increases on $[0, \pi/2]$ , the angle is less than $13^\circ$ .
(d) $\widetilde{\mathbf{A}} - 2\mathbf{I} = \begin{psmallmatrix} 3 & 1/2 & 0 \\ 1/2 & 0 & 1/2 \\ 0 & 1/2 & -3 \end{psmallmatrix}$ sends $(1, -6, -1)$ to $(3 - 3,\ \tfrac12 - \tfrac12,\ -3 + 3) = \mathbf{0}$ , so $2$ is an eigenvalue. The other two have sum $\operatorname{tr}\widetilde{\mathbf{A}} - 2 = 4$ and product $\det\widetilde{\mathbf{A}}/2$ , where expanding along the first row gives $\det\widetilde{\mathbf{A}} = 5(-2 - \tfrac14) - \tfrac12(-\tfrac12) = -11$ . So they are the roots of $t^2 - 4t - \tfrac{11}{2}$ , namely $2 \pm \sqrt{19/2} \approx 5.082, -1.082$ . The exact separation of $\{2, 2 - \sqrt{19/2}\}$ from $5$ is $3$ , and the bound becomes $\tfrac{1/2}{3} = \tfrac16 \approx 0.167$ . (A direct computation of $\widetilde{\mathbf{x}}$ gives $\sin\theta \approx 0.163$ .)

Exercise (B2: Which theorem applies?)

In each case $\mathbf{A}$ and $\widetilde{\mathbf{A}}$ are Hermitian $4 \times 4$ matrices, $k = 2$ , $\boldsymbol{\Lambda}_1$ lists the eigenvalues of $\mathbf{A}$ belonging to $\mathbf{Q}_1$ , $\widetilde{\boldsymbol{\Lambda}}_2$ lists the eigenvalues of $\widetilde{\mathbf{A}}$ belonging to $\widetilde{\mathbf{Q}}_2$ , and $\left\| \mathbf{E}\mathbf{Q}_1 \right\|_2 = 0.2$ , $\left\| \mathbf{E}\mathbf{Q}_1 \right\|_F = 0.25$ . Determine which of Theorem 20.9.3 and Theorem 20.9.4 apply, and give the best bound on $\sin\theta_k$ that they yield. Justify your answer.

(a) $\boldsymbol{\Lambda}_1 = \operatorname{diag}(3, 2)$ , $\widetilde{\boldsymbol{\Lambda}}_2 = \operatorname{diag}(0.4, -1)$ .
(b) $\boldsymbol{\Lambda}_1 = \operatorname{diag}(3, 0)$ , $\widetilde{\boldsymbol{\Lambda}}_2 = \operatorname{diag}(1.9, 5)$ .
(c) $\boldsymbol{\Lambda}_1 = \operatorname{diag}(2, 1)$ , $\widetilde{\boldsymbol{\Lambda}}_2 = \operatorname{diag}(2, -1)$ .
(d) $\boldsymbol{\Lambda}_1 = \operatorname{diag}(-1, -2)$ , $\widetilde{\boldsymbol{\Lambda}}_2 = \operatorname{diag}(0.5, 4)$ .

Solution.

(a) Every eigenvalue in $\boldsymbol{\Lambda}_1$ is $\ge 2$ and both in $\widetilde{\boldsymbol{\Lambda}}_2$ are $\le 0.4 = 2 - 1.6$ . So case (i) of the one-sided theorem holds with $a = 2$ , $\delta = 1.6$ , and $\sin\theta_2 \le 0.2/1.6 = 0.125$ . The Frobenius theorem also applies, with the smallest of the four differences, $\delta = 2 - 0.4 = 1.6$ , but gives only $\sin\theta_2 \le \left\| \sin\Theta \right\|_F \le 0.25/1.6 \approx 0.156$ .
(b) The value $1.9$ lies between $0$ and $3$ , so no point has one list entirely above it and the other entirely below, and the one-sided theorem does not apply. The Frobenius theorem applies with $\delta = \min(1.1, 1.9, 2, 5) = 1.1$ , the four differences being $\lvert 1.9 - 3\rvert$ , $\lvert 1.9 - 0\rvert$ , $\lvert 5 - 3\rvert$ , and $\lvert 5 - 0\rvert$ . It gives $\sin\theta_2 \le \left\| \sin\Theta \right\|_F \le 0.25/1.1 \approx 0.227$ .
(c) $\lvert 2 - 2\rvert = 0$ , so no $\delta > 0$ exists and neither theorem applies. The check after Lemma 20.9.2 shows why nothing can be said in general: an eigenvalue of $\widetilde{\mathbf{A}}$ outside the subspace coincides with one of $\mathbf{A}$ inside it, and then the equation need not determine $\mathbf{X}$ .
(d) Every eigenvalue in $\boldsymbol{\Lambda}_1$ is $\le -1$ and both in $\widetilde{\boldsymbol{\Lambda}}_2$ are $\ge 0.5 = -1 + 1.5$ , so case (ii) holds with $a = -1$ and $\delta = 1.5$ : $\sin\theta_2 \le 0.2/1.5 \approx 0.133$ . The Frobenius theorem, with $\delta = 0.5 - (-1) = 1.5$ again, gives $0.25/1.5 \approx 0.167$ .

Exercise (B3: The same bounds for the projections)

In the setting of Theorem 20.9.3, let $U = \operatorname{col}(\mathbf{Q}_1)$ and $W = \operatorname{col}(\widetilde{\mathbf{Q}}_1)$ , with orthogonal projections $P_U$ and $P_W$ . Prove that $\left\| P_U - P_W \right\|_F \le \frac{\sqrt2\,\left\| \mathbf{E}\mathbf{Q}_1 \right\|_F}{\delta},$ and that under the hypotheses of Theorem 20.9.4, $\left\| P_U - P_W \right\|_2 \le \left\| \mathbf{E}\mathbf{Q}_1 \right\|_2/\delta$ .

Solution. Both subspaces have dimension $k$ , so Theorem 20.8.5 applies: $\left\| P_U - P_W \right\|_F = \sqrt2\,\left\| \sin\Theta \right\|_F$ and $\left\| P_U - P_W \right\|_2 = \sin\theta_k$ . By Theorem 20.9.3, $\sqrt2\,\left\| \sin\Theta \right\|_F \le \sqrt2\,\left\| \mathbf{E}\mathbf{Q}_1 \right\|_F/\delta$ , which is the first claim. By Theorem 20.9.4, $\sin\theta_k \le \left\| \mathbf{E}\mathbf{Q}_1 \right\|_2/\delta$ , which is the second.

C. Going deeper

Exercise (C1: A bound that needs only the perturbed matrix)

Let $\widetilde{\mathbf{A}} \in M_n(\mathbb{C})$ be Hermitian with $\widetilde{\mathbf{Q}} = \begin{pmatrix} \widetilde{\mathbf{Q}}_1 & \widetilde{\mathbf{Q}}_2 \end{pmatrix}$ and $\widetilde{\boldsymbol{\Lambda}}_2$ as in the text. Let $\mathbf{Z} \in M_{n \times k}(\mathbb{C})$ be any matrix with orthonormal columns, not necessarily eigenvectors of anything, and put $\mathbf{M} = \mathbf{Z}^{*}\widetilde{\mathbf{A}}\mathbf{Z} \in M_k(\mathbb{C}), \qquad \mathbf{R} = \widetilde{\mathbf{A}}\mathbf{Z} - \mathbf{Z}\mathbf{M} .$

(a) Prove that if every eigenvalue of the Hermitian matrix $\mathbf{M}$ differs from every diagonal entry of $\widetilde{\boldsymbol{\Lambda}}_2$ by at least $\delta > 0$ , then the principal angles between $\operatorname{col}(\mathbf{Z})$ and $\operatorname{col}(\widetilde{\mathbf{Q}}_1)$ satisfy $\left\| \sin\Theta \right\|_F \le \left\| \mathbf{R} \right\|_F/\delta$ .
(b) Deduce: let $\lambda_i(\widetilde{\mathbf{A}})$ be a simple eigenvalue of $\widetilde{\mathbf{A}}$ , let $\mathbf{z}$ be a unit vector, $\mu = \mathbf{z}^{*}\widetilde{\mathbf{A}}\mathbf{z}$ , and $\mathbf{r} = \widetilde{\mathbf{A}}\mathbf{z} - \mu\mathbf{z}$ . If every eigenvalue of $\widetilde{\mathbf{A}}$ other than $\lambda_i(\widetilde{\mathbf{A}})$ lies at distance at least $\delta$ from $\mu$ , then a unit eigenvector $\widetilde{\mathbf{x}}$ for $\lambda_i(\widetilde{\mathbf{A}})$ satisfies $\sin\theta(\mathbf{z}, \widetilde{\mathbf{x}}) \le \left\| \mathbf{r} \right\|/\delta$ .

Hint: diagonalize $\mathbf{M}$ and compute $\widetilde{\mathbf{Q}}_2^{*}\mathbf{R}$ in two ways.

Solution.

(a) $\mathbf{M}^{*} = \mathbf{Z}^{*}\widetilde{\mathbf{A}}^{*}\mathbf{Z} = \mathbf{M}$ , so by Corollary 12.4.3 and Theorem 12.2.1, $\mathbf{M} = \mathbf{V}\mathbf{D}\mathbf{V}^{*}$ with $\mathbf{V} \in M_k(\mathbb{C})$ unitary and $\mathbf{D}$ real diagonal, holding the eigenvalues of $\mathbf{M}$ . Put $\mathbf{Z}' = \mathbf{Z}\mathbf{V}$ , which has orthonormal columns, since $\mathbf{Z}'^{*}\mathbf{Z}' = \mathbf{V}^{*}\mathbf{V} = \mathbf{I}_k$ , and the same column space as $\mathbf{Z}$ , since $\mathbf{V}$ is invertible. Then $\mathbf{R}\mathbf{V} = \widetilde{\mathbf{A}}\mathbf{Z}' - \mathbf{Z}\mathbf{V}\mathbf{D} = \widetilde{\mathbf{A}}\mathbf{Z}' - \mathbf{Z}'\mathbf{D}$ . As in the proof of Lemma 20.9.2, $\widetilde{\mathbf{Q}}_2^{*}\widetilde{\mathbf{A}} = \widetilde{\boldsymbol{\Lambda}}_2\widetilde{\mathbf{Q}}_2^{*}$ , so with $\mathbf{X}' = \widetilde{\mathbf{Q}}_2^{*}\mathbf{Z}'$ , $\widetilde{\mathbf{Q}}_2^{*}\mathbf{R}\mathbf{V} = \widetilde{\boldsymbol{\Lambda}}_2\mathbf{X}' - \mathbf{X}'\mathbf{D} .$ Both coefficient matrices are real diagonal, hence normal, and their diagonal entries differ by at least $\delta$ , so, as in the proof of Theorem 20.9.3, Theorem 20.7.2 and Proposition 20.7.1 (d) give $\left\| \mathbf{X}' \right\|_F \le \left\| \widetilde{\mathbf{Q}}_2^{*}\mathbf{R}\mathbf{V} \right\|_F/\delta$ . By Lemma 20.9.1 (c), $\left\| \widetilde{\mathbf{Q}}_2^{*}\mathbf{R}\mathbf{V} \right\|_F \le \left\| \mathbf{R}\mathbf{V} \right\|_F = \left\| \mathbf{R} \right\|_F$ . Finally, by Theorem 20.8.4 applied as in Lemma 20.9.2, with $\operatorname{col}(\mathbf{Z}') = \operatorname{col}(\mathbf{Z})$ in place of $\operatorname{col}(\mathbf{Q}_1)$ , $\left\| \mathbf{X}' \right\|_F = \left\| \sin\Theta \right\|_F$ . This proves (a).
(b) Take $k = 1$ and $\mathbf{Z} = \mathbf{z}$ . Then $\mathbf{M} = (\mu)$ , $\mathbf{R} = \mathbf{r}$ , and the only eigenvalue of $\mathbf{M}$ is $\mu$ . Since $\lambda_i(\widetilde{\mathbf{A}})$ is simple, its eigenspace is the line $\operatorname{span}(\widetilde{\mathbf{x}})$ , so we may choose $\widetilde{\mathbf{Q}}$ with first column $\widetilde{\mathbf{x}}$ and $\widetilde{\boldsymbol{\Lambda}}_2$ holding the other eigenvalues of $\widetilde{\mathbf{A}}$ , as in the proof of Corollary 20.9.5. Part (a) gives $\sin\theta(\mathbf{z}, \widetilde{\mathbf{x}}) \le \left\| \mathbf{r} \right\|/\delta$ . This is the eigenvector companion of a residual bound: everything on the right is computable from $\mathbf{z}$ and $\widetilde{\mathbf{A}}$ and a gap estimate, with no unperturbed matrix in sight.

Exercise (C2: The constant in the eigenvector bound is sharp)

Let $g > 0$ and $e > 0$ , and let $\mathbf{A} = \operatorname{diag}(g, 0)$ , $\mathbf{E} = e\begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ .

(a) Show that a unit eigenvector $\widetilde{\mathbf{x}}$ of $\mathbf{A} + \mathbf{E}$ for its larger eigenvalue makes an angle $\theta \in [0, \pi/4)$ with $\mathbf{e}_1$ satisfying $\tan 2\theta = 2e/g$ .
(b) Deduce that $\sin\theta \cdot g/e \to 1$ as $e \to 0^{+}$ .
(c) Hence show that for no constant $c < 1$ is it true that $\sin\theta(\mathbf{x}, \widetilde{\mathbf{x}}) \le c\,\left\| \mathbf{E} \right\|_2/\gamma$ for all sufficiently small Hermitian $\mathbf{E}$ , in the setting of Corollary 20.9.5.

Solution.

(a) The larger eigenvalue of $\widetilde{\mathbf{A}} = \begin{psmallmatrix} g & e \\ e & 0 \end{psmallmatrix}$ is $\lambda_+ = h + s$ , where $h = g/2$ and $s = \sqrt{h^2 + e^2}$ . The first row of $\widetilde{\mathbf{A}} - \lambda_+\mathbf{I}$ is $(g - \lambda_+, e) = (h - s, e)$ , so $(e, s - h)$ spans the eigenline, and $s - h > 0$ . The angle with $\mathbf{e}_1$ therefore satisfies $\tan\theta = t \mathrel{:=} (s - h)/e > 0$ . Using $s^2 = h^2 + e^2$ , $1 - t^2 = \frac{e^2 - (s - h)^2}{e^2} = \frac{2h(s - h)}{e^2} > 0 ,$ so $t < 1$ , that is $\theta < \pi/4$ , and $\begin{aligned} \tan 2\theta = \frac{2t}{1 - t^2} &= \frac{2(s - h)}{e}\cdot\frac{e^2}{2h(s - h)} \\ &= \frac{e}{h} = \frac{2e}{g} . \end{aligned}$
(b) From (a), $\cos 2\theta = 1/\sqrt{1 + \tan^2 2\theta} = g/\sqrt{g^2 + 4e^2}$ , since $2\theta \in [0, \pi/2)$ . Hence $\begin{aligned} \sin^2\theta = \frac{1 - \cos 2\theta}{2} &= \frac{\sqrt{g^2 + 4e^2} - g}{2\sqrt{g^2 + 4e^2}} \\ &= \frac{2e^2}{\sqrt{g^2 + 4e^2}\,\bigl(\sqrt{g^2 + 4e^2} + g\bigr)} , \end{aligned}$ multiplying above and below by $\sqrt{g^2 + 4e^2} + g$ . So $\Bigl(\frac{g\sin\theta}{e}\Bigr)^2 = \frac{2g^2}{\sqrt{g^2 + 4e^2}\,\bigl(\sqrt{g^2 + 4e^2} + g\bigr)} ,$ which tends to $2g^2/(g \cdot 2g) = 1$ as $e \to 0^{+}$ , by continuity of the square root.
(c) Here $\mathbf{x} = \mathbf{e}_1$ , $\gamma = g$ , and $\left\| \mathbf{E} \right\|_2 = e$ , since $\mathbf{E}/e$ is Hermitian with eigenvalues $\pm1$ . If $\sin\theta \le c\,e/g$ held for all small $e > 0$ with some $c < 1$ , then $\sin\theta \cdot g/e \le c$ for those $e$ , contradicting (b). So to first order in $\left\| \mathbf{E} \right\|_2$ , the bound $\left\| \mathbf{E} \right\|_2/(\gamma - \left\| \mathbf{E} \right\|_2)$ of Corollary 20.9.5 cannot be improved by any constant factor.

20.9.1. Eigenvectors can move a long way

20.9.2. Two norms, three facts

20.9.3. The perturbation of a subspace is a Sylvester equation

20.9.4. The sin⁡Θ theorem in the Frobenius norm

20.9.5. A one-sided version in the spectral norm

20.9.6. Single eigenvectors

20.9.7. Clusters: the subspace is stable when the vectors are not

20.9.8. Exercises

A. Check your understanding

B. Practice

C. Going deeper

20.9.4. The $\sin\Theta$ theorem in the Frobenius norm