Weyl's inequality

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

Weyl's inequality about perturbation

Let ${\textstyle A,B}$ be Hermitian on inner product space ${\textstyle V}$ with dimension ${\textstyle n}$ , with spectrum ordered in descending order ${\textstyle \lambda _{1}\geq ...\geq \lambda _{n}}$ . Note that these eigenvalues can be ordered, because they are real (as eigenvalues of Hermitian matrices).^[1]

Weyl inequality—Let ${\textstyle A,B}$ be ${\textstyle n\times n}$ Hermitian matrices, and let ${\textstyle 1\leq i,j\leq n}$ be integers. If ${\textstyle i+j\leq n+1}$ , then $\lambda _{i+j-1}(A+B)\leq \lambda _{i}(A)+\lambda _{j}(B).$ If ${\textstyle n<i+j}$ , then $\lambda _{i}(A)+\lambda _{j}(B)\leq \lambda _{i+j-n}(A+B).$

Proof

By the min-max theorem, it suffices to show that any ${\textstyle W\subset V}$ with dimension ${\textstyle i+j-1}$ , there exists a unit vector ${\textstyle w}$ such that ${\textstyle \langle w,(A+B)w\rangle \leq \lambda _{i}(A)+\lambda _{j}(B)}$ .

By the min-max principle, there exists some ${\textstyle W_{A}}$ with codimension ${\textstyle (i-1)}$ , such that $\lambda _{i}(A)=\max _{x\in W_{A};\|x\|=1}\langle x,Ax\rangle$ Similarly, there exists such a ${\textstyle W_{B}}$ with codimension ${\textstyle j-1}$ . Now ${\textstyle W_{A}\cap W_{B}}$ has codimension ${\textstyle \leq i+j-2}$ , so it has nontrivial intersection with ${\textstyle W}$ . Let ${\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:^[1]

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$ . ^[2]

Applications

Estimating perturbations of the spectrum

Let Hermitian matrices $M$ and $N$ differ by a matrix $R$ . 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^[3]

|\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.^[1] 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}$ .

Weyl's inequality

Weyl's inequality about perturbation

Weyl's inequality between eigenvalues and singular values

Applications

Estimating perturbations of the spectrum

Weyl's inequality for singular values

Notes

References

Related Articles

Timelines

Top Qs

Fact Checks