Mutasim Mim

mathjax.axby.world
Discrete Hodge theory · spectral graph theory · combinatorics
notes-first pages · MathJax everywhere · print-friendly

Codimension-1 Courant–Fischer trick

Complete proof of a move that shows up constantly in spectral bounds.

Proposition
min–max, codim-1 slice

Let $A\succeq 0$ on an inner-product space $V$ and let $W=(\ker A)^\perp$. If $H\subseteq W$ has codimension $1$ in $W$, then $$\lambda_{\min}^+(A)\le \max_{x\in H,\ \|x\|=1}\langle Ax,x\rangle.$$

Proof

Restrict $A$ to $W$. On $W$, $A$ is positive definite (no kernel), and $\lambda_{\min}^+(A)$ equals the smallest eigenvalue of $A|_W$. Let $m=\dim W$. By Courant–Fischer on $W$, $$\lambda_1(A|_W)=\min_{\dim S = m-1}\ \max_{x\in S,\ \|x\|=1}\langle Ax,x\rangle.$$

Since $H$ has dimension $m-1$, it is an admissible choice of $S$. Therefore $$\lambda_{\min}^+(A)=\lambda_1(A|_W)\le \max_{x\in H,\ \|x\|=1}\langle Ax,x\rangle,$$ proving the claim.

Why this is useful

If you can construct $H$ explicitly (e.g., by imposing one linear constraint like $\langle x, u\rangle=0$), the right-hand side often becomes computable or at least estimable.