The smallest singular value of random combinatorial matrices

Abstract

Let $Q_n$ be a random $n\times n$ matrix with entries in $\{0,1\}$ whose rows are independent vectors of exactly $n/2$ zero components. We show that the smallest singular value $s_n(Q_n)$ of $Q_n$ satisfies \[ \mathbb{P}\Big\{s_n(Q_n)\le \frac{\varepsilon}{\sqrt{n}}\Big\} \le C\varepsilon + 2 e^{-cn} \quad \forall \varepsilon \ge 0, \] which is optimal up to the constants $C,c>0$. This improves on earlier results of Ferber, Jain, Luh and Samotij, as well as Jain. In particular, for $\epsilon =0$, we obtain the first exponential bound in dimension for the singularity probability \[ \mathbb{P}\big\{Q_n \,\,\text{is singular}\big\} \le 2 e^{-cn}.\] To overcome the lack of independence between entries of $Q_n$, we introduce an arithmetic-combinatorial invariant of a pair of vectors, which we call a Combinatorial Least Common Denominator (CLCD). We prove a small ball probability inequality for the combinatorial statistic ${\sum }_{i=1}^n{a}_i{v}_{\ddot{I}ƒ(i)}$ in terms of the CLCD of the pair $(a,v)$, where $\ddot{I}ƒ$ is a uniformly random permutation of $\{1,2,\dots ,n\}$ and $a:=(a_1,\dots ,a_n),v:=(v_1,\dots ,v_n)$ are real vectors. This inequality allows us to derive strong anti-concentration properties for the distance between a fixed row of $Q_n$ and the linear space spanned by the remaining rows, and prove the main result.

27 pages + two appendices. Section 2.6 was rewritten. We also added an appendix by Jain, Sah and Sawhney. Update: We were recently informed that Proposition 3.4 has been proved earlier by Bero Roos [New inequalities for permanents and hafnians and some generalizations, arXiv:1906.06176v2]. As such we removed the proof of Proposition 3.4 and cited Bero Roos' paper instead