Eigenvalue Bounds for Random Matrices via Zerofreeness

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}\mathrm{\mid }{\mathbf{M}}_{ij}^2\mathrm{\mid }\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}\mathrm{\mid }{\mathbf{M}}_{ij}^2\mathrm{\mid }\le \frac{1}{n}$, and $\mathbb{E}\mathrm{\mid }{\mathbf{M}}_{ij}^4\mathrm{\mid }\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.