THE CIRCULAR LAW FOR SPARSE NON-HERMITIAN MATRICES

• 成果类型: Article
• 署名作者: Basak, Anirban; Rudelson, Mark
• 署名单位: Tata Institute of Fundamental Research (TIFR); International Centre for Theoretical Sciences, Bengaluru; Weizmann Institute of Science; University of Michigan System; University of Michigan
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/18-AOP1310
• 发表日期: 2019
• 页码: 2359-2416
• 关键词: spectral measure; INVERTIBILITY; UNIVERSALITY; Markov

摘要

For a class of sparse random matrices of the form A(n) = (xi(i, j)delta(i, j))(i)(n), j=1 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 An/root np(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 np(n) > exp(c root 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 Erdos-Renyi graph with edge connectivity probability p(n).