Investigate Invertibility of Sparse Symmetric Matrix

Abstract

In this paper, we investigate the invertibility of sparse symmetric matrices. We show that for an $n\times n$ sparse symmetric random matrix $A$ with $A_{ij} = δ_{ij} ξ_{ij}$ is invertible with high probability. Here, $δ_{ij}$s, $i\ge j$ are i.i.d. Bernoulli random variables with $\mathbb{P} \left(ξ_{ij}=1 \right) =p \ge n^{-c}$, $ξ_{ij}, i\ge j$ are i.i.d. random variables with mean 0, variance 1 and finite forth moment $M_4$, and $c$ is constant depending on $M_4$. More precisely, $$ s_{\rm min} (A) > \varepsilon \sqrt{\frac{p}{n}}. $$ with high probability.

arXiv admin note: substantial text overlap with arXiv:1102.0300, arXiv:1507.03525 by other authors