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 [math]\displaystyle{ A }[/math] be Hermitian on inner product space [math]\displaystyle{ V }[/math] with dimention [math]\displaystyle{ n }[/math], with spectrum ordered in descending order [math]\displaystyle{ \lambda_1 \geq ... \geq \lambda_n }[/math]. Note that these eigenvalues can be ordered, because they are real (as eigenvalues of Hermitian matrices).

Weyl inequality — [math]\displaystyle{ \lambda_{i+j-1}(A+B) \leq \lambda_i(A)+\lambda_j(B) \leq \lambda_{i+j-n}(A+B) }[/math]

Proof

By the min-max theorem, it suffices to show that any [math]\displaystyle{ W \subset V }[/math] with dimension [math]\displaystyle{ i+j-1 }[/math], there exists a unit vector [math]\displaystyle{ w }[/math] such that [math]\displaystyle{ \langle w, (A+B)w\rangle \leq \lambda_i(A) + \lambda_j(B) }[/math].

By the min-max principle, there exists some [math]\displaystyle{ W_A }[/math] with codimension [math]\displaystyle{ (i-1) }[/math], such that [math]\displaystyle{ \lambda_i(A) = \max_{x\in W_A; \|x\|=1}\langle x, Ax\rangle }[/math] Similarly, there exists such a [math]\displaystyle{ W_B }[/math] with codimension [math]\displaystyle{ j-1 }[/math]. Now [math]\displaystyle{ W_A \cap W_B }[/math] has codimension [math]\displaystyle{ \leq i+j-2 }[/math], so it has nontrivial intersection with [math]\displaystyle{ W }[/math]. Let [math]\displaystyle{ w \in W \cap W_A \cap W_B }[/math], 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) — [math]\displaystyle{ \lambda_k(A+B) - \lambda_k(A) \in [\lambda_n(B), \lambda_1(B)] }[/math] [math]\displaystyle{ |\lambda_k(A+B) - \lambda_k(A)| \leq \|B\|_{op} }[/math] where
[math]\displaystyle{ \|B\|_{op} = \max(|\lambda_1(B)|, |\lambda_n(B)|) }[/math] is the operator norm.

In jargon, it says that [math]\displaystyle{ \lambda_k }[/math] is Lipschitz-continuous on the space of Hermitian matrices with operator norm.

Weyl's inequality between eigenvalues and singular values

Let [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] have singular values [math]\displaystyle{ \sigma_1(A) \geq \cdots \geq \sigma_n(A) \geq 0 }[/math] and eigenvalues ordered so that [math]\displaystyle{ |\lambda_1(A)| \geq \cdots \geq |\lambda_n(A)| }[/math]. Then

[math]\displaystyle{ |\lambda_1(A) \cdots \lambda_k(A)| \leq \sigma_1(A) \cdots \sigma_k(A) }[/math]

For [math]\displaystyle{ k = 1, \ldots, n }[/math], with equality for [math]\displaystyle{ k=n }[/math].

Applications

Estimating perturbations of the spectrum

Assume that [math]\displaystyle{ R }[/math] is small in the sense that its spectral norm satisfies [math]\displaystyle{ \|R\|_2 \le \epsilon }[/math] for some small [math]\displaystyle{ \epsilon\gt 0 }[/math]. Then it follows that all the eigenvalues of [math]\displaystyle{ R }[/math] are bounded in absolute value by [math]\displaystyle{ \epsilon }[/math]. Applying Weyl's inequality, it follows that the spectra of the Hermitian matrices M and N are close in the sense that

[math]\displaystyle{ |\mu_i - \nu_i| \le \epsilon \qquad \forall i=1,\ldots,n. }[/math]

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 [math]\displaystyle{ t\gt 0 }[/math] be arbitrarily small, and consider

[math]\displaystyle{ 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}. }[/math]

whose eigenvalues [math]\displaystyle{ \mu_1 = \mu_2 = 0 }[/math] and [math]\displaystyle{ \nu_1 = +1/t, \nu_2 = -1/t }[/math] do not satisfy [math]\displaystyle{ |\mu_i - \nu_i| \le \|R\|_2 = 1 }[/math].

Weyl's inequality for singular values

Let [math]\displaystyle{ M }[/math] be a [math]\displaystyle{ p \times n }[/math] matrix with [math]\displaystyle{ 1 \le p \le n }[/math]. Its singular values [math]\displaystyle{ \sigma_k(M) }[/math] are the [math]\displaystyle{ p }[/math] positive eigenvalues of the [math]\displaystyle{ (p+n) \times (p+n) }[/math] Hermitian augmented matrix

[math]\displaystyle{ \begin{bmatrix} 0 & M \\ M^* & 0 \end{bmatrix}. }[/math]

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 [math]\displaystyle{ M }[/math] due to an additive perturbation [math]\displaystyle{ \Delta }[/math]:

[math]\displaystyle{ |\sigma_k(M+\Delta) - \sigma_k(M)| \le \sigma_1(\Delta) }[/math]

where we note that the largest singular value [math]\displaystyle{ \sigma_1(\Delta) }[/math] coincides with the spectral norm [math]\displaystyle{ \|\Delta\|_2 }[/math].

References

• Matrix Theory, Joel N. Franklin, (Dover Publications, 1993) ISBN:0-486-41179-6
• "Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen", H. Weyl, Math. Ann., 71 (1912), 441–479