6
$\begingroup$

The question: Let $A$ be the matrix whose each element is an independently generated random variable which is uniform on $[0,1]$. One can see that the eigenvalues of $A$ will be distinct almost surely. Let $\delta = \min_{i,j} |\lambda_i(A) - \lambda_j(A)|$ be the smallest distance between any two eigenvalues of $A$ in the complex plane. What sort of lower bounds does $\delta$ satisfy with high probability?

Background: looking at the literature, it seems that for some symmetric random matrices $A$ the question has been settled, in the sense that the exact distribution of $\delta$ is known. This does not, however, seem to apply to the non-symmetric case above, and it seems reasonable to guess that the exact distribution of $\delta$ for the random matrix I am asking about is an open question.

However, here I am asking for something much less than an exact distribution of $\delta$ -- for example, can one make a statement along the lines of $P(\delta \geq 1/n^{10}) \geq 1-1/n^{0.1}$, or something like that?

$\endgroup$
1
  • $\begingroup$ In the symmetric case, an estimate of the type you ask about has recently been derived by Nguyen, Tao and Vu. arxiv.org/pdf/1504.00396v1.pdf I am not aware of a similar result in the non-Hermitian case $\endgroup$ Nov 7, 2015 at 21:41

1 Answer 1

4
$\begingroup$

This paper treats the case of iid complex Gaussian entries: http://arxiv.org/abs/1207.4240

In particular, the smallest eigenvalue gap is shown to be of order $n^{-3/4}$ when the entries are normalized to have variance $1/n$. One might expect this to extend to more general entry distributions, but as far as I am aware this is unknown.

Edit: As to whether one can show $P(\delta\ge n^{-C})\rightarrow 1$ for some $C>0$, for general (possibly discrete) entry distributions it seems difficult to even show $P(\delta> 0)\rightarrow 1$. However, as is the case for controlling the smallest singular value, it may be easier to lower bound $\delta$ when the entries have a bounded density (perhaps this is why you posed the question for the uniform distribution on $[0,1]$).

$\endgroup$
2
  • 1
    $\begingroup$ This is still in the determinantal setup..... $\endgroup$ Nov 8, 2015 at 9:38
  • $\begingroup$ Right... As for universality, it looks like the Tao–Vu four moment theorem only gives that at most $O(n^{1-c})$ eigenvalues are repeated (see Corollary 18 here: arxiv.org/pdf/1206.1893v6.pdf). $\endgroup$
    – Nick Cook
    Nov 8, 2015 at 21:41

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.