Weyl's inequality for eigenvalues of symmetric matrices

Idea. Same as for singular values: the quantities in the min-max formula move by at most $\|A-B\|$.

Step 0. By Courant-Fischer, for symmetric $A$,
$$\lambda_k(A)=\max_{\dim V=k}\ \min_{x\in V,|x|=1}x^TAx.$$

Step 1: pointwise. For every unit $x$,
$$x^TAx=x^TBx+x^T(A-B)x\ge x^TBx-|x^T(A-B)x|\ge x^TBx-\|A-B\|,$$
since $|x^TCx|\le|x|\,|Cx|\le\|C\|$ by Cauchy-Schwarz.

Step 2: min over $V$, then max over $V$. For each $k$-dimensional $V$,
$$\min_{V,|x|=1}x^TAx\ge\min_{V,|x|=1}x^TBx-\|A-B\|,$$
and taking $\max_V$ gives $\lambda_k(A)\ge\lambda_k(B)-\|A-B\|$.

Step 3: symmetry. Exchange $A$ and $B$ to get the other inequality.

Numeric check. For two random PSD matrices $S=AA^T$, $T=BB^T$ with $\|S-T\|=0.709$: $\max_k|\lambda_k(S)-\lambda_k(T)|=0.412\le0.709$.

Remark.
- In particular $\rho(A)=\max_k|\lambda_k(A)|$ is $1$-Lipschitz on $\mathrm{Sym}_n$, contrasting with the Hölder exponent $\frac1n$ of Problem 82 for general matrices.
- The inequality fails for non-symmetric matrices with the ordered *real parts* replaced by anything: e.g. Jordan-type perturbations give $\varepsilon^{1/n}$ shifts.
- Weyl's inequality is the core of the Hoffman-Wielandt theorem $\sum(\lambda_k(A)-\lambda_k(B))^2\le\|A-B\|_F^2$.