# Probability of a random $n \times n$ matrix over $\mathbb F_2$ being nonsingular

Given a random square matrix of size $n\times n$ in the field $\mathbb F_2$, what is the probability that its determinant is $1$? (This is also the probability that the matrix is non-singular, since $\mathbb F_2$ only has the elements $0$ and $1$.)

-
Just to supplement jpescter's answer, here is the link to a question of mine on SO, which gives Mathematica program to generate non-singular random matrices over $Z_p$. It also gives the link to the Dana Randal's article, where the algorithm was taken from. – Sasha Nov 22 '11 at 13:56

The probability that a matrix over $\mathbb{F}_2$ has determinant $1$ is

$$\frac{|SL_n(\mathbb{F}_2)|}{|\mathcal{M}_n(\mathbb{F}_2)|} = \frac{\displaystyle\prod_{k=0}^{n-1}(2^n - 2^k)}{2^{n^2}} = \prod_{k=1}^{n} \Big(1 - \frac{1}{2^k} \Big).$$

More generally, the probability that a matrix over $\mathbb{F}_q$ has determinant 1 is

$$\frac{|SL_n(\mathbb{F}_q)|}{|\mathcal{M}_n(\mathbb{F}_q)|} = \frac{\frac{1}{q-1}\displaystyle\prod_{k=0}^{n-1}(q^n - q^k)}{q^{n^2}} = \frac{1}{q-1}\prod_{k=1}^{n} \Big(1 - \frac{1}{q^k} \Big).$$

For an explanation on how to calculate $|SL_n(\mathbb{F}_q)|,$ see this note by Gabe Cunningham.

As this is too long for a comment, I've posted it as an addendum to my original answer. The probability does indeed converge to a positive limit as $n\rightarrow \infty.$ Observe,

\begin{align} \log \left(\prod_{n \in \mathbb{Z}_+}(1 - \frac{1}{q^n}) \right) &= \sum_{n \in \mathbb{Z}_+} \log \Big(1 - \frac{1}{2^n} \Big) \\ &= -\sum_{n \in \mathbb{Z}_+} \sum_{k \in \mathbb{Z}_+} \frac{1}{k} \left( \frac{1}{q^n} \right)^k \\ &= -\sum_{k \in \mathbb{Z}_+} \frac{1}{k} \left(\sum_{n \in \mathbb{Z}_+} \Big(\frac{1}{q^{k}} \Big)^n \right) \\ &= -\sum_{k \in \mathbb{Z}_+} \frac{1}{k} \left(\frac{q^{-{k}}}{1 - q^{-{k}}} \right) \\ &= -\sum_{k \in \mathbb{Z}_+} \frac{1}{k} \left(\frac{1}{q^{k} -1} \right) \\ &\gt -q\sum_{k \in \mathbb{Z}_+} \frac{1}{k} \Big(\frac{1}{q} \Big)^k \\ &= \log(1/q^q). \end{align}

It follows $\displaystyle\prod_{n \in \mathbb{Z}_+} \Big(1 - \frac{1}{q^n} \Big) > 1/q^q$, so the product converges.

-
It seems that there is something called $q$-Pochhammer symbol, such that $\prod^n_{k=1}(1-2^{-k})=(1/2;1/2)_n$. It seems that this actually converges: $(1/2;1/2)_\infty=0.2887880950866\dots$ – FUZxxl Oct 10 '11 at 0:02
The number even appears on oeis.org as A048651 – FUZxxl Oct 10 '11 at 0:14
The infinite product $\displaystyle \prod_{k=1}^\infty (1 - 2^{-k})$ does converge to a nonzero value because $\displaystyle \sum_{k=1}^\infty 2^{-k}$ converges. The result might be denoted by the Q-Pochhammer symbol $(1/2; 1/2)_\infty$. I don't know if there's any simpler expression than that. You could also write it as $\sum_{k=1}^\infty a(k) 2^{-k}$ where $a(k)$ is the number of partitions of $k$ into an odd number of distinct positive integers minus the number of partitions into an even number of distinct positive integers. – Robert Israel Oct 10 '11 at 0:31
For $n\geq 3$ we don't have $SL_n = GL_n$ anymore so I think the generalization part should read "determinant 0" instead of "determinant 1". – Ragib Zaman Oct 10 '11 at 3:09
@RagibZaman: I assume you mean $q \ge 3$, not $n \ge 3$. It's easy to see that $SL_n$ has index $q-1$ in $GL_n$, since determinant is a homomorphism of $GL_n$ onto the multiplicative group of ${\mathbb F}_q$. – Robert Israel Oct 10 '11 at 19:53