Perturbation Theory

Every matrix that comes from a measurement or a computation is slightly wrong, so the eigenvalues one actually knows are those of a nearby matrix $\mathbf{A}+\mathbf{E}$. Two earlier chapters began to say what that costs. Chapter 16 showed that the eigenvalues move continuously with the matrix (Corollary 16.7.4), and that “continuously” can be very bad: a perturbation of size $\epsilon$ moves the eigenvalue of a $k\times k$ Jordan block by ${\epsilon }^{1/k}$ (Example (A Jordan block’s eigenvalues move like ${\epsilon }^{1/k}$)). Chapter 17 showed that Hermitian matrices are as good as one could hope: each eigenvalue moves by at most ${\Vert \mathbf{E}\Vert }_2$ (Corollary 17.3.6). Most matrices are neither Jordan blocks nor Hermitian, and this chapter handles them. It asks four questions.

• Where are the eigenvalues, before any of them is computed? Discs and ovals read off the entries, and the numerical range, locate them.
• How far do they move when $\mathbf{A}$ is not Hermitian? For every matrix there is a bound with an $n$-th root, and the Jordan block shows that the root cannot be removed. For a diagonalizable matrix, the Bauer–Fike theorem gives a bound proportional to $\Vert \mathbf{E}\Vert$, with a factor that measures how far the eigenvectors are from orthonormal.
• Which eigenvalue goes where? A bound saying that each new eigenvalue is near some old one does not say that they can be paired off. For normal matrices they can, and the pairing comes from Birkhoff’s theorem of Chapter 19.
• What happens to the rest? Eigenvectors and invariant subspaces, singular values, and the factors of the polar decomposition all move, and the chapter bounds each of them. It ends with the first-order sensitivity of a single simple eigenvalue.

One result settles an old account. Chapter 16 quoted the theorem that the roots of a polynomial depend continuously on its coefficients (Theorem 16.7.3) and left the proof to this chapter. §03 gives it from compactness and unique factorization alone, so Corollary 16.7.4, and everything Chapter 16 built on it, now rests on a proved theorem.

The field is $\mathbb{C}$ throughout, unless a statement says $\mathbb{R}$. A real matrix is read in $M_n(\mathbb{C})$ when its eigenvalues are wanted. Three conventions hold in every section.

• The perturbation is $\mathbf{E}$, and the perturbed matrix is $\mathbf{A}+\mathbf{E}$, as in Chapters 16 and 17. A different letter, $\tilde{\mathbf{A}}$, is used only where the perturbed matrix is not naturally written as a sum.
• Every bound names its norm. ${\Vert \cdot \Vert }_2$ is the spectral norm and ${\Vert \cdot \Vert }_F$ the Frobenius norm. A norm without a subscript means an arbitrary operator norm, and it is written that way only where the statement holds for all of them. There is one other use, announced where it starts: in §§09–10 a norm without a subscript stands for either the spectral or the Frobenius norm, the same one throughout the statement, and there it ranges over just those two.
• Near some eigenvalue is not the same as matched. “Every eigenvalue of $\mathbf{A}+\mathbf{E}$ lies within $r$ of some eigenvalue of $\mathbf{A}$” is a one-sided statement. “The eigenvalues can be numbered so that each pair is within $r$” is a matching, and it is stronger. §§03–05 are largely about the difference, and the chapter never blurs it.

The analysis this chapter imports

The list is Chapter 16’s, facts (A1)–(A6) of that chapter’s introduction, together with the algebra of limits, and each fact is named again where it is used. Two carry most of the weight. (A3), compactness of closed bounded sets, is the engine of §03’s proof of the continuity of roots, and it is also what makes the numerical range of §02 compact. (A5), the intermediate value theorem, gives the convexity of the numerical range in §02. (A4), the extreme value theorem, is used once, also in §02, to know that the numerical radius — the largest modulus on the numerical range — is attained. §03’s counting theorem needs one more fact, that an integer-valued function on an interval that is locally constant is constant, and it derives this from (A5) as well. Nothing else analytic is used. In particular, the first-order formula of §11 for the derivative of a simple eigenvalue is proved without the implicit function theorem.

