Random matrices have simple spectrum (Q1677622)

The paper under review deals with symmetric \(n\times n\) matrices where the upper triangular elements \(\xi_{ij}\) with \(i<j\) are fully independent and identically distributed, all having the distribution of a real random variable \(\xi\) (which may depend on \(n\)), and the diagonal elements \(\xi_{ii}\) are independent of the upper triangular elements, though the diagonal elements can be correlated with each other and can have any distribution. Of course the eigenvalues of a symmetric matrix are real. We say that a random variable \(\xi\) is non-trivial if exists \(\mu>0\) (independent of \(n\)) such that \(\mathbb{P}(\xi=x)\leq 1-\mu\) for all \(x\in \mathbb{R}\). For example any non-degnerate random variable independent of \(n\) is non-trivial. The main result of the article is that, for a random symmetric matrix as in the first paragraph, if \(\xi\) has a non-degenerate distribution, then -- i.e., with probability tending to 1 as \(n\rightarrow\infty\) -- the spectrum of such a matrix is simple, i.e., all the eigenvalues have multiplicity 1. Indeed the probability of being simple is at least \(1-n^{-A}\) for any \(A>0\). This implies a positive solution to a long-standing conjecture of Babai that a random graph \(G(n,1/2)\) has simple spectrum. The idea of the proof is that if the spectrum were not simple, this would have an implication for the eigenvectors -- that they satisfy the technical condition of being rich. Rich vectors are shown to mostly lie in a generalised arithmetic progression (GAP) of bounded rank. In fact, critically, the GAP does not just contain most of the rich vectors, but also a large subset of the set of components of the eigenvectors which does not concentrate too much. Since the probability that a rich vector is an eigenvector is small, by controlling the number of such vectors we can get the required result. This simplistic summary hides a lot of work in the last step as we seem to need more than the union bound on the probability of getting a rich vector which is an eigenvalue: entropy plays a role. The authors note that the full i.i.d. assumption on the upper triangular entries is not actually needed and that the result extends to Hermitian random matrix models.