The Courant-Fischer Min-Max Theorem: Eigenvalues as Optimization Problems

The precise statement

Let A be a real symmetric (or complex Hermitian) n×n matrix. By the spectral theorem its eigenvalues are real; order them λ₁ ≤ λ₂ ≤ ⋯ ≤ λₙ (with multiplicity). Define the Rayleigh quotient R(x) = xᵀAx / xᵀx for x ≠ 0 (use x*Ax / x*x in the complex case). The Courant-Fischer theorem states, for each k = 1,…,n:

• Min-max: λₖ = min over all k-dimensional subspaces V ⊆ ℝⁿ of ( max over x ∈ V, x ≠ 0 of R(x) ).
• Max-min (dual): λₖ = max over all (n−k+1)-dimensional subspaces V of ( min over x ∈ V, x ≠ 0 of R(x) ).

Crucially the extrema are attained: the outer min in the first form is achieved by V = span(v₁,…,vₖ), where vⱼ is a unit eigenvector for λⱼ. The special cases k = 1 and k = n recover the classical Rayleigh principle λ₁ = min R and λₙ = max R. Note the definiteness of A is not assumed — eigenvalues may be negative; only self-adjointness matters.

The geometric picture

Diagonalize A in an orthonormal eigenbasis, so that in coordinates y = (y₁,…,yₙ) the quadratic form becomes R(y) = (λ₁y₁² + ⋯ + λₙyₙ²) / (y₁² + ⋯ + yₙ²). The Rayleigh quotient is thus a weighted average of the eigenvalues, with weights yⱼ²/‖y‖² summing to 1. So R(x) always lies between λ₁ and λₙ, and it equals λⱼ exactly along the eigendirection vⱼ.

Now picture choosing a k-dimensional subspace V. On V the quotient ranges over some band of values; its maximum is at least λₖ, because a k-dimensional V must contain a nonzero vector orthogonal to the (k−1)-dimensional span of v₁,…,vₖ₋₁ — and any such vector, being a mix of eigendirections k through n, has R ≥ λₖ. The magic is that this floor is achieved by the flattest possible choice of V, namely span(v₁,…,vₖ), on which R never exceeds λₖ. Min-max = tilt the subspace to hold its worst-case value as low as possible.

The key idea of the proof

The whole argument rests on one dimension-counting fact: in ℝⁿ, a subspace of dimension k and a subspace of dimension n−k+1 have dimensions summing to n+1 > n, so they must intersect in a nonzero vector.

Fix any k-dimensional subspace V. Let W = span(vₖ, vₖ₊₁,…,vₙ), which has dimension n−k+1. Since dim V + dim W = n+1, there is a nonzero z ∈ V ∩ W. Because z lies in W, it is a combination of eigenvectors with eigenvalues ≥ λₖ, so R(z) ≥ λₖ. Hence max over V of R is ≥ λₖ — for every V. This proves

• min over V of (max over V of R) ≥ λₖ.

For the reverse inequality, exhibit the optimal subspace: take V₀ = span(v₁,…,vₖ). Every unit x ∈ V₀ is a combination of eigenvectors with eigenvalues ≤ λₖ, so R(x) ≤ λₖ, giving max over V₀ of R = λₖ. Combining the two bounds forces equality. The max-min form follows by the same argument applied to −A, which flips the order of the eigenvalues.

A worked example

Take the 3×3 symmetric matrix with the eigenvalues built in via a diagonal A = diag(2, 5, 9), so λ₁ = 2, λ₂ = 5, λ₃ = 9 and eigenvectors e₁, e₂, e₃. Then R(x) = (2x₁² + 5x₂² + 9x₃²)/(x₁² + x₂² + x₃²).

