Full-rank rectangular matrices over GF(2)

Question

Given positive integers $k$, $m$, $n$, let $A$ be an $m \times n$ matrix over $GF(2)$ constructed as follows. Let $X_1, \ldots, X_m$ be independent random subsets of $\{1,\ldots,n\}$ with cardinality $k$, and take $A_{i,j} = 1$ if $j \in X_i$, $0$ otherwise. What can be said about the probability $P(k,m,n)$ that $A$ has rank $m$ over $GF(2)$?

In particular, I suspect that there is some $t(k) > 1$ such that as $m, n \to \infty$ with $n/m < t(k) - \epsilon$, $P(k,m,n) \to 0$, while for $n/m > t(k) + \epsilon$, $P(k,m,n)$ is bounded below. Is this true?

Answer 1

Actually, something a bit stronger is true: For fixed $k\geq 3$ the threshold is sharp in the sense that above $t(k)$ the probability that $A$ is of full rank tends to $1$. In computer science this question has received a fair amount of study under the name of "random XOR-SAT". The existence of a threshold was apparently first shown by Creignou and Daude in 2003 (I haven't seen the paper and don't have access to it).

Dubois and Mandler determined the precise value of the threshold for $k=3$, and a recent preprint of Pittel and Sorkin extends this to larger $k$. The rough idea is to start by doing a peeling process -- if there's a column with exactly one non-zero entry, we can delete the column and the row of that entry without affecting whether the matrix has full rank. After repeatedly doing this and deleting any columns that are entirely $0$, we'll be left with a "core" matrix where each row has $k$ non-zero entries and each column has at least two non-zero entries.

What ends up being true (but requires a long technical argument to prove) is that the size of the core pretty much determines everything -- if the core has more rows than columns, it can't be full (row) rank, while if it has significantly more columns than rows it almost surely has full row rank.