Given Hermitian matrix $A$, I would like to perturbate it so that its eigenvalues become well-separated. Specifically, let $A$ be some Hermitian matrix, and let $G$ be a Gaussian matrix, with each entry $G_{i,j} \sim {\cal N}(0,1)$. Let $\epsilon>0$ be some parameter. Does there exist a function $f(\epsilon)$ such that the following holds with high probability:

The eigenvalues $\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n$ of $A+ \epsilon G$ have pairwise spacing at least $f(\epsilon)$, i.e. $\lambda_i - \lambda_j \geq f(\epsilon)$, for all $i<j$.

Note that since some eigenvalues may appear with multiplicity, variational techniques may not work here, due to non-existence of the second order derivative.

In addition, some eigenvalues can be at arbitrarily close distance to each other so that while variational techniques collapse, degenerate perturbation analysis is not completely accurate either.


since you want $f$ to be the same for all $A$, let's first take the special case $A=0$; then the eigenvalues of $A+\epsilon G$ have an average spacing of order $\epsilon/\sqrt{n}$, but the fraction of eigenvalues with a smaller spacing vanishes only linearly as the spacing goes to zero. So you'll have to take $f(\epsilon)\ll\epsilon/\sqrt{n}$ if you seek a lower bound on the spacing "with high probability".

adding a nonzero $A$ will not change much; the degenerate eigenvalues of $A$ will split by an amount of order $\epsilon$ as a result of the perturbation by $\epsilon G$, which is already much larger than the bound $f(\epsilon)\ll\epsilon/\sqrt{n}$ which you need to account for the case $A=0$.

  • $\begingroup$ Thank you for the detailed answer. Regarding the second part of the answer, is it easy to see, why the degenerate eigenvalues are split by order $\epsilon$ ? $\endgroup$ – Lior Eldar Oct 29 '13 at 7:48
  • $\begingroup$ isn't that just degenerate perturbation theory? the correction to the eigenvectors is of order $\epsilon^2$, but the eigenvalues split linearly in $\epsilon$. More precisely, the splitting is $\delta \lambda=\epsilon\sqrt{(G_{aa}-G_{bb})^2+4G_{ab}^{2}}$, where $G_{ij}$ is the matrix element of $G$ in the eigenbasis of $A$. $\endgroup$ – Carlo Beenakker Oct 29 '13 at 8:18
  • $\begingroup$ There is something here I do not understand - how is the degeneracy-splitting process different than the eigenvalue distribution of $A+\epsilon G$ for $A=0$, and why will this splitting be larger than $f(\epsilon)$? After all, this is $n$-fold degenracy. It seems to me that given an arbitrary matrix $A$, the minimal spacing will be determined precisely by the $f(\epsilon)$ determined for $A=0$, but perhaps I'm confused. $\endgroup$ – Lior Eldar Oct 30 '13 at 10:43
  • $\begingroup$ certainly, and that is why I wrote that adding a nonzero $A$ does not change the estimate $f(\epsilon)\ll\epsilon/\sqrt{n}$. $\endgroup$ – Carlo Beenakker Oct 30 '13 at 11:11
  • $\begingroup$ Thank you. Is there a known theorem that handles both the degenerate and non-degenerate case together?: I actually fear the intermediate case in which non-degenerate analysis cannot neglect the second order derivative (which goes to $\infty$) but degenerate analysis is non-applicable because the e.v.s are not exactly identical. $\endgroup$ – Lior Eldar Oct 30 '13 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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