Eigenvalue Bounds for Random Matrices via Zerofreeness

Abstract

We introduce a new technique to prove bounds for the spectral radius of a random matrix, based on using Jensen's formula to establish the zerofreeness of the associated characteristic polynomial in a region of the complex plane. Our techniques are entirely non-asymptotic, and we instantiate it in three settings: (i) The spectral radius of non-asymptotic Girko matrices -- these are asymmetric matrices $\mathbf{M}\in {\mathbb{C}}^{n\times n}$ whose entries are independent and satisfy $\mathbb{E}{\mathbf{M}}_{ij}=0$ and $\mathbb{E}|{\mathbf{M}}_{ij}^2|\le \frac{1}{n}$. (ii) The spectral radius of non-asymptotic Wigner matrices -- these are symmetric matrices $\mathbf{M}\in {\mathbb{C}}^{n\times n}$ whose entries above the diagonal are independent and satisfy $\mathbb{E}{\mathbf{M}}_{ij}=0$, $\mathbb{E}|{\mathbf{M}}_{ij}^2|\le \frac{1}{n}$, and $\mathbb{E}|{\mathbf{M}}_{ij}^4|\le \frac{1}{n}$. (iii) The second eigenvalue of the adjacency matrix of a random $d$-regular graph on $n$ vertices, as drawn from the configuration model. In all three settings, we obtain constant-probability eigenvalue bounds that are tight up to a constant. Applied to specific random matrix ensembles, we recover classic bounds for Wigner matrices, as well as results of Bordenave--Chafaï--García-Zelada, Bordenave--Lelarge--Massoulié, and Friedman, up to constants.

20 pages