Some interesting tips on binary random matrices again. Kolchin’s book also discusses some aspects of this (see Page 126 for example). It is interesting to see the asymptotic behaviour.

The probability that a random matrix {k \times (k+m)} binary matrix with each element chosen uniformly ({0} and {1} picked equally likely), is of full rank { k} for {m \ge 0} is

\displaystyle\rho =\prod_{i=m+1}^{\infty}{\left(1-\frac{1}{2^{i}}\right)}, \quad m=0,1,2,\ldots\ \ \ \ \ (1)

The probability that a random matrix k \times (k+m) binary matrix with each element chosen uniformly ({0} and 1 picked equally likely), is of full rank k+m  for m < 0 is

\displaystyle\rho =\prod_{i=1}^{k+m}{\left(1-\frac{1}{2^{k-i+1}}\right)}, \quad m=-1,-2,\ldots\ \ \ \ \ (2)