Probability of a $1000 \times 1000$ square matrix over $\mathbb{Z}_2$ having full rank

Question

There are only two entries, $0$ and $1$, over $\mathbb{Z}_2$. Thus, only $16$ possible $2\times2$ matrices over $\mathbb{Z}_2$, and $6$ of them have full rank:

$$\begin{pmatrix}0&1\\ 1&0\end{pmatrix} \quad \begin{pmatrix}1&1\\ 1&0\end{pmatrix} \quad \begin{pmatrix}0&1\\ 1&0\end{pmatrix} \quad \begin{pmatrix}0&1\\ 1&1\end{pmatrix} \quad \begin{pmatrix}1&1\\ 0&1\end{pmatrix} \quad \begin{pmatrix}1&0\\ 0&1\end{pmatrix}$$

Randomly generate a $n \times n$ matrix over $\mathbb{Z}_2$ (where $n$ is big, say, $1000$). What's the probability that the matrix has full rank?

Answer 1

The general linear group $GL(n,q)$ is the group of invertible $n\times n$ matrices over a field with $q$ elements (note $q=p^k$ for some prime $p$).

The order of $$|GL(n,q)|=\prod_{k=0}^{n-1}(q^n-q^k)$$

So the probability is $$\dfrac{1}{q^{n^2}}\prod_{k=0}^{n-1}(q^n-q^k)$$

For $n=2$ $q=2$ you get $\frac{1}{2^4}(2^2-2)(2^2-1)=\frac{6}{16}$

Answer 2

The probability that a random $n$-by-$n$ matrix over a field of $q$ elements is non-singular is $$P(n,q)=\prod_{k=1}^n\left(1-\frac1{q^k}\right).$$ To prove this, prove that the probability that the $k$-th row is linearly independent of the previous rows, conditional on those previous rows being linearly independent, is $1-1/q^{n+1-k}$.

As $n\to\infty$ for fixed $q$, $P(n,q)$ tends to a positive limit. Indeed $$\prod_{k=1}^\infty\left(1-\frac1{q^k}\right) =1-\frac1{q}-\frac1{q^2}+\frac1{q^5}+\frac1{q^7}-\cdots =1+\sum_{m=1}^\infty(-1)^m(q^{-m(3m-1)/2}+q^{{-m(3m+1)/2}})$$ by Euler's pentagonal number theorem. For large $n$, a few terms of this will give a good approximation to $P(n,q)$.