Rank inequality for spectral measures

Question

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)$)

Answer 1

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$.

Answer 2

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.