The circular law for sparse non-Hermitian matrices

Abstract

For a class of sparse random matrices of the form $A_n=({\xi }_{i,j}{\delta }_{i,j}{)}_{i,j=1}^n$, where $\{{\xi }_{i,j}\}$ are i.i.d.~centered sub-Gaussian random variables of unit variance, and $\{{\delta }_{i,j}\}$ are i.i.d.~Bernoulli random variables taking value $1$ with probability $p_n$, we prove that the empirical spectral distribution of $A_n/\sqrt{n{p}_n}$ converges weakly to the circular law, in probability, for all $p_n$ such that $p_n=\omega ({\log }^{2}n/n)$. Additionally if $p_n$ satisfies the inequality $n{p}_n>\exp (c\sqrt{\log n})$ for some constant $c$, then the above convergence is shown to hold almost surely. The key to this is a new bound on the smallest singular value of complex shifts of real valued sparse random matrices. The circular law limit also extends to the adjacency matrix of a directed Erdős-Rényi graph with edge connectivity probability $p_n$.

arXiv comment55 pages, Section 9 shortened, presentation improved, proof of Theorem 1.7 is removed from this version. For its proof we refer the reader to V1