Invertibility of sparse non-Hermitian matrices

Abstract: We consider a class of sparse random matrices of the form

A_{n} = (x i_{i, j} d e l t a_{i, j})_{i, j = 1}^{n}

, where

x i_{i, j}

are i.i.d.~centered random variables, and

d e l t a_{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} = O m e g a (f r a c l o g 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} = O m e g a (n^{- a l p h a})

with some

a l p h a i n (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

x i_{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

x i_{i, j}

are i.i.d.~sub-Gaussian, we further show that a sparse random matrix is singular with probability at most

e x p (- c n p_{n})

whenever

p_{n}

is above the critical threshold

p_{n} = O m e g a (f r a c l o g n n)

. The results also extend to the case when

x i_{i, j}

have a non-zero mean. We further find quantitative estimates on the smallest singular value of the adjacency matrix of a directed ErdH{o}s-R'{e}yni graph whenever its edge connectivity probability is above the critical threshold

O m e g a (f r a c l o g n n)

.

Recommendations

Cites work

Cited in

(28)

This page was built for publication: Invertibility of sparse non-Hermitian matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q520368)