Universality and the circular law for sparse random matrices

Abstract

The universality phenomenon asserts that the distribution of the eigenvalues of random matrix with i.i.d. zero mean, unit variance entries does not depend on the underlying structure of the random entries. For example, a plot of the eigenvalues of a random sign matrix, where each entry is +1 or -1 with equal probability, looks the same as an analogous plot of the eigenvalues of a random matrix where each entry is complex Gaussian with zero mean and unit variance. In the current paper, we prove a universality result for sparse random n by n matrices where each entry is nonzero with probability $1/n^{1-\alpha }$ where $0<\alpha \le 1$ is any constant. One consequence of the sparse universality principle is that the circular law holds for sparse random matrices so long as the entries have zero mean and unit variance, which is the most general result for sparse random matrices to date.

Published in at http://dx.doi.org/10.1214/11-AAP789 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (9)

• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Spectra of Sparse Random Matrices
• Cavity approach to the spectral density of non-Hermitian sparse matrices
• A simple invariance theorem
• Sparse regular random graphs: Spectral density and eigenvectors
• Spectrum of non-Hermitian heavy tailed random matrices
• Universal sum and product rules for random matrices
• Properties of Uniform Doubly Stochastic Matrices
• Sparse random graphs: Eigenvalues and Eigenvectors

Cited by in corpus (22)

• Around the circular law
• Exploratory Adaptation in Large Random Networks
• Circular law for random matrices with exchangeable entries
• Non-Hermitian random matrices with a variance profile (I): Deterministic equivalents and limiting ESDs
• Axions of Evil
• Spectrum of Markov generators on sparse random graphs
• Sparse Matrix Factorization
• Axionic Band Structure of the Cosmological Constant
• Latent Representation in Human-Robot Interaction with Explicit Consideration of Periodic Dynamics
• Cokernels of adjacency matrices of random $r$-regular graphs
• Antagonistic interactions can stabilise fixed points in heterogeneous linear dynamical systems
• Sparse General Wigner-type Matrices: Local Law and Eigenvector Delocalization
• The circular law for random regular digraphs with random edge weights
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Convergence of the spectral radius of a random matrix through its characteristic polynomial
• Circular Law for Random Block Band Matrices with Genuinely Sublinear Bandwidth
• Random Antagonistic Matrices
• Dense random regular digraphs: singularity of the adjacency matrix
• The Local Circular Law III: General Case
• Distribution of the number of pivots needed using Gaussian elimination with partial pivoting on random matrices
• Random reversible Markov matrices with tunable extremal eigenvalues
• The sparse circular law under minimal assumptions