Rank deficiency in sparse random GF[2] matrices

Research output: Contribution to journalArticle

71 Downloads (Pure)

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 α−, 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.
Original languageEnglish
Pages (from-to)1-36
Number of pages36
JournalElectronic Journal of Probability
Volume19
Issue number83
DOIs
Publication statusPublished - 14 Sep 2014

Fingerprint

Zero vector
Converge
Weight Distribution
Hypergraph
Iterative Algorithm
Null
Probability Distribution
Random variable
Binary
Denote
Incidents
Random variables
Probability distribution

Keywords

  • Random sparse matrix, null vector, hypercycle, random allocation, XORSAT, phase transition, hypergraph core, large deviations, Ehrenfest model

Cite this

Rank deficiency in sparse random GF[2] matrices. / Penrose, Mathew.

In: Electronic Journal of Probability, Vol. 19, No. 83, 14.09.2014, p. 1-36.

Research output: Contribution to journalArticle

@article{be9b5d3625fa4312b20038ffd16672da,
title = "Rank deficiency in sparse random GF[2] matrices",
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 α−, 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.",
keywords = "Random sparse matrix, null vector, hypercycle, random allocation, XORSAT, phase transition, hypergraph core, large deviations, Ehrenfest model",
author = "Mathew Penrose",
year = "2014",
month = "9",
day = "14",
doi = "10.1214/EJP.v19-2458",
language = "English",
volume = "19",
pages = "1--36",
journal = "Electronic Journal of Probability",
issn = "1083-6489",
publisher = "Institute of Mathematical Statistics",
number = "83",

}

TY - JOUR

T1 - Rank deficiency in sparse random GF[2] matrices

AU - Penrose, Mathew

PY - 2014/9/14

Y1 - 2014/9/14

N2 - 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.

AB - 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.

KW - Random sparse matrix, null vector, hypercycle, random allocation, XORSAT, phase transition, hypergraph core, large deviations, Ehrenfest model

UR - http://dx.doi.org/10.1214/EJP.v19-2458

UR - http://ejp.ejpecp.org/article/view/2458

U2 - 10.1214/EJP.v19-2458

DO - 10.1214/EJP.v19-2458

M3 - Article

VL - 19

SP - 1

EP - 36

JO - Electronic Journal of Probability

JF - Electronic Journal of Probability

SN - 1083-6489

IS - 83

ER -