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:
• Home • Research • Durham Research Online • Rank deficiency in sparse random GF matrices.

# Rank deficiency in sparse random GF matrices.

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

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