On the singularity of random Bernoulli matrices -- novel integer partitions and lower bound expansions

DOI10.1007/S00026-013-0176-7zbMATH Open1320.60020arXiv1105.2834OpenAlexW1989937807MaRDI QIDQ360357FDOQ360357

Stephen DeSalvo, Richard Arratia

Publication date: 26 August 2013

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: We prove a lower bound expansion on the probability that a random $pm1$ matrix is singular, and conjecture that such expansions govern the actual probability of singularity. These expansions are based on naming the most likely, second most likely, and so on, ways that a Bernoulli matrix can be singular; the most likely way is to have a null vector of the form $e_{i}pm{e}_j$, which corresponds to the integer partition 11, with two parts of size 1. The second most likely way is to have a null vector of the form $e_{i}pm{e}_{j}pm{e}_{k}pm{e}_{e}ll$, which corresponds to the partition 1111. The fifth most likely way corresponds to the partition 21111. We define and characterize the "novel partitions" which show up in this series. As a family, novel partitions suffice to detect singularity, i.e., any singular Bernoulli matrix has a left null vector whose underlying integer partition is novel. And, with respect to this property, the family of novel partitions is minimal. We prove that the only novel partitions with six or fewer parts are 11, 1111, 21111, 111111, 221111, 311111, and 322111. We prove that there are fourteen novel partitions having seven parts. We formulate a conjecture about which partitions are "first place and runners up," in relation to the ErdH{o}s-Littlewood-Offord bound. We prove some bounds on the interaction between left and right null vectors.

Full work available at URL: https://arxiv.org/abs/1105.2834

Recommendations

• On the singularity probability of random Bernoulli matrices
• Singularity of random Bernoulli matrices
• Singularity of sparse Bernoulli matrices
• Singularity of random symmetric matrices revisited
• On random ±1 matrices: Singularity and determinant

zbMATH Keywords

integer partitionsBernoulli matricesrandom \(\pm 1\) matrices

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05)

Cites Work

• Random graphs.
• Title not available (Why is that?)
• On the singularity probability of discrete random matrices
• On the singularity probability of random Bernoulli matrices
• On the Probability That a Random ± 1-Matrix Is Singular
• On a lemma of Littlewood and Offord
• On subspaces spanned by random selections of \(\pm 1\) vectors
• On random ±1 matrices: Singularity and determinant
• On a class of (0,1) matrices with vanishing determinants

Cited In (5)

• Matrix representations for a certain class of combinatorial numbers associated with Bernstein basis functions and cyclic derangements and their probabilistic and asymptotic analyses
• Probabilistic divide-and-conquer: deterministic second half
• Recent progress in combinatorial random matrix theory
• Irreducibility of Random Polynomials
• Sequential metric dimension for random graphs

Uses Software

• Mathematica

This page was built for publication: On the singularity of random Bernoulli matrices -- novel integer partitions and lower bound expansions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q360357)