Gaussian Regularization of the Pseudospectrum and Davies Conjecture

A matrix $Ainmathbb{C}^{ntimes n}$ is diagonalizable if it has a basis of linearly independent eigenvectors. Since the set of nondiagonalizable matrices has measure zero, every $Ain mathbb{C}^{ntimes n}$ is the limit of diagonalizable matrices. We prove a quantitative version of this fact conjectured by E.B. Davies: for each $deltain (0,1)$, every matrix $Ain mathbb{C}^{ntimes n}$ is at least $delta|A|$-close to one whose eigenvectors have condition number at worst $c_n/delta$, for some constants $c_n$ dependent only on $n$. Our proof uses tools from random matrix theory to show that the pseudospectrum of $A$ can be regularized with the addition of a complex Gaussian perturbation. Along the way, we explain how a variant of a theorem of Sniady implies a conjecture of Sankar, Spielman and Teng on the optimal constant for smoothed analysis of condition numbers.