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

Let $M$ 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, with $d=pn$ for some fixed constant $p\in (0,1\mathrm{/}2]$. A recent result of Tran states that the smallest singular value $s_n(M)$ is bounded below by $c_p{n}^{-1\mathrm{/}2}$ with high probability. In this note, we establish a complementary upper bound for $s_n(M)$, proving that $$\mathrm{\forall }\epsilon >0\mathbb{P}(s_n(M)\le \frac{\sqrt{d}}{{\epsilon }^{2}n})\ge 1-C_p(\epsilon +\frac{1}{\sqrt{d}}),$$where $C_p$ is a positive constant depending only on $p$. This result confirms that the least singular value $s_n(M)$ of dense random combinatorial matrices is typically of the order $n^{-1\mathrm{/}2}$.