12
$\begingroup$

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

  • 1
    Just 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 1

13

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.

  • 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