Variational Principles and Interlacing

Since Chapter 13 the book has written ${\lambda }_1(\mathbf{A})\ge \cdots \ge {\lambda }_n(\mathbf{A})$ for the eigenvalues of a Hermitian matrix without ever saying what the middle ones are. The two at the ends have an answer. Chapter 11 observed that $⟨Tv,v⟩$ is real for a self-adjoint operator, and Chapter 13 §05 turned that into Lemma 13.5.2: on the unit sphere, $⟨\mathbf{A}\mathbf{x},\mathbf{x}⟩$ runs from ${\lambda }_n(\mathbf{A})$ up to ${\lambda }_1(\mathbf{A})$, and both ends are attained at eigenvectors. Everything between the ends was left blank, twice and deliberately. Chapter 13 §05 said it in one sentence: the intermediate eigenvalues “have no description as a plain maximum over the whole unit sphere”. Chapter 13 §13 said where the blank would be filled: “Chapter 17 characterizes the eigenvalues of a Hermitian matrix as maxima and minima of $⟨\mathbf{A}\mathbf{x},\mathbf{x}⟩$ — at which point the test becomes the theory.”

This is that chapter, and the device that fills the blank is a min–max. One maximum over the unit sphere is not enough information to see ${\lambda }_2$; a maximum over a subspace, followed by a minimum over all subspaces of the right dimension, is exactly enough. That is the Courant–Fischer theorem, and its proof is one dimension count repeated: two subspaces of $F^n$ whose dimensions add to more than $n$ must share a nonzero vector. Once every eigenvalue is a maximum and a minimum of a quantity that does not mention an eigenvector, eigenvalues of different matrices become comparable, and the rest of the chapter is the harvest. How far the eigenvalues move when the matrix moves (Weyl). How they move when a row and its column are deleted, or a rank-one matrix is added (Cauchy interlacing, and the secular equation). What sums of the largest eigenvalues optimize (Poincaré, Ky Fan), and what arbitrary index sets do (Wielandt, Lidskii). What the diagonal of a Hermitian matrix can be, given its spectrum (Schur). The same theory for singular values, which finally proves the approximation theorem Chapter 13 §11 could only state. Inertia, re-proved without a basis and then made additive across a Schur complement. And a first look at which scalar functions respect the Loewner order.

Every matrix whose eigenvalues are indexed in this chapter is Hermitian, and the field is $\mathbb{R}$ or $\mathbb{C}$. This is not a convenience. The index $i$ in ${\lambda }_i(\mathbf{A})$ presupposes that the eigenvalues are real and can be sorted, which is Theorem 12.2.1, and every eigenvalue inequality below is false without it — §04 exhibits a non-Hermitian matrix with a $1\times 1$ principal submatrix lying outside the convex hull of the whole matrix’s spectrum. Each section states the hypothesis once and keeps it.

Eigenvalues are indexed decreasingly, ${\lambda }_1(\mathbf{A})\ge {\lambda }_2(\mathbf{A})\ge \cdots \ge {\lambda }_n(\mathbf{A})$, repeated according to multiplicity, as Chapter 13 §05 fixed it. Many sources index the min–max theorem the other way, and the two statements differ by $i\leftrightarrow n+1-i$; §02 gives the increasing form once, as a remark, so that a reader who meets it elsewhere is not lost.

The analysis this chapter imports

None that is new. Chapter 16 named everything it borrowed from analysis in a numbered list (A1)–(A6) in its introduction, and this chapter uses that list and nothing else, citing an item by the same name at the point of use — “by the extreme value theorem, fact (A4) of Chapter 16’s introduction”. Compactness of the unit sphere (A3) and the extreme value theorem (A4) are the two that a reader will expect to see, since a min–max is an optimization and optimizations need their extrema to exist.

It is worth saying in advance that the expectation is not always met. In §§01–02, where the maxima and minima are first written down, no analytic fact is invoked: the spectral theorem is already available, and it hands over a maximizer explicitly, so the extreme value theorem is never called on to prove that one exists. That is not the same as saying no analysis lies underneath. The spectral theorem rests on the fundamental theorem of algebra, and Chapter 6 §05 proves that with the extreme value theorem on a closed disc; the analysis was paid for there, once, and is not paid again here. Chapter 12 §02 avoided that theorem on purpose and said so; §§01–02 below return to the remark and settle the account. Where a later section does need an item of the list, it names it. Nothing is added to the list.