What you need

• Chapter 0 §06 and §09 — the triangle inequality for complex numbers, which is the first move of nearly every estimate in the chapter (§§01, 02, 03, 09 and 11), and the trace, which §08 computes with: Theorem 0.6.4, Theorem 0.9.6.
• Chapter 1 §06 — basis extension, once, in §11, to turn an eigenvector into the first column of an invertible matrix: Theorem 1.6.5.
• Chapter 3 §05 and §07 — Rank–Nullity for matrices and the factor theorem, both in §11: Theorem 3.5.7, Lemma 3.7.1.
• Chapter 4 §05 — that a projection’s image is the subspace it projects onto, which is what lets §08 compare two subspaces by comparing their projections: Theorem 4.5.1.
• Chapter 6 — polynomials over $\mathbb{C}$: Corollary 6.5.5, Theorem 6.3.5, Theorem 6.4.5.
• Chapter 7 — determinants, the adjugate and minors: Definition 7.6.2, Theorem 7.6.2, Theorem 7.7.1, Theorem 7.10.2, Theorem 7.10.4, Theorem 7.8.4.
• Chapter 8 — block matrices and the Kronecker and vec identities: Theorem 8.1.1, Theorem 8.4.4.
• Chapter 9 — eigenvalues, multiplicities, diagonalization and left eigenvectors: Theorem 9.2.1, Definition 9.3.1, Theorem 9.3.1, Definition 9.4.1, Theorem 9.4.1, Definition 9.10.1, Proposition 9.10.5, Proposition 9.10.7.
• Chapter 10 — the Jordan form, and its warning that the form is unstable: Theorem 10.3.1, Definition 10.3.1. Here the Jordan form is the thing being measured rather than a tool: §§04 and 11 discuss it in the text and pay off Chapter 10’s promise, and no proof in the chapter cites it.
• Chapter 11 — inner products, orthogonal projections, unitary maps and the unitary invariance of the Frobenius norm: Theorem 11.1.5, Definition 11.3.2, Theorem 11.3.2, Corollary 11.2.3, Theorem 11.7.3, Lemma 11.7.5.
• Chapter 12 — Schur’s theorem, the spectral theorem, the Sylvester equation and the departure from normality: Theorem 12.1.2, Corollary 12.4.3, Theorem 12.3.3, Definition 12.10.1, Theorem 12.10.2, Corollary 12.10.3, Definition 12.11.1, Example (A perturbation that moves the eigenvalues a thousand times as far).
• Chapter 13 — the singular value and polar decompositions, and Hadamard’s inequality: Theorem 13.8.1, Definition 13.8.1, Theorem 13.9.1, Theorem 13.6.4.
• Chapter 16 — operator norms, the Neumann series, continuity of eigenvalues and condition numbers: Definition 16.3.2, Theorem 16.3.2, Theorem 16.3.3, Theorem 16.5.1, Lemma 16.7.1, Theorem 16.7.3, Corollary 16.7.4, Example (A Jordan block’s eigenvalues move like ${\epsilon }^{1/k}$), Definition 16.8.1.
• Chapter 17 — the Rayleigh quotient, Weyl’s inequalities, Lidskii’s inequality, majorization, the Hermitian dilation, and §10’s law of inertia for Hermitian matrices: Definition 17.1.1, Theorem 17.2.3, Theorem 17.3.3, Corollary 17.3.6, Theorem 17.7.2, Definition 17.8.1, Proposition 17.9.3, Corollary 17.9.5, Definition 17.10.1, Theorem 17.10.1.
• Chapter 18 — extreme points, and linear functions on compact convex sets: Definition 18.8.1, Corollary 18.8.6.
• Chapter 19 — irreducible matrices, and Birkhoff’s theorem: Definition 19.2.3, Theorem 19.2.5, Theorem 19.7.2.

