Spectral radii of sparse random matrices
Florent Benaych-Georges, Charles Bordenave, Antti Knowles
Abstract
Nous établissons des bornes sur le rayon spectral pour une grande classe de matrices aléatoires creuses, qui inclut les matrices d’adjacence des graphes Erdős–Rényi inhomogènes. Nos bornes d’erreur sont optimales pour une grande classe de matrices aléatoires. En particulier, pour le graphe Erdős–Rényi $G(n,d/n)$, nos résultats impliquent que la plus petite et la deuxième plus grande valeurs propres de la matrice d’adjacence convergent vers les bords du support de la distribution asymptotique des valeurs propres sous la condition $d/\log n\to \infty $. Avec le papier (Benaych-Georges, Bordenave and Knowles (2017)), où nous analysons les valeurs propres extrêmes dans le régime complémentaire $d/\log n\to 0$, ceci établit une transition dans le comportement des valeurs propres dans le régime $d\asymp \log n$. Nos résultats s’appliquent aussi aux matrices non-hermitiennes, correspondant à des matrices d’adjacence de graphes dirigés. La démonstration combine (i) une nouvelle inégalité reliant le rayon spectral d’une matrice et le rayon spectral de sa version nonbacktracking avec (ii) une nouvelle application de la méthode des moments pour les matrices nonbacktracking.