Rank deficiency in sparse random GF[2] matrices

R. W.R. Darling*, Mathew D. Penrose, Andrew R. Wade, Sandy L. Zabell

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Let M be a random m × n matrix with binary entries and i.i.d. rows. The weight (i.e., number of ones) of a row has a specified probability distribution, with the row chosen uniformly at random given its weight. Let N (n, m) denote the number of left null vectors in {0, 1}m for M (including the zero vector), where addition is mod 2. We take n, m → ∞, with m/n → α > 0, while the weight distribution converges weakly to that of a random variable W on {3, 4, 5,…}. Identifying M with a hypergraph on n vertices, we define the 2-core of M as the terminal state of an iterative algorithm that deletes every row incident to a column of degree 1. We identify two thresholds α and (Formula presented), and describe them analytically in terms of the distribution of W. Threshold α marks the infimum of values of α at which n-1 log E[N (n, m)] converges to a positive limit, while (Formula Presented) marks the infimum of values of α at which there is a 2-core of non-negligible size compared to n having more rows than non-empty columns. We have 1/2 ≤ α ≤ (Formula presented) ≤ 1, and typically these inequalities are strict; for example when W = 3 almost surely, α ≈ 0.8895 and (formula presented) ≈ 0.9179. for which N(n;m) α for which N (n, m) ≥ 2 in probability lies in [α, (Formula presented)] and is conjectured to equal (Formula presented). The random row-weight setting gives rise to interesting new phenomena not present in the case of non-random W that has been the focus of previous work.

Original languageEnglish (US)
Pages (from-to)1-36
Number of pages36
JournalElectronic Journal of Probability
Volume19
DOIs
StatePublished - 2014

Keywords

  • Ehrenfest model
  • Hypercycle
  • Hypergraph core
  • Large deviations
  • Null vector
  • Phase transition
  • Random allocation
  • Random sparse matrix
  • XORSAT

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Rank deficiency in sparse random GF[2] matrices'. Together they form a unique fingerprint.

Cite this