• k = 1: min R over all x is 2, at x = e₁. ✓
• k = 3: max R is 9, at x = e₃. ✓
• k = 2 (the interesting one): pick the plane V = span(e₁, e₂). On it R = (2x₁²+5x₂²)/(x₁²+x₂²) ≤ 5, with max 5 at e₂. Any other 2-plane must contain a vector with a nonzero e₃-component (since it meets span(e₂,e₃)), pushing its max above 5. So the min over 2-planes of the max of R is exactly λ₂ = 5.

Notice you never had to compute a characteristic polynomial: the eigenvalue popped out as the solution of a nested min-max. This is precisely how iterative eigensolvers (Lanczos, LOBPCG) locate interior eigenvalues.

Why self-adjointness matters — and what it unlocks

The theorem lives or dies on A being self-adjoint. If A is not symmetric, its eigenvalues can be complex, and a Rayleigh quotient of real vectors need not track them at all — 'min' and 'max' of a complex-valued object are undefined. Even a real matrix like [[0,−1],[1,0]] has eigenvalues ±i and R(x) ≡ 0 for all real x, so no min-max statement can hold. Self-adjointness guarantees real eigenvalues and an orthonormal eigenbasis, which the dimension-counting step exploits.

What it unlocks is a cascade of corollaries you get almost for free:

• Weyl's inequality: λₖ(A+B) ≤ λₖ(A) + λₙ(B) and λₖ(A) + λ₁(B) ≤ λₖ(A+B) — eigenvalues move by no more than ‖B‖ under a perturbation B.
• Cauchy interlacing: if B is a principal (n−1)×(n−1) submatrix, then λₖ(A) ≤ λₖ(B) ≤ λₖ₊₁(A).
• Monotonicity: A ⪯ A′ (i.e. A′−A positive semidefinite) forces λₖ(A) ≤ λₖ(A′) for all k.

Each is a two-line consequence of the min-max form, whereas direct proofs via characteristic polynomials are painful.

Applications and generalizations

Courant-Fischer is the finite-dimensional shadow of a principle that governs continuous spectra too. For a compact self-adjoint operator on a Hilbert space, or a Sturm-Liouville problem −(pu′)′ + qu = λ w u, the same min-max over k-dimensional subspaces of a function space gives the k-th eigenvalue. This is how physicists and engineers reason about eigenvalues they cannot solve for in closed form:

• Physics: the Rayleigh-Ritz method bounds ground-state and excited-state energies of a quantum system from above by minimizing ⟨ψ|H|ψ⟩/⟨ψ|ψ⟩ over trial functions — a direct min-max estimate.
• Engineering: natural vibration frequencies of a structure are √λₖ; the theorem shows adding stiffness (making A larger) can only raise every frequency.
• Data science: PCA extracts the top eigenvector as argmax R(x); spectral clustering uses the second-smallest eigenvalue of the graph Laplacian (algebraic connectivity), which the max-min form estimates.
• Numerical analysis: convergence bounds for Lanczos and the analysis of finite-element eigenvalue approximation both route through min-max.

In short, it is the bridge from algebra to optimization that makes eigenvalues computable and estimable.

The two dual forms of Courant-Fischer and the plain Rayleigh characterization (eigenvalues ordered λ₁ ≤ λ₂ ≤ ⋯ ≤ λₙ, Rayleigh quotient R(x) = xᵀAx / xᵀx)

Characterization	Formula for λₖ	Optimizing subspace
Min-max form	λₖ = min_{dim V = k} max_{x ∈ V, x ≠ 0} R(x)	V = span of first k eigenvectors v₁,…,vₖ
Max-min form	λₖ = max_{dim V = n−k+1} min_{x ∈ V, x ≠ 0} R(x)	V = span of last n−k+1 eigenvectors vₖ,…,vₙ
Extremes (Rayleigh)	λ₁ = min_x R(x), λₙ = max_x R(x)	the single eigenvector v₁ (resp. vₙ)
Constrained (Rayleigh-Ritz)	λₖ = min over x ⊥ v₁,…,v_{k−1} of R(x)	1-dim, requires knowing v₁,…,v_{k−1}