Research Repository

# Rank deficiency in sparse random GF matrices

## Authors

Richard W.R. Darling

Mathew D. Penrose

Professor

Sandy L. Zabell

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

### Citation

Darling, R. W., Penrose, M. D., Wade, A. R., & Zabell, S. L. (2014). Rank deficiency in sparse random GF matrices. Electronic Journal of Probability, 19, Article 83. https://doi.org/10.1214/ejp.v19-2458

Journal Article Type Article Sep 4, 2014 Sep 14, 2014 Sep 14, 2014 Oct 5, 2014 Oct 6, 2014 Electronic Journal of Probability Institute of Mathematical Statistics Peer Reviewed 19 83 https://doi.org/10.1214/ejp.v19-2458