Roadmap

• Gershgorin discs. Every eigenvalue lies in a union of discs read off the rows, a diagonal rescaling moves the discs, and an irreducible matrix can have an eigenvalue on the boundary only if it lies on every circle.
• Other inclusion regions. Brauer’s ovals, which are never worse than the discs, and the numerical range: it contains the spectrum, it is convex by the Toeplitz–Hausdorff theorem, and it equals the convex hull of the eigenvalues for a normal matrix.
• Continuity of roots. Chapter 16’s quoted theorem, proved by compactness. Elsner’s bound, with its exponent $1/n$ shown to be sharp by a Jordan block, and its matching version. The counting theorem: a group of Gershgorin discs separated from the others contains exactly as many eigenvalues as discs.
• The Bauer–Fike theorem. For a diagonalizable matrix, each perturbed eigenvalue lies within ${\kappa }_2(\mathbf{X}){\Vert \mathbf{E}\Vert }_2$ of an old one, with factor $1$ for a normal matrix. It comes with a residual bound for computed eigenpairs and a version with an $m$-th root for defective matrices.
• The Hoffman–Wielandt theorem. The eigenvalues of two normal matrices can be matched within their Frobenius distance, by Birkhoff’s theorem. The inequality fails for non-normal matrices.
• Hermitian perturbations. Residual bounds, the Kato–Temple bound, which is quadratic in the residual, and Ostrowski’s theorem, which says that a congruence changes each eigenvalue by a bounded relative factor.
• The Sylvester equation, quantitatively. The separation of two matrices, which measures how badly conditioned $\mathbf{A}\mathbf{X}-\mathbf{X}\mathbf{B}=\mathbf{Y}$ is. For normal matrices it is the distance between the spectra, and in general it can be much smaller. Bounds for separated Hermitian spectra follow.
• Principal angles. The angles between two subspaces, their sines, and the distance ${\Vert P_U-P_W\Vert }_2$ between the orthogonal projections.
• The Davis–Kahan theorem. An invariant subspace of a Hermitian matrix moves by at most the perturbation divided by the spectral gap. Single eigenvectors inside a cluster may not be stable, but the subspace of the whole cluster is.
• Singular values and polar factors. Mirsky’s Frobenius bound for singular values, and bounds for the positive and the unitary factors of the polar decomposition of an invertible matrix.
• Condition numbers of eigenvalues. The derivative of a simple eigenvalue, from a right and a left eigenvector, and its worst size, which is the condition number. The chapter’s summary closes this section.

Named moves

• Dominant coordinate plus the triangle inequality. Read the eigen-equation at the coordinate where the eigenvector is largest.
• A determinant bounded two ways. A product of distances to the eigenvalues is a determinant, and Hadamard’s inequality bounds it by column lengths.
• Compactness plus uniqueness. Bound the roots, extract a convergent subsequence, and let unique factorization identify the limit.
• An integer-valued continuous function is constant. Count eigenvalues along a path on which none of them can escape the region.
• Factor out the resolvent. Write $\mathbf{A}+\mathbf{E}-\mu \mathbf{I}=(\mathbf{A}-\mu \mathbf{I})(\mathbf{I}+(\mathbf{A}-\mu \mathbf{I}{)}^{-1}\mathbf{E})$ and invert the second factor by the Neumann series.
• Birkhoff turns a doubly stochastic weight into a permutation. Minimize a linear function over the doubly stochastic matrices, and the minimum sits at a permutation.
• The perturbation of a subspace is a Sylvester equation. The block coupling an invariant subspace to the new complement solves one, so the spectral gap is the conditioning.
• The singular-pair trick. Test a matrix equation against the top singular pair of the unknown.
• The adjugate as a polynomial eigenvector. A column of $\mathrm{adj}(\mu \mathbf{I}-\mathbf{B})$ is an eigenvector whose entries are polynomials, so it moves continuously with the data.