Singularity of sparse random matrices: simple proofs. (15th January 2022) - Ferber, Asaf; Kwan, Matthew; Sauermann, Lisa
Abstract: Consider a random n× n zero-one matrix with 'sparsity' p, sampled according to one of the following two models: either every entry is independently taken to be one with probability p (the 'Bernoulli' model) or each row is independently uniformly sampled from the set of all length- n zero-one vectors with exactly pn ones (the 'combinatorial' model). We give simple proofs of the (essentially best-possible) fact that in both models, if (p, 1-p)≥ (1+ε)n/n for any constant ε>0, then our random matrix is nonsingular with probability 1-o(1) . In the Bernoulli model, this fact was already well known, but in the combinatorial model this resolves a conjecture of Aigner-Horev and Person.