On the real Davies' conjecture

Abstract

We show that every matrix $A\in {\mathbb{R}}^{n\times n}$ is at least $\delta$$\Vert A\Vert$-close to a real matrix $A+E\in {\mathbb{R}}^{n\times n}$ whose eigenvectors have condition number at most ${\tilde{O}}_n({\delta }^{-1})$. In fact, we prove that, with high probability, taking $E$ to be a sufficiently small multiple of an i.i.d. real sub-Gaussian matrix of bounded density suffices. This essentially confirms a speculation of Davies, and of Banks, Kulkarni, Mukherjee, and Srivastava, who recently proved such a result for i.i.d. complex Gaussian matrices. Along the way, we also prove non-asymptotic estimates on the minimum possible distance between any two eigenvalues of a random matrix whose entries have arbitrary means; this part of our paper may be of independent interest.

See Section 1.6 for discussion of concurrent and independent work of Banks, Garza-Vargas, Kulkarni, and Srivastava. v2: minor formatting changes