Abstract
A diagonalizable matrix has linearly independent eigenvectors, and every complex matrix is a limit of diagonalizable matrices. We prove a quantitative version of this fact: every n x n complex matrix is within distance delta in the operator norm of a matrix whose eigenvectors have condition number poly(n)/delta, confirming a conjecture of E. B. Davies. The proof is based adding a complex Gaussian perturbation to the matrix and studying its pseudospectrum, and may be viewed as a simple non-asymptotic incarnation of the "hermitization" method for proving limit laws in random matrix theory.
We discuss extensions and applications of this result to numerical analysis, yielding the fastest known provable algorithm for diagonalizing an arbitrary matrix.
Joint work with J. Banks, A. Kulkarni, S. Mukherjee, J. Garza Vargas.