Let $G_n$ be an $n times n$ matrix with real i.i.d. $N(0,1/n)$ entries, let $A$ be a real $n times n$ matrix with $Vert A Vert le 1$, and let $gamma in (0,1)$. We show that with probability $0.99$, $A + gamma G_n$ has all of its eigenvalue condition numbers bounded by $Oleft(n^{5/2}/gamma^{3/2}right)$ and eigenvector condition number bounded by $Oleft(n^3 /gamma^{3/2}right)$. Furthermore, we show that for any $s > 0$, the probability that $A + gamma G_n$ has two eigenvalues within distance at most $s$ of each other is $Oleft(n^4 s^{1/3}/gamma^{5/2}right).$ In fact, we show the above statements hold in the more general setting of non-Gaussian perturbations with real, independent, absolutely continuous entries with a finite moment assumption and appropriate normalization. This extends the previous work [Banks et al. 2019] which proved an eigenvector condition number bound of $Oleft(n^{3/2} / gammaright)$ for the simpler case of {em complex} i.i.d. Gaussian matrix perturbations. The case of real perturbations introduces several challenges stemming from the weaker anticoncentration properties of real vs. complex random variables. A key ingredient in our proof is new lower tail bounds on the small singular values of the complex shifts $z-(A+gamma G_n)$ which recover the tail behavior of the complex Ginibre ensemble when $Im z eq 0$. This yields sharp control on the area of the pseudospectrum $Lambda_epsilon(A+gamma G_n)$ in terms of the pseudospectral parameter $epsilon>0$, which is sufficient to bound the overlaps and eigenvector condition number via a limiting argument.
Download