Spectral radii of sparse random matrices

Monday, 10 April, 2017

Published in: 

arXiv:1704.02945

We establish bounds on the spectral radii for a large class of sparse random matrices, which includes the adjacency matrices of inhomogeneous Erd\H{o}s-R\'enyi graphs. For the Erd\H{o}s-R\'enyi graph G(n,d/n), our results imply that the smallest and second-largest eigenvalues of the adjacency matrix converge to the edges of the support of the asymptotic eigenvalue distribution provided that d \gg \log n. Together with the companion paper [3], where we analyse the extreme eigenvalues in the complementary regime d \ll \log n, this establishes a crossover in the behaviour of the extreme eigenvalues around d \sim \log n. Our results also apply to non-Hermitian sparse random matrices, corresponding to adjacency matrices of directed graphs, as well as so-called structured random matrices. The proof combines (i) a new inequality between the spectral radius of a matrix and the spectral radius of its nonbacktracking version together with (ii) a new application of the method of moments for nonbacktracking matrices.

Author(s): 

Florent Benaych-Georges
Charles Bordenave
Antti Knowles