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 $\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 $\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$.
Categories: math.CO math.PR