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


2 Answers 2


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

  • $\begingroup$ 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. $\endgroup$
    – Fei Cao
    Jan 17, 2022 at 1:36
  • $\begingroup$ The min-max principle is how you prove the interlacing theorem. $\endgroup$ Jan 17, 2022 at 15:48
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 17, 2022 at 18:34
  • $\begingroup$ @FeiCao: If $V,W$ are subspaces with $\dim V>\dim W+k$, then $\dim V\ominus W>k$. $\endgroup$ Jan 17, 2022 at 18:36
  • $\begingroup$ @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. $\endgroup$ Jan 17, 2022 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.