# 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

1 Scopus citations

## 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 language English (US) 1-36 36 Electronic Journal of Probability 19 https://doi.org/10.1214/EJP.v19-2458 Published - 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.