Invertibility of Sparse non-Hermitian matrices

Understand

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(\frac{\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 \in (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.