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

Let M be an n × 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 = p n for some fixed constant p ∈ ( 0 , 1 / 2 ] . A recent result of Tran states that the smallest singular value s n ( M ) is bounded below by c p n − 1 / 2 with high probability. In this note, we establish a complementary upper bound for s n ( M ) , proving that ∀ ε > 0 P ( s n ( M ) ≤ d ε 2 n ) ≥ 1 − C p ( ε + 1 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 / 2 .