Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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

1 Answer 1

up vote 12 down vote accepted

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.

share|improve this answer
1  
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
1  
The number even appears on oeis.org as A048651 –  FUZxxl Oct 10 '11 at 0:14
2  
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
1  
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
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$. –  Robert Israel Oct 10 '11 at 19:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.