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.
Best Answer
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})$$