8
$\begingroup$

Is it known how the number of involutions in $GL_n(2)$, the group of $n\times n$ matrices over $\mathbb{Z}/2\mathbb{Z}$, behaves as $n\to\infty$ ?

Equivalently, one may ask this for the number of $n\times n$ matrices $A$ over $\mathbb{Z}/2\mathbb{Z}$ satisfying $A^2=0$, as $(A+I)^2=I \mod 2$.

Needless to say, there are $\lfloor n/2\rfloor$ conjugacy classes of involutions in $GL_n(2)$, and one can write down formula for the centraliser order for each class,

$$\frac{\left|GL_n(2)\right|}{2^{k^2+2k(n-2k)}\left|GL_k(2)\right|\left|GL_{n-2k}(2)\right|},\quad 1\leq k\leq \left\lfloor \frac{n}{2} \right\rfloor,$$

but it's quite a mess to just sum them up.

$\endgroup$
5
  • $\begingroup$ Have you tried calculating the first few terms, then consulting the Online Encyclopedia of Integer Sequences? $\endgroup$ Sep 30, 2015 at 3:01
  • $\begingroup$ yes I did. No such sequence is known, apparently. $\endgroup$ Sep 30, 2015 at 3:31
  • 2
    $\begingroup$ Rod Gow informs me that A. A. Kirillov and A. Melnikov answered this question in a paper dating from 1995: www.emis.de/journals/SC/1997/2/pdf/smf_sem-cong_2_35-42.pdf $\endgroup$ Sep 30, 2015 at 14:05
  • 1
    $\begingroup$ John, this paper talks a lot about solutions of $X^2=0$ in upper triangular matrices over a finite field, but does not mention $GL$. $\endgroup$ Sep 30, 2015 at 16:36
  • 1
    $\begingroup$ I guess this question led to this paper by Jason Fulman, Robert Guralnick, and Dennis Stanton arxiv.org/abs/1602.03611 $\endgroup$
    – j.c.
    Sep 27, 2017 at 15:51

2 Answers 2

3
$\begingroup$

We may write $|{\rm GL}(n,2)| = 2^{n^{2}} \prod_{j=1}^{n}( 1- \frac{1}{2^{j}}).$ As $n \to \infty$, the rightmost factor tends to $\left( \sum_{r=0 }^{\infty} \frac{p(r)}{2^{r}} \right)^{-1}$, where $p(r)$ is the number of partitions of $r$. Let us write $|{\rm GL}(n,2)| = 2^{n^{2}}f(n)$.

Then we see that the number of involutions of ${\rm GL}(n,2)$ is given by $\sum_{k = 1}^{\lfloor \frac{n}{2} \rfloor} 2^{2k(n-k)} \frac{f(n)}{f(k)f(n-2k)}$ using the formula given in the question ( if $k = \frac{n}{2}$, we should interpret $|{\rm GL}(n-2k,2)|$ as $1$).

Hence the number of involutions in ${\rm GL}(n,2)$ may be expressed as

$2^{\frac{n^{2}}{2}} \left(\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} 2^{- 2\left(\frac{n}{2}-k\right)^{2}}\left( \frac{\prod_{j=k+1}^{n}( 1- \frac{1}{2^{j}})}{ \prod_{m=1}^{n-2k}( 1- \frac{1}{2^{m}})}\right)\right)$ if $n$ is odd, and $2^{\frac{n^{2}}{2}} \left( \prod_{j=\frac{n}{2}+1}^{n}( 1- \frac{1}{2^{j}})+ \sum_{k=1}^{\lfloor \frac{n}{2} \rfloor-1} 2^{- 2\left(\frac{n}{2}-k\right)^{2}}\left( \frac{\prod_{j=k+1}^{n}( 1- \frac{1}{2^{j}})}{ \prod_{m=1}^{n-2k}( 1- \frac{1}{2^{m}})}\right)\right)$ if $n$ is even.

Hence when $n$ is even, the number of involutions is at most $2^{\frac{n^{2}}{2}} \prod_{j=\frac{n}{2}+1}^{n}( 1- \frac{1}{2^{j}}) \left( 1 + \frac{1}{\prod_{m=1}^{n-2}( 1- \frac{1}{2^{m}})} \left( \sum_{k=1}^{\frac{n}{2}} 2^{- 2(\frac{n}{2}-k)^{2}}\right)\right)$ and is at least $2^{\frac{n^{2}}{2}} \prod_{j=\frac{n}{2}+1}^{n}( 1- \frac{1}{2^{j}})$.

As (even) $n \to \infty$, the first product appearing approaches $1$ from below and (the reciprocal of) the second product appearing tends to $\sum_{r=0}^{\infty} \frac{p(r)}{2^{r}}$, while the inner sum is at most $\sum_{j=0}^{\infty} \left(\frac{1}{4} \right)^{j^{2}}$.

I omit the similar analysis when $n$ is odd.

$\endgroup$
5
$\begingroup$

As a matter of fact, OEIS has the corresponding integer sequence A053722, although shifted by 1, as it corresponds to the number of solutions to $X^2=1$ in $GL_n(2)$, i.e. it counts the identity along with the involutions. I thought OEIS does this kind of elementary transformations of sequences automatically, but in fact it does not.

Incidentally, this (shifted) number can be obtained as the sum of dimensions of real representations of $GL_n(2)$, see e.g. paper by Fulman and Vinroot.

This still does not answer the original question, though.

$\endgroup$
5
  • $\begingroup$ The summation given in OEIS seems routine for asymptotic estimation. $\endgroup$ Oct 3, 2015 at 1:37
  • $\begingroup$ I added a formula for each of [n/2] terms (plus the term for k=0, which should be 1, assuming $|GL_0(k)|=1$) in the question, but it does not look routine... $\endgroup$ Oct 3, 2015 at 4:09
  • $\begingroup$ The ratio of consecutive terms is easy to calculate and from that the dominant terms can be identified. It looks pretty messy, but not fundamentally difficult. $\endgroup$ Oct 3, 2015 at 4:57
  • $\begingroup$ Well, I only did such things for ordinary hypergeometric functions, not for basic hypergeometric ones, like here. Any place to look for these things? $\endgroup$ Oct 3, 2015 at 5:37
  • $\begingroup$ OK, I think I'm being lazy, I should just sit down and calculate :-) $\endgroup$ Oct 3, 2015 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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