Random matrices have simple spectrum

DOI10.1007/S00493-016-3363-4MaRDI QIDQ1677622zbMATH OpenOpenAlexFDO

Authors Terence Tao, Van Vu

Publication date 10 November 2017

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.1438

zbMATH Keywords

matricesspectrum

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05)

Abstract: Let $M_n=(x{i}_{ij}{)}_{1leqi,jleqn}$ be a real symmetric random matrix in which the upper-triangular entries $x{i}_{ij},i<j$ and diagonal entries $x{i}_{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.

Recommendations

• Sparse random matrices have simple spectrum
• Random matrices: tail bounds for gaps between eigenvalues
• Wigner random matrices with non-symmetrically distributed entries
• Invertibility of symmetric random matrices
• Spectral norm of random matrices

Cites work

• A sharp inverse Littlewood-Offord theorem
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Optimal inverse Littlewood-Offord theorems
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues

Cited in

(36)

• 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)