Rank of random binary matrix

Question

Let $A\in\{0,1\}^{m\times n}$ where $m \gg n$. Take this matrix to be over $\mathbb{R}^{m\times n}$ (not the binary field). What is the probability that said matrix will have full rank? Is there some condition on the difference between $m$ and $n$ so that the probability approaches $1$?

Answer 1

Let $A=[a_{i,j}]\in M_{m,n}(\{0,1\})$ where $m\geq n$. We assume that $A$ is a random matrix with $prob(a_{i,j}=1)=prob(a_{i,j}=0)=1/2$. Note that $A$ has full rank iff $\det(A^TA)\not=0$ (the columns are linearly independent). Let $p_{m,n}=prob(\det(A^TA)=0)$.

Proposition 1. $p_{m,n}$ is ALWAYS $>0$ and $<1$.

Proof. Clearly $p_{m,1}=prob(A=0)=2^{-m}$. Note that if $n\geq 2$ and if the first two columns of $A$ are equal, then $\det(A^TA)=0$; then $p_{m,n}\geq 2^{-m}$. Clearly, $p_{m,n}<1$ (random choosing $A=[I_n,0_{n,m-n}]^T$ has a positive probability).

Assume that $n$ is fixed. When $m$ increases, we add rows to the matrix $A$; then $(p_{m,n})_m$ is a decreasing sequence.

For instance $p_{10,2}\approx 340\times 10^{-5},p_{12,2}\approx 82\times 10^{-5},p_{15,2}\approx 8\times 10^{-5}$.

Proposition 2. The sequence $(p_{m,n})_m$ converges to $0$. Moreover, there is $\lambda_n<1$ s.t. $p_{m,n}=0(\lambda_n)^{m/n}$ when $m\rightarrow \infty$.

Proof. According to the above remark, it suffices to show that $\lim_{k\rightarrow \infty}p_{kn,n}=0$. Let $A\in M_{kn,n}(\{0,1\})$ s.t. $\det(A^TA)=0$; then $A=[A_1,\cdots,A_k]^T$ where $A_i\in M_{n,n}(\{0,1\})$ and $\det(A_i)=0$. Consequently $p_{kn,n}\leq (p_{n,n})^k$. According to Proposition 1, $p_{n,n}<1$ and we are done.

Answer 2

The probability is $1$, we only need $m\geq n$.

The probability that any given column is in the span of the other columns is zero, the measure of a proper subspace of $\mathbb R^m$ is 0.