On sparse random combinatorial matrices


الملخص بالإنكليزية

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] = Oleft(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]=Oleft(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$.

تحميل البحث