Random matrices have simple spectrum
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.
- Random matrices: probability of normality
- Low-degree factors of random polynomials
- A new perspective on the average mixing matrix
- On the eigenvalues distribution in threshold graphs
- Sparse random matrices have simple spectrum
- Recent progress in combinatorial random matrix theory
- Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
- Upper Hessenberg and Toeplitz Bohemian matrix sequences: a note on their asymptotical eigenvalues and singular values
- On the real Davies' conjecture
- Tail bounds for gaps between eigenvalues of sparse random matrices
- The characteristic polynomial of a random matrix
- An ensemble of high rank matrices arising from tournaments
- Unlocking the walk matrix of a graph
- On Hosoya's dormants and sprouts
- A note on species richness and the variance of epidemic severity
- Upper Hessenberg and Toeplitz Bohemians
- Determinants of Seidel matrices and a conjecture of Ghorbani
- Almost equitable partitions and new necessary conditions for network controllability
- The robust minimal controllability problem
- On a Conjecture of Godsil Concerning Controllable Random Graphs
- Eigenvectors of random matrices of symmetric entry distributions
- Random quantum graphs
- Random matrices: tail bounds for gaps between eigenvalues
- The robust minimal controllability and observability problem
- Bifurcations in Nagumo equations on graphs and Fiedler vectors
- The least singular value of a random symmetric matrix
- On the multiplicities of digraph eigenvalues
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Low-rank matrices, tournaments, and symmetric designs
- Selected open problems in continuous-time quantum walks
- Eigenvalue gaps of random perturbations of large matrices
- A characterization of generalized cospectrality of rooted graphs with applications in graph reconstruction
- Generic diagonalizability, structural functional observability and output controllability
- Graph matching via convex relaxation to the simplex
- Eigenvectors of random matrices: A survey
- On the number of integral graphs
This page was built for publication: Random matrices have simple spectrum
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1677622)
