Abstract
Let M n =(ξ ij )1≤i,j≤n be a real symmetric random matrix in which the upper-triangular entries ξ ij , i < j and diagonal entries ξ 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ős-Rényi random graph has simple spectrum asymptotically almost surely, answering a question of Babai.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
L. Babai, D. Grigoryev and D. Mount: Isomorphism of graphs with bounded eigenvalue multiplicity, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 310–324 (1982).
L. Babai: Private conversation, May 2012.
L. Erdős, A. Knowles, H.-T. Yau and J. Yin: Spectral statistics of Erdős-Rényi Graphs II: Eigenvalue spacing and the extreme eigenvalues, Comm. Math. Phys. 314 (2012), 587–640.
J. Komlós: On the determinant of (0; 1) matrices, Studia Sci. Math. Hungar. 2 (1967), 7–21.
H. Nguyen and V. Vu: Small Ball Probability, Inverse Theorems, and Applications, Erdős Centenial Proceeding, Eds. L. Lovász et. al., Springer 2013.
H. Nguyen and V. Vu: Optimal Littlewood-Offord theorems, Advances in Math., Vol. 226 6 (2011), 5298–5319.
T. Tao and V. Vu: Additive Combinatorics, Cambridge University Press, 2006.
T. Tao and V. Vu: Inverse Littlewood-Offord theorems and the condition number of random matrices, Annals of Mathematics 169 (2009), 595–632.
T. Tao and V. Vu: A sharp inverse Littlewood-Offord theorem, Random Structures Algorithms 37 (2010), 525–539.
Author information
Authors and Affiliations
Corresponding author
Additional information
T. Tao is supported by a Simons Investigator grant, the James and Carol Collins Chair, the Mathematical Analysis & Application Research Fund Endowment, and by NSF grant DMS-1266164.
V. Vu is supported by NSF grant DMS 1307797 and AFORS grant FA9550-12-1-0083.