# Probability that a random binary matrix will have full column rank?

If $S = \{ A_{m \times n} : m > n, A_{ij} \in \{0,1\} \},$ is the set of all $m \times n$ binary matrices, and I choose a random matrix $r \in S$, what would be the probability that $r$ would have full column rank (each of the n columns would be linearly independent)?

Several papers simply claim that this probability is very high, but I'm curious as to what the exact probability would be, and how to compute it.

• This seems to be already hard to answer in the case $m=n$ (even if it is excluded in the question it would probably follow from a solution). See math.stackexchange.com/questions/54246/… Commented Nov 12, 2013 at 22:07
• Even for the $n\times n$ case the probability is only conjectured. (ref) Commented Nov 12, 2013 at 23:04

Let $m>n$, and $\{v_1,\ldots,v_{n+1}\}$ be random vectors in $\mathbb{F}^m_2$. Call $p_n$ the probability that $\{v_1,\ldots,v_n\}$ are linearly independent.
In that case, $\{v_1,\ldots,v_{n+1}\}$ are independent (event $A_n$) if and only if $\{v_1,\ldots, v_n\}$ are independent and $v_{n+1} \notin \left<v_1,\ldots,v_n\right>$ (event $B_n$).
$$p_{n+1} = P(A_n \cap B_n) = P(A_n)P(B_n|A_n) = (1-2^{n-m})p_n$$
$p_1 = (1-2^{-m})$, since a single vector is independent if and only if it's not $0$, so: $$p_n = \prod_{i=1}^n (1-2^{i-1-m})$$