Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5778597 | Advances in Mathematics | 2017 | 58 Pages |
Abstract
We consider a class of sparse random matrices of the form An=(ξi,jδi,j)i,j=1n, where {ξi,j} are i.i.d. centered random variables, and {δi,j} are i.i.d. Bernoulli random variables taking value 1 with probability pn, and prove a quantitative estimate on the smallest singular value for pn=Ω(logâ¡nn), under a suitable assumption on the spectral norm of the matrices. This establishes the invertibility of a large class of sparse matrices. For pn=Ω(nâα) with some αâ(0,1), we deduce that the condition number of An is of order n with probability tending to one under the optimal moment assumption on {ξi,j}. This in particular, extends a conjecture of von Neumann about the condition number to sparse random matrices with heavy-tailed entries. In the case that the random variables {ξi,j} are i.i.d. sub-Gaussian, we further show that a sparse random matrix is singular with probability at most expâ¡(âcnpn) whenever pn is above the critical threshold pn=Ω(logâ¡nn). The results also extend to the case when {ξi,j} have a non-zero mean. We further find quantitative estimates on the smallest singular value of the adjacency matrix of a directed ErdÅs-Réyni graph whenever its edge connectivity probability is above the critical threshold Ω(logâ¡nn).
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematics (General)
Authors
Anirban Basak, Mark Rudelson,