We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Rank deficiency in sparse random GF[2] matrices.

Darling, Richard W. R. and Penrose, Mathew D. and Wade, Andrew R. and Zabell, Sandy L. (2014) 'Rank deficiency in sparse random GF[2] matrices.', Electronic journal of probability., 19 . p. 83.


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.

Item Type:Article
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:This work is licensed under a Creative Commons Attribution 3.0 License (CC BY 3.0).
Date accepted:04 September 2014
Date deposited:06 October 2014
Date of first online publication:14 September 2014
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar