Rank deficiency in sparse random GF[2] matrices

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