On sparse random combinatorial matrices

Abstract

Let $Q_{n,d}$ denote the random combinatorial matrix whose rows are independent of one another and such that each row is sampled uniformly at random from the subset of vectors in $\{0,1{\}}^n$ having precisely $d$ entries equal to $1$. We present a short proof of the fact that $\mathrm{Pr}[\det (Q_{n,d})=0]=O\left(\frac{n^{1/2}{\log }^{3/2}n}{d}\right)=o(1)$, whenever $d=\omega (n^{1/2}{\log }^{3/2}n)$. In particular, our proof accommodates sparse random combinatorial matrices in the sense that $d=o(n)$ is allowed. We also consider the singularity of deterministic integer matrices $A$ randomly perturbed by a sparse combinatorial matrix. In particular, we prove that $\mathrm{Pr}[\det (A+Q_{n,d})=0]=O\left(\frac{n^{1/2}{\log }^{3/2}n}{d}\right)$, again, whenever $d=\omega (n^{1/2}{\log }^{3/2}n)$ and $A$ has the property that $(1,-d)$ is not an eigenpair of $A$.