Rank deficiency in sparse random GF[2] matrices

R.W.R. Darling, Mathew D. Penrose, Andrew R. Wade, Sandy L. Zabell

Electronic Journal of Probability, 19, paper no. 83, 2014. DOI: 10.1214/EJP.v19-2458

Abstract

Let $M$ be a random $m \times 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 $\mathcal{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 \to \infty$, with $m/n \to \alpha > 0$, while the weight distribution converges weakly to that of a random variable $W$ on $\{3, 4, 5, \ldots\}$. Identifying $M$ with a hypergraph on $n$ vertices, we define the {\em 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 $\alpha^*$ and $\underline{\alpha\mkern-4mu}\mkern4mu$, and describe them analytically in terms of the distribution of $W$. Threshold $\alpha^*$ marks the infimum of values of $\alpha$ at which $n^{-1} \log \mathbb{E} \mathcal{N} (n,m)$ converges to a positive limit, while $\underline{\alpha\mkern-4mu}\mkern4mu$ marks the infimum of values of $\alpha$ 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 \leq \alpha^* \leq \underline{\alpha\mkern-4mu}\mkern4mu \leq 1$, and typically these inequalities are strict; for example when $W = 3$ almost surely, $\alpha^* \approx 0.8895$ and $\underline{\alpha\mkern-4mu}\mkern4mu \approx 0.9179$. The threshold of values of $\alpha$ for which $\mathcal{N} (n,m) \geq 2$ in probability lies in $[\alpha^*, \underline{\alpha\mkern-4mu}\mkern4mu]$ and is conjectured to equal $\underline{\alpha\mkern-4mu}\mkern4mu$.

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.