6
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\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
    Commented Oct 29, 2013 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
    Commented Oct 29, 2013 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
    Commented Oct 30, 2013 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
    Commented Oct 30, 2013 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
    Commented Oct 30, 2013 at 11:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .