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

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?

• the probability as a function of $n$ the size of the matrix stabilizes very quickly with the increase of $n$. For $n=11$ you already get the correct $3$ digits – Orest Bucicovschi May 28 '18 at 8:50

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}$

• My major is not math, and I am courious with two points. (1) Does the group $GL(n,q)$ include all invertible $n\times n$ matrices over $GF(p^k)$ ? (2) The conclusion of the order of $GL(n,q)$ can be found in an ordinary textbook of group theory? – foool May 28 '18 at 7:10
• Yes GL(n,q) is all nxn invertible matrices over GF(q). It depends on the book, but usually. It's not actually that hard it's a basis counting argument over GF(q)^n. The number of nonzero vectors is (q^n-1). Then take a subspace spanned by the first vector you picked it has size q. So the number of vectors linearly independent from the first subspace is q^n-q. Now pick a vector from that set and then the subspace spanned by the first 2 vectors has size q^2. You can continue doing this till you have a basis. The total number of bases is the product and equal to the number of invertible matrices – N8tron May 28 '18 at 7:18

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)$.

• You can also prove $P(n,q)$ through reference to the size of $GL(n,q)$ through a tricky reverse reindexing: $$|GL(n,q)|=q^{n^2}\prod_{j=0}^{n-1}\left(1-q^{j-n}\right)=q^{n^2}\left(1-q^{-n}\right)\left(1-q^{1-n}\right)\cdots\left(1-q^{-1}\right)=q^{n^2}\prod_{k=1}^{n-1}\left(1-q^{-k}\right)$$ Thanks for the proof that $P(n,q)$ converges for a fixed $q$ I'd noticed that but had not proved it :) – N8tron May 28 '18 at 17:14