# Weyl's inequality

In linear algebra, Weyl's inequality is a theorem about the changes to eigenvalues of an Hermitian matrix that is perturbed. It can be used to estimate the eigenvalues of a perturbed Hermitian matrix.

## Weyl's inequality about perturbation

Let A{\textstyle A} be Hermitian on inner product space V{\textstyle V} with dimension n{\textstyle n}, with spectrum ordered in descending order λ$_1$≥...≥λ$_n${\textstyle \lambda _{1}\geq ...\geq \lambda _{n}}. Note that these eigenvalues can be ordered, because they are real (as eigenvalues of Hermitian matrices).
Weyl inequality — $\lambda _{i+j-1}(A+B)\leq \lambda _{i}(A)+\lambda _{j}(B)\leq \lambda _{i+j-n}(A+B)$
By the min-max theorem, it suffices to show that any W⊂V{\textstyle W\subset V} with dimension i+j−1{\textstyle i+j-1}, there exists a unit vector w{\textstyle w} such that ⟨w, (A+B)w⟩≤λ$_i$(A)+λ$_j$(B){\textstyle \langle w, (A+B)w\rangle \leq \lambda _{i}(A)+\lambda _{j}(B)}.
By the min-max principle, there exists some W$_A${\textstyle W_{A}} with codimension (i−1){\textstyle (i-1)}, such that $\lambda _{i}(A)=\max _{x\in W_{A};\|x\|=1}\langle x,Ax\rangle$ Similarly, there exists such a W$_B${\textstyle W_{B}} with codimension j−1{\textstyle j-1}. Now W$_A$∩W$_B${\textstyle W_{A}\cap W_{B}} has codimension ≤i+j−2{\textstyle \leq i+j-2}, so it has nontrivial intersection with W{\textstyle W}. Let w∈W∩W$_A$∩W$_B${\textstyle w\in W\cap W_{A}\cap W_{B}}, and we have the desired vector.
The second one is a corollary of the first, by taking the negative.
Weyl's inequality states that the spectrum of Hermitian matrices is stable under perturbation. Specifically, we have:
Corollary (Spectral stability) — $\lambda _{k}(A+B)-\lambda _{k}(A)\in [\lambda _{n}(B),\lambda _{1}(B)]$ $|\lambda _{k}(A+B)-\lambda _{k}(A)|\leq \|B\|_{op}$ where $\|B\|_{op}=\max(|\lambda _{1}(B)|,|\lambda _{n}(B)|)$ is the operator norm.
In jargon, it says that $\lambda _{k}$ is Lipschitz-continuous on the space of Hermitian matrices with operator norm.

## Weyl's inequality between eigenvalues and singular values

Let $A\in \mathbb {C} ^{n\times n}$ have singular values $\sigma _{1}(A)\geq \cdots \geq \sigma _{n}(A)\geq 0$ and eigenvalues ordered so that $|\lambda _{1}(A)|\geq \cdots \geq |\lambda _{n}(A)|$. Then
    $|\lambda _{1}(A)\cdots \lambda _{k}(A)|\leq \sigma _{1}(A)\cdots \sigma _{k}(A)$
For $k=1,\ldots ,n$, with equality for $k=n$.

## Applications
### Estimating perturbations of the spectrum

Assume that $R$ is small in the sense that its spectral norm satisfies $\|R\|_{2}\leq \epsilon$ for some small $\epsilon >0$. Then it follows that all the eigenvalues of $R$ are bounded in absolute value by $\epsilon$. Applying Weyl's inequality, it follows that the spectra of the Hermitian matrices M and N are close in the sense that
    $|\mu _{i}-\nu _{i}|\leq \epsilon \qquad \forall i=1,\ldots ,n.$
Note, however, that this eigenvalue perturbation bound is generally false for non-Hermitian matrices (or more accurately, for non-normal matrices). For a counterexample, let $t>0$ be arbitrarily small, and consider
    $M={\begin{bmatrix}0&0\\1/t^{2}&0\end{bmatrix}},\qquad N=M+R={\begin{bmatrix}0&1\\1/t^{2}&0\end{bmatrix}},\qquad R={\begin{bmatrix}0&1\\0&0\end{bmatrix}}.$
whose eigenvalues $\mu _{1}=\mu _{2}=0$ and $\nu _{1}=+1/t,\nu _{2}=-1/t$ do not satisfy $|\mu _{i}-\nu _{i}|\leq \|R\|_{2}=1$.

### Weyl's inequality for singular values

Let $M$ be a $p\times n$ matrix with $1\leq p\leq n$. Its singular values $\sigma _{k}(M)$ are the $p$ positive eigenvalues of the $(p+n)\times (p+n)$ Hermitian augmented matrix
    ${\begin{bmatrix}0&M\\M^{*}&0\end{bmatrix}}.$
Therefore, Weyl's eigenvalue perturbation inequality for Hermitian matrices extends naturally to perturbation of singular values. This result gives the bound for the perturbation in the singular values of a matrix $M$ due to an additive perturbation $\Delta$:
    $|\sigma _{k}(M+\Delta )-\sigma _{k}(M)|\leq \sigma _{1}(\Delta )$
where we note that the largest singular value $\sigma _{1}(\Delta )$ coincides with the spectral norm $\|\Delta \|_{2}$.