Invertibility of sparse non-Hermitian matrices.

We consider a class of sparse random matrices of the form A n = ( ξ i , j δ i , j ) i , j = 1 n , 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 p n , and prove a quantitative estimate on the smallest singular value for p n = Ω ( 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 = Ω ( n − α ) with some α ∈ ( 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 { ξ 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 ⁡ ( − c n p n ) whenever p n is above the critical threshold p n = Ω ( log ⁡ n n ) . 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 ⁡ n n ) . [ABSTRACT FROM AUTHOR]