Skip to main content

Research Repository

Advanced Search

Rank deficiency in sparse random GF[2] matrices

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

Rank deficiency in sparse random GF[2] matrices Thumbnail


Richard W.R. Darling

Mathew D. Penrose

Sandy L. Zabell


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 α−, and describe them analytically in terms of the distribution of W. Threshold α∗ marks the infimum of values of α at which n−1logE[N(n,m)] converges to a positive limit, while α− 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≤α∗≤α−≤1, and typically these inequalities are strict; for example when W=3 almost surely, α∗≈0.8895 and α−≈0.9179. The threshold of values of α for which N(n,m)≥2 in probability lies in [α∗,α−] and is conjectured to equal α−. 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.


Darling, R. W., Penrose, M. D., Wade, A. R., & Zabell, S. L. (2014). Rank deficiency in sparse random GF[2] matrices. Electronic Journal of Probability, 19, Article 83.

Journal Article Type Article
Acceptance Date Sep 4, 2014
Online Publication Date Sep 14, 2014
Publication Date Sep 14, 2014
Deposit Date Oct 5, 2014
Publicly Available Date Oct 6, 2014
Journal Electronic Journal of Probability
Publisher Institute of Mathematical Statistics
Peer Reviewed Peer Reviewed
Volume 19
Article Number 83


You might also like

Downloadable Citations