Singularity of sparse random matrices: simple proofs. (15th January 2022)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Kwan, Matthew; Sauermann, Lisa
• Is Part Of: Combinatorics, probability and computing. Volume 31:Number 1(2022)
• Page Start: 21
• Page End: 28
• Publication Date: 2022-01-15
• Subjects: 60B20; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548321000146
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: Consider a random $n\times 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 $\min(p, 1-p)\geq (1+\varepsilon)\log n/n$ for any constant $\varepsilon>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.