# Rank inequality for spectral measures

Let $$A$$ and $$B$$ be $$n \times n$$ Hermitian matrices and denote by $$F_A$$ and $$F_B$$ the distribution functions related to the spectral measures $$L_A$$ and $$L_B$$ of $$A$$ and $$B$$, respectively. Setting $$k = \mathrm{rank}(A-B)$$, prove the following rank inequality $$\|F_A - F_B\|_\infty \leq \frac{k}{n}.$$ This problem is taken from Exercise 6.3 of this book where the authors want us to deliver a proof based on Cauchy's interlacing theorem. I am wondering whether there is an alternate (perhaps simpler) route to this "linear-algebra" result?

Some background: Let $$H$$ be a $$n \times n$$ Hermitian matrix with real eigenvalues $$\lambda_1(A) \geq \lambda_2(A) \geq \cdots \geq \lambda_n(A)$$, the spectral measure of $$A$$, denoted by $$L_A$$, is just the counting measure on the eigenvalues of $$A$$, i.e., $$L_A = \frac{1}{n}\sum_{i=1}^n \delta_{\lambda_i(A)}$$. Given any pair of probability measures (or probability distribution functions) $$\mu, \nu$$ on $$\mathbb{R}$$, the distance $$\|\mu - \nu\|_\infty := \sup\limits_{x\in \mathbb R} \left|\mu\left((-\infty,x)\right) - \nu\left((-\infty,x)\right) \right|$$ is also known as the Kolmogorov distance between $$\mu$$ and $$\nu$$ (denoted by $$\mathrm{d}_K(\mu,\nu)$$)

The inequality says the following: if $$A$$ has (exactly) $$m$$ eigenvalues in $$(-\infty, x]$$, then the number of eigenvalues of $$B$$ in the same interval lies between $$m-k$$ and $$m+k$$.

This can indeed be seen directly: If, let's say, $$B$$ had $$>m+k$$ eigenvalues there, then we could find $$>k$$ orthogonal vectors $$R(E_B(-\infty,x])$$ (with $$E$$ denoting the spectral projection) that are also orthogonal to (the $$m$$-dimensional space) $$R(E_A(-\infty, x])$$. Then, however, some non-zero vector in this at least $$(k+1)$$-dimensional space is annihilated by $$A-B$$, and we now have an at least $$(m+1)$$-dimensional space on which $$\langle v, Av\rangle \le x\|v\|^2$$. By min-max, this would make $$\dim R(E_A(-\infty, x])\ge m+1$$.

• May I know why "$B$ had $>m+k$ eigenvalues there, then we could find $>k$ orthogonal vectors $R(E_B(-\infty,x])$ (with $E$ denoting the spectral projection) that are also orthogonal to (the $m$-dimensional space) $R(E_A(-\infty, x])$"? It will be better if you can explain your notations in more detail as well. Jan 17 at 1:36
• The min-max principle is how you prove the interlacing theorem. Jan 17 at 15:48
• @ShannonStarr: I just said "min-max" for ease of reference. What I need here is that if the quadratic form is $\le x$ on a $d$-dimensional subspace, then there are at least $d$ eigenvalues in $(-\infty,x]$. This is a very easy exercise. Jan 17 at 18:34
• @FeiCao: If $V,W$ are subspaces with $\dim V>\dim W+k$, then $\dim V\ominus W>k$. Jan 17 at 18:36
• @ShannonStarr: Of course, in another sense you cannot escape the interlacing principle because the statement the OP wants proved is essentially a rephrasing of it. Jan 17 at 18:41

For that result, the interlacing theorem is the standard approach. It is behind a result of Bai

Bai, Z. D. (1999). Methodologies in spectral analysis of large-dimensional random matrices, a review. Statist. Sinica 9 no. 3, 611–677.

In fact that is reference 1 in another good short paper to look at by Chatterjee and Ledoux https://arxiv.org/abs/0808.2521

An observation about submatrices. Sourav Chatterjee, Michel Ledoux. Electron. Commun. Probab. 14 495-500 (2009)

If there were any confusion about how you use the interlacing theorem to obtain the sup-norm bound, then looking at Chatterjee and Ledoux could help with clarifying that.

In principle there could be a more complicated approach, which would be to look at the Krein spectral shift function, as you inductively switch from $$A$$ to $$B$$ by exchanging 1 row-and-column pair at a time to go from $$A$$ to $$B$$.

The reason I think the interlacing theorem (and ultimately Bai's approach) is the best is that the empirical spectral distribution function is a complicated function of the matrix entries and the sup-norm is a pretty strong norm. So the inequality is almost tailor-made for the minimax interlacing argument. This is typical for certain types of concentration-of-measure bounds, which are well explained in the reference you linked to.