Least singular values of shifted sparse random combinatorial matrices

Abstract

Let $M_n$ be an $n\times n$ random matrix with entries in $\{0,1\}$, where each row is independently and uniformly sampled from the set of all vectors in $\{0,1{\}}^n$ containing exactly $d$ ones. we establish quantitative lower bounds on the smallest singular value of the shifted matrices $M_n-z{\mathbf{I}}_n$ whenever $|z|\le \sqrt{d}\log \log d$ and $C\log n\le d\le n/2$ for some absolute positive constant $C$. As an application, we show that the empirical spectral distribution of the appropriately rescaled matrix $M_n$ converges in probability to the circular law provided that ${\log }^{2+\epsilon }n\le d=o(n)$ for some fixed $\epsilon \in (0,1)$.