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$.)
Probability of a random $n \times n$ matrix over $\mathbb F_2$ being nonsingular
-
1Just to supplement jpescter's answer, here is the [link](http://stackoverflow.com/questions/5771217/how-to-efficiently-set-matrixs-minor-in-mathematica) 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](http://www.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-658.pdf), where the algorithm was taken from. – 2011-11-22
1 Answers
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.
-
0At a glance from the plot, it seems that this function converges to something above 0.28; is that possible? And if not, is it possible to give asymptotics? – 2011-10-09
-
0Sorry, I mistyped... It seems to converge to [0.288788...](http://www.wolframalpha.com/input/?i=+%5Cprod_%7Bk%3D1%7D%5E%7Bn%7D%281+-+%5Cfrac%7B1%7D%7B2%5Ek%7D%29+where+n+%3D+10000000), but it might also be that it just falls infinitly, but extremly slow. – 2011-10-09
-
1It 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](http://www.wolframalpha.com/input/?i=QPochhammer%5B1%2F2%5D): $(1/2;1/2)_\infty=0.2887880950866\dots$ – 2011-10-10
-
1The number even appears on `oeis.org` as [`A048651`](http://oeis.org/A048651) – 2011-10-10
-
2The 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. – 2011-10-10
-
0Shouldn't you be evaluating the ratio for $SL_n$ rather than $GL_n$? It would seem you've only computed the probability a matrix is invertible instead of the probability it has determinant 1. Also, for completeness, I think you could also do a general calculation for $\mathbb{F}_q$ and provide links on how the order of matrix groups over finite fields are actually derived. – 2011-10-10
-
0@anon. We're working over $\mathbb{F}_2$ so $SL_n = GL_n.$ I think the downvote is uncalled for. – 2011-10-10
-
0@jspecter: I didn't downvote (the score is +3,-0 in case you can't see it yourself at this time). You're right they coincide for $q=2$, but perhaps you could have mentioned that or why it was true? – 2011-10-10
-
0@ anon. My b. Someone must have taken away their vote. I'll incorporate a remark about the general case. – 2011-10-10
-
1For $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". – 2011-10-10
-
1@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$. – 2011-10-10