An upper bound on the smallest singular value of dense signed random combinatorial matrices

Source abstract

Let $M_n$ be an $n\times n$ random matrix with entries in $\{-1, 0, 1\}$, where each row is independently and uniformly sampled from the set of all vectors in $\{-1, 0, 1\}^n$ containing exactly $d$ nonzero entries, with $d=pn$ for some fixed constant $p\in(0,1/2]$. A recent result by one of the authors gives a lower bound of order $n^{-1/2}$ for the smallest singular value $s_n(M_n)$ of this model with high probability. In this paper, we establish a matching upper bound for $s_n(M_n)$. Specifically, there exists a constant $C_p>0$ depending only on $p$ such that $$\forall \varepsilon >0 \qquad \mathbb{P} \left( s_n(M_n) \le \frac{\sqrt{d}}{\varepsilon^2 n} \right) \ge 1-C_p\left(\varepsilon + \frac{1}{\sqrt{d}}\right).$$ Consequently, in the dense regime, the smallest singular value $s_n(M_n)$ of signed random combinatorial matrices is typically of order $n^{-1/2}$.