Proof of Weyl's Inequality and Monotonicity of the Ordered Eigenvalues

Routine facts about the semidefinite ordering and the dot product are used without comment (Toolkit for AL3). Throughout, a unit vector is an $x\in\mathbb{R}^{n}$ with Euclidean norm $\lVert x\rVert=1$. All three clauses follow from one comparison principle, which we prove first.

Comparison. Let $C,D\in\mathcal{S}(n)$ and $t\in\mathbb{R}$, and suppose that

$$x\cdot(Cx)+t\le x\cdot(Dx)\qquad\text{for every unit vector }x.$$

We claim that then $\lambda_{k}(C)+t\le\lambda_{k}(D)$. By The Spectral Theorem for Real Symmetric Matrices (i) there are $Q\in\mathrm{O}(n)$ and $\mu\in\mathbb{R}^{n}$ with $\mu_{1}\ge\dots\ge\mu_{n}$ and $C=(Q\operatorname{diag}(\mu))Q^{\top}$, and $\mu_{k}=\lambda_{k}(C)$ by The Ordered Eigenvalues of a Symmetric Matrix (i). So The Courant–Fischer Min–Max Theorem (i), for $C$ with this decomposition, provides a $k$-dimensional linear subspace $V$ of the real vector space $\mathbb{R}^{n}$, namely the span of $Qe_{1},\dots,Qe_{k}$, with $x\cdot(Cx)\ge\lambda_{k}(C)$ for every unit vector $x\in V$. Now choose a decomposition of $D$ in the same way, so that its $k$th diagonal entry is $\lambda_{k}(D)$; then The Courant–Fischer Min–Max Theorem (i), for $D$ with that decomposition, shows that the $k$-dimensional subspace $V$ contains a unit vector $x$ with $x\cdot(Dx)\le\lambda_{k}(D)$. For this $x$,

$$\lambda_{k}(C)+t\le x\cdot(Cx)+t\le x\cdot(Dx)\le\lambda_{k}(D),$$

which proves the claim.

Monotonicity. If $A\preceq B$, then $x\cdot(Ax)\le x\cdot(Bx)$ for every $x\in\mathbb{R}^{n}$ by the definition of the ordering, in particular for every unit vector. The comparison principle with $C=A$, $D=B$ and $t=0$ gives $\lambda_{k}(A)\le\lambda_{k}(B)$, which is (i).

Weyl's inequality. Put $\delta=\lVert A-B\rVert$, and note that $A-B\in\mathcal{S}(n)$. For a unit vector $x$, The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (iii) and Products of Real Matrices with Zero Matrices, Negatives and Differences (iii) give

$$x\cdot(Ax)-x\cdot(Bx)=x\cdot(Ax-Bx)=x\cdot\bigl((A-B)x\bigr),$$

and The Operator Norm of a Symmetric Matrix: Quadratic Forms, Eigenvalues and the Semidefinite Ordering (iii) gives $|x\cdot((A-B)x)|\le\delta\lVert x\rVert^{2}=\delta$. Hence

$$x\cdot(Ax)-\delta\le x\cdot(Bx)\qquad\text{and}\qquad x\cdot(Bx)-\delta\le x\cdot(Ax)$$

for every unit vector $x$. The comparison principle with $(C,D,t)=(A,B,-\delta)$ gives $\lambda_{k}(A)-\delta\le\lambda_{k}(B)$, and with $(C,D,t)=(B,A,-\delta)$ it gives $\lambda_{k}(B)-\delta\le\lambda_{k}(A)$. Together these are (ii).

Shift. Let $c\in\mathbb{R}$; then $A+cI_{n}\in\mathcal{S}(n)$. For a unit vector $x$, Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (v) gives $(A+cI_{n})x=Ax+(cI_{n})x$, so The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (iii) and The Operator Norm of a Symmetric Matrix: Quadratic Forms, Eigenvalues and the Semidefinite Ordering (ix) give

$$x\cdot\bigl((A+cI_{n})x\bigr)=x\cdot(Ax)+c\lVert x\rVert^{2}=x\cdot(Ax)+c.$$

The comparison principle with $(C,D,t)=(A,A+cI_{n},c)$ gives $\lambda_{k}(A)+c\le\lambda_{k}(A+cI_{n})$, and with $(C,D,t)=(A+cI_{n},A,-c)$ it gives $\lambda_{k}(A+cI_{n})-c\le\lambda_{k}(A)$. Together these are (iii).