Courant–Fischer min-max theorem

The $k$-th largest eigenvalue of a Hermitian matrix is the maximum over $(k+1)$-dimensional subspaces of the minimum of the Rayleigh quotient.

Results

Let $\mathbb K$ be $\mathbb R$ or $\mathbb C$, and let $A$ be a Hermitian $N\times N$ matrix over $\mathbb K$ with eigenvalues $\lambda_0\ge\dots\ge\lambda_{N-1}$, listed with multiplicity. The Rayleigh quotient of $x\in\mathbb K^N$ is $$ R_A(x)=\frac{\operatorname{Re}(x^*Ax)}{\operatorname{Re}(x^*x)} . $$

Theorem (Courant–Fischer). [Cou20]; [Fis05] For every $0\le k<N$:

  1. some subspace $W\subseteq\mathbb K^N$ of dimension $k+1$ satisfies $R_A(x)\ge\lambda_k$ for every nonzero $x\in W$;
  2. every subspace $W\subseteq\mathbb K^N$ of dimension $k+1$ contains a nonzero $x$ with $R_A(x)\le\lambda_k$.

The same two statements hold for any matrix $A$ with an orthonormal basis $b_0,\dots,b_{N-1}$ of $\mathbb K^N$ and real numbers $\mu_0\ge\dots\ge\mu_{N-1}$ such that $Ab_j=\mu_jb_j$, with $\mu_k$ in place of $\lambda_k$.

Use

The theorem is the tool behind the Cauchy interlacing theorem and Weyl's rank-one interlacing.

Proof

For part 1 take $W=\operatorname{span}(b_0,\dots,b_k)$. For part 2 the span of $b_k,\dots,b_{N-1}$ has dimension $N-k$, so it meets every subspace of dimension $k+1$ in a nonzero vector.

References

See [Cou20]; [Fis05].

  1. [Cou20] R. Courant. Über die Eigenwerte bei den Differentialgleichungen der mathematischen Physik. Mathematische Zeitschrift, 7(1-4), 1-57, 1920.
    BibTeX
    @article{Courant1920,
      author = {Courant, R.},
      title = {{\"U}ber die {E}igenwerte bei den {D}ifferentialgleichungen der mathematischen {P}hysik},
      year = {1920},
      journal = {Mathematische Zeitschrift},
      volume = {7},
      number = {1-4},
      pages = {1--57},
      doi = {10.1007/BF01199396},
      url = {https://doi.org/10.1007/BF01199396}
    }
  2. [Fis05] Ernst Fischer. Über quadratische Formen mit reellen Koeffizienten. Monatshefte für Mathematik und Physik, 16(1), 234-249, 1905.
    BibTeX
    @article{Fischer1905,
      author = {Fischer, Ernst},
      title = {Über quadratische {F}ormen mit reellen {K}oeffizienten},
      year = {1905},
      journal = {Monatshefte für Mathematik und Physik},
      volume = {16},
      number = {1},
      pages = {234--249},
      doi = {10.1007/BF01693781},
      url = {https://doi.org/10.1007/BF01693781}
    }

Definitions

  • Eigenvalues of a Hermitian matrix in decreasing order

    RealRooted.sortedEigenvaluessource
    noncomputable def sortedEigenvalues {N : ℕ}
        (A : Matrix (Fin N) (Fin N) 𝕜) (hA : A.IsHermitian) : Fin N → ℝ :=
      fun k => hA.eigenvalues₀ (finCongr (Fintype.card_fin N).symm k)
  • Rayleigh quotient

    RealRooted.rayleighsource
    noncomputable def rayleigh {N : ℕ} (A : Matrix (Fin N) (Fin N) 𝕜)
        (x : Fin N → 𝕜) : ℝ :=
      RCLike.re (star x ⬝ᵥ A.mulVec x) / RCLike.re (star x ⬝ᵥ x)

Theorems

  • Courant–Fischer: the kth eigenvalue is a max-min of the Rayleigh quotientMain result

    RealRooted.courant_fischersource
    theorem courant_fischer (𝕜 : Type*) [RCLike 𝕜] :
        ∀ {N : ℕ} (A : Matrix (Fin N) (Fin N) 𝕜) (hA : A.IsHermitian) (k : Fin N),
          (∃ W : Submodule 𝕜 (Fin N → 𝕜), Module.finrank 𝕜 W = (k : ℕ) + 1 ∧
              ∀ x ∈ W, x ≠ 0 → sortedEigenvalues A hA k ≤ rayleigh A x) ∧
          (∀ W : Submodule 𝕜 (Fin N → 𝕜), Module.finrank 𝕜 W = (k : ℕ) + 1 →
              ∃ x ∈ W, x ≠ 0 ∧ rayleigh A x ≤ sortedEigenvalues A hA k)
  • Courant–Fischer from an orthonormal eigenbasis with antitone eigenvalues

    RealRooted.courantFischer_of_eigenbasissource
    theorem courantFischer_of_eigenbasis {N : ℕ}
        (A : Matrix (Fin N) (Fin N) 𝕜)
        (b : OrthonormalBasis (Fin N) 𝕜 (EuclideanSpace 𝕜 (Fin N)))
        (μ : Fin N → ℝ) (hμ : Antitone μ)
        (hb : ∀ j, A *ᵥ WithLp.ofLp (b j) = μ j • WithLp.ofLp (b j)) (k : Fin N) :
        (∃ W : Submodule 𝕜 (EuclideanSpace 𝕜 (Fin N)),
            Module.finrank 𝕜 W = (k : ℕ) + 1 ∧
            ∀ x ∈ W, x ≠ 0 → μ k ≤ rayleigh A (WithLp.ofLp x)) ∧
        (∀ W : Submodule 𝕜 (EuclideanSpace 𝕜 (Fin N)),
            Module.finrank 𝕜 W = (k : ℕ) + 1 →
            ∃ x ∈ W, x ≠ 0 ∧ rayleigh A (WithLp.ofLp x) ≤ μ k)

Lean source RealRooted/Challenges/Matrices/CourantFischer.lean at revision d6670742. Formalized 2026-07-01.