What you need

• Chapter 0 §09 — the trace and its cyclic invariance, which §§05 and 06 compute with: Theorem 0.9.6.
• Chapter 1 §07 — the dimension formula $\dim (U+W)=\dim U+\dim W-\dim (U\cap W)$, Theorem 1.7.3. It is the engine of every min–max proof in the chapter, and §02 packages it as a lemma.
• Chapter 3 §04 and §05 — permutation matrices, which §08 uses to put a spectrum in order, and Rank–Nullity for matrices, which §09 counts singular values with: Definition 3.4.2, Lemma 3.4.7, Theorem 3.5.7.
• Chapter 2 — the coordinate isomorphism and what it preserves, and Rank–Nullity, which §§07 and 10 count with: Corollary 2.5.5, Theorem 2.5.2, Theorem 2.3.1.
• Chapter 4 — the matrix of a map read through coordinates, which is how §02 passes between an operator and its matrix: Theorem 4.1.1.
• Chapter 6 §01 — one fact, in §04: a nonzero polynomial of degree at most $n$ has at most $n$ roots, which is how the bordered-determinant identity passes from all but finitely many scalars to every scalar: Corollary 6.1.4.
• Chapter 7 and Chapter 8 — principal submatrices (Definition 7.7.1) and Schur complements: Definition 8.3.1, Theorem 8.3.2, Theorem 8.3.1, Corollary 8.3.6. §§04, 05, and 10 lean on them.
• Chapter 9 — the trace and determinant as sum and product of the eigenvalues, Theorem 9.3.3.
• Chapter 11 — inner products, orthonormal bases, and the adjoint: Definition 11.1.1, Definition 11.1.3, Theorem 11.1.5, Theorem 11.2.1, Definition 11.3.1, Theorem 11.3.2, Corollary 11.2.3, Definition 11.6.2, Theorem 11.6.3, Proposition 11.6.7.
• Chapter 12 — the spectral theorems, in both the operator and the matrix form: Theorem 12.2.1, Theorem 12.4.2, Corollary 12.4.3, Theorem 12.5.1, Corollary 12.5.2, Corollary 12.5.4, and the functional calculus Definition 12.8.2, Theorem 12.8.3.
• Chapter 13 — positivity, the Loewner order, and the singular value decomposition: Definition 13.1.1, Theorem 13.1.4, Theorem 13.1.5, Theorem 13.2.1, Definition 13.5.1, Proposition 13.5.1, Lemma 13.5.2, Theorem 13.5.3, Proposition 13.5.4, Definition 13.9.1, Theorem 13.9.1, Theorem 13.9.3, Definition 13.11.1, Lemma 13.11.2, Theorem 13.11.3; from §04 the generalized eigenvalues (Definition 13.4.1, Theorem 13.4.2), and from §06 Hadamard’s inequality and the block criterion (Theorem 13.7.3, Theorem 13.6.1), each of which gets a second proof here.
• Chapter 14 §§02, 05 — congruence (Definition 14.2.1), inertia, and signature: Theorem 14.5.1, Definition 14.5.1, Theorem 14.5.3. This one is a connection rather than a prerequisite: §10 gives Sylvester’s law a second proof and reworks its examples, and no proof in the chapter cites Chapter 14 — one worked example and two exercises of §10 do.
• Chapter 16 — the way a matrix is measured, and the questions left open: Definition 16.3.2, Theorem 16.3.2, and Theorem 16.3.3, whose part (c) is the formula ${\Vert \mathbf{A}\Vert }_2={\sigma }_1(\mathbf{A})$; then Definition 16.4.1, Theorem 16.4.1, Definition 16.8.1, and the imported-analysis list of the Chapter 16 introduction.

Roadmap

• The Rayleigh quotient. $R_{\mathbf{A}}(\mathbf{x})=⟨\mathbf{A}\mathbf{x},\mathbf{x}⟩/⟨\mathbf{x},\mathbf{x}⟩$ promoted from a test to an object: its range is exactly $[{\lambda }_n,{\lambda }_1]$, its critical points on the unit sphere are exactly the unit eigenvectors, and the first description of ${\lambda }_k$ — maximize after deflating by the top eigenvectors — is correct but circular.
• The min–max theorem. Courant–Fischer: ${\lambda }_k$ is a minimum over subspaces of a maximum over vectors, and equally a maximum over subspaces of a minimum. No eigenvector is named, so two matrices can now be compared eigenvalue by eigenvalue.
• How far eigenvalues move. Weyl’s inequalities, and the Lipschitz bound $|{\lambda }_i(\mathbf{A}+\mathbf{E})-{\lambda }_i(\mathbf{A})|\le {\Vert \mathbf{E}\Vert }_2$ that Chapter 16 §07 promised.
• Deleting a row and a column. Cauchy interlacing: the spectrum of a principal submatrix is caught between consecutive eigenvalues of the whole matrix. When the interlacing is strict, which settles a promise of Chapter 11: the zeros of consecutive orthogonal polynomials interlace strictly. And why none of it survives without symmetry.
• Adding a rank-one matrix. Interlacing again, the secular equation that locates the new eigenvalues between the old, and the shifts that add up to $\tau {\Vert \mathbf{v}\Vert }^2$.
• Subspaces and sums. Poincaré’s separation theorem, and Ky Fan’s: the sum of the $k$ largest eigenvalues is a maximum of a trace over orthonormal $k$-frames, hence a convex function of the matrix. Chapter 13’s capture bound turns out to be one case of it.
• Arbitrary index sets. The Wielandt min–max over a flag of subspaces, and Lidskii’s inequality. It contains Ky Fan’s subadditivity and the Weyl inequalities with one index at an end — but not all of Weyl’s, which is worth seeing.
• The diagonal and the spectrum. Majorization; Schur’s theorem and Horn’s converse, which together say that the diagonals of the Hermitian matrices with a given spectrum are exactly the vectors that spectrum majorizes.
• The same theory for singular values. The min–max for ${\sigma }_k$, perturbation with no hypothesis on the perturbation at all, the spectral-norm form of Eckart–Young, interlacing when a row or column is deleted, and the distance from an invertible matrix to the nearest singular one — which is what Chapter 16’s condition number was measuring all along.
• Inertia, again and additively. A second proof of Sylvester’s law with no basis in it, now over $\mathbb{C}$ as well; how far a rank-$r$ perturbation can move the inertia; and Haynsworth’s additivity across a Schur complement.
• Which functions respect the order. Operator monotone and operator convex functions, why the square root behaves and the square does not, and a statement of the classification that Chapter 21 proves.

Named moves

• Count dimensions to force an intersection. Two subspaces of an $n$-dimensional space whose dimensions add to more than $n$ meet in a nonzero vector. This one line proves Courant–Fischer and Weyl directly, and Cauchy interlacing and Poincaré through Courant–Fischer. It is the chapter’s single technique, and everything else is bookkeeping around it.
• Prove a min–max by two inequalities of different characters. One direction exhibits a witness subspace — usually a span of eigenvectors — and computes on it. The other takes an arbitrary subspace and intersects it with a span of eigenvectors from the other end. Neither half resembles the other, and recognizing which half is which is most of the work in reading any proof below.
• Apply the result to $-\mathbf{A}$. The two halves of Courant–Fischer, the two families of Weyl inequalities, and the top- and bottom-$k$ trace theorems are each other’s images under $\mathbf{A}\mapsto -\mathbf{A}$, which reverses the order and sends ${\lambda }_i$ to $-{\lambda }_{n+1-i}$. Deriving the second statement this way is a genuine argument, not a wave of the hand, and it is written out each time.
• Compress, then interlace. Restricting the quadratic form to a subspace produces a smaller Hermitian matrix whose eigenvalues are trapped by the original’s. Deleting rows and columns, adding a rank-one matrix, and cutting a singular value decomposition short are all this move.
• Perturb and compare, eigenvalue by eigenvalue. Chapter 16’s move, now applied one index at a time rather than to the spectrum as a whole.
• Reduce singular values to eigenvalues. Either through ${\mathbf{A}}^{\ast }\mathbf{A}$, which is shortest, or through the Hermitian dilation, which is symmetric in $\mathbf{A}$ and ${\mathbf{A}}^{\ast }$. Both appear, and each section says which it uses and why.
• Majorize. When the right comparison is between sums of the largest entries rather than individual ones, compare the partial sums of the decreasing rearrangements. The diagonal of a Hermitian matrix against its spectrum (§08), and the Ky Fan and Lidskii sums (§§06–07), are all of this type.