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$:
- some subspace $W\subseteq\mathbb K^N$ of dimension $k+1$ satisfies $R_A(x)\ge\lambda_k$ for every nonzero $x\in W$;
- 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
- [Cou20] Ü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} } - [Fis05] Ü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} }