Eigenvalue Perturbation Theorem: Hoffman-Wielandt Inequality

We are interested in the question: say matrix $A$$A$ is perturbed by a small matrix E, how much do the eigenvalues of the perturbed matrix $A+E$$A+E$ deviate from the eigenvalues of $A$$A$?

The Hoffman-Wielandt inequality answers this question. Roughly, it tells us that the eigenvalues of a symmetric (actually only need to be normal) matrix enjoy a strong stability under small perturbations in its entries.

Hoffman-Wielandt Inequality

Let $A,E$$A,E$ be $n\times n$$n\times n$ real and symmetric square matrices. Let ${\lambda }_1,\cdots ,{\lambda }_n$$\lambda_1,\cdots,\lambda_n$ be the eigenvalues of $A$$A$ in some given order; and let ${\hat{\lambda }}_1,\cdots ,{\hat{\lambda }}_n$$\hat \lambda_1,\cdots,\hat\lambda_n$ be the eigenvalues of $A+E$$A+E$ in some given order. There is a permutation $\sigma (\cdot )$$\sigma(\cdot)$ of the indexes $1,\cdots ,n$$1,\cdots,n$ such that

Here $\parallel E{\parallel }_2^2$$\| E \|_2^2$ denotes the Frobenius norm of matrix $E$$E$.

Proof

Let $\mathrm{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_n)$$\Lambda = \text{diag} (\lambda_1,\cdots,\lambda_n)$ and $\hat{\mathrm{\Lambda }}=\text{diag}({\hat{\lambda }}_1,\cdots ,{\hat{\lambda }}_n)$$\hat\Lambda = \text{diag} (\hat \lambda_1,\cdots,\hat\lambda_n)$. Let $V,W$$V,W$ be $n\times n$$n\times n$ orthonormal matrices such that the diagonalization of $A$$A$ and $A+E$$A+E$ are

Because the Frobenius norm is invariant when multiplying an orthogonal matrix, we calculate

where we denote $U\equiv W^{\mathrm{\top }}V$$U \equiv W^\top V$. The entris of $U$$U$ are denoted as $u_{ij}$$u_{ij}$

Since $\hat{\mathrm{\Lambda }},\mathrm{\Lambda }$$\hat\Lambda,\Lambda$ are diagonal matrices, we have

Thus their difference is

Because $U$$U$ is the multiplication of two orthonormal matrices, the matrix whose entries are $u_{ij}^2$$u_{ij}^2$ is doubly stochastic. A doubly stochastic matrix is a square matrix of nonnegative entries, each of whose rows and columns sums to 1. Therefore, $\parallel E{\parallel }_2^2$$\| E \|_2^2$ must be larger than the following quantity

We can ponder about it for a while or just take Birkhoff's theorem off the shelf, which states this minimum is attained when $u_{ij}^2$$u_{ij}^2$ constitute a permutation matrix. A permutation matrix refers to a matrix where $u_{ij}^2$$u_{ij}^2$ is either 0 or 1 and satisfies the above equality, i.e., rows and columns sum to 1. When $u_{ij}^2$$u_{ij}^2$ constitute a permutation matrix, the sum can be written as

where $\sigma (\cdot )$$\sigma(\cdot)$ is a permutation of $1,\cdots ,n$$1,\cdots ,n$. This completes the proof.

Corollary

Actually, for a real and symmetric matrix, the permutation $\sigma (\cdot )$$\sigma(\cdot)$ is the natural permutaion where we arrange the eigenvalues by descending order. Stating more formally, we have

if ${\hat{\lambda }}_1,\cdots ,{\hat{\lambda }}_n$$\hat\lambda_1, \cdots, \hat\lambda_n$ are arranged by descending order and so are ${\lambda }_1,\cdots ,{\lambda }_n$$\lambda_1, \cdots, \lambda_n$.

Reference

Chapter 6.3 of this book:

Horn, R. A., & Johnson, C. R. (2012). Matrix analysis. Cambridge university press.