Random matrices have simple spectrum

Abstract

Let $M_n=({\xi }_{ij}{)}_{1\le i,j\le n}$ be a real symmetric random matrix in which the upper-triangular entries ${\xi }_{ij},i<j$ and diagonal entries ${\xi }_{ii}$ are independent. We show that with probability tending to 1, $M_n$ has no repeated eigenvalues. As a corollary, we deduce that the Erd{\H o}s-Renyi random graph has simple spectrum asymptotically almost surely, answering a question of Babai.

12 pages, no figures, submitted, Combinatorica