Invertibility of sparse non-Hermitian matrices

We consider 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 random variables, and {delta(i),(j)} are i.i.d. Bernoulli random variables taking value 1 with probability p(n), and prove a quantitative estimate on the smallest singular value for p(n) = Omega(log n/n); under a suitable assumption on the spectral norm of the matrices. This establishes the invertibility of a large class of sparse matrices. For p(n) = Omega(n(-alpha)) with some alpha is an element of (0,1), we deduce that the condition number of A(n) is of order n with probability tending to one under the optimal moment assumption on {xi(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 {xi(i,j)} are i.i.d. sub-Gaussian, we further show that a sparse random matrix is singular with probability at most exp(-cnp(n)) whenever p(n) is above the critical threshold p(n) = Omega(log n/n). The results also extend to the case when {xi(i,j)} have a non-zero mean. We further find quantitative estimates on the smallest singular value of the adjacency matrix of a directed Erdos-Reyni graph whenever its edge connectivity probability is above the critical threshold Omega(log n/n). (C) 2017 Elsevier Inc. All rights reserved.