Sparse Random Matrices have Simple Spectrum

Abstract

Let $M_n$ be a class of symmetric sparse random matrices, with independent entries $M_{ij}={\delta }_{ij}{\xi }_{ij}$ for $i\le j$. ${\delta }_{ij}$ are i.i.d. Bernoulli random variables taking the value $1$ with probability $p\ge n^{-1+\delta }$ for any constant $\delta >0$ and ${\xi }_{ij}$ are i.i.d. centered, subgaussian random variables. We show that with high probability this class of random matrices has simple spectrum (i.e. the eigenvalues appear with multiplicity one). We can slightly modify our proof to show that the adjacency matrix of a sparse Erdős-Rényi graph has simple spectrum for $n^{-1+\delta }\le p\le 1-n^{-1+\delta }$. These results are optimal in the exponent. The result for graphs has connections to the notorious graph isomorphism problem.

27 pages