Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How to deduce a formula (see below) for number of conjugacy classes in GL_n(F_2) ? (More generally F_q) ? Is there some description of conjugacy classes or we just know how many of them but do not know how to describe them ?

Can someone send me a paper, please ?: "Pairs of commuting matrices over a finite field" Walter Feit and N. J. Fine


FORMULA from OEIS The number a(n) of conjugacy classes in the group GL(n, q) is the coefficient of t^n in the infinite product: product k=1, 2, ... (1-t^k)/(1-qt^k) - Noam Katz (noamkj(AT)hotmail.com), Mar 30 2001.

Simple observations

Clearly if characteristic polynom is different then matrices are not conjugated. For each char. pol. it is easy to give a matrix with such char. pol. so we get (q-1)q^{n-1} possibilities at least.

But if char. pol has a roots with multiplicities - then we may have several Jordan cells and several conjugacy classes with same characteristic polynomial. So it is not clear for me how to count them.

Diagonal elements of corresponding Jordan cells may not live in F_q but in some alg. extentsion of it, these makes me completely puzzled - is it possible to control this ? Hardly...

Related and not so much but nice questions :)

Number of conjugacy classes in generic finite group?

Sizes of twisted conjugacy classes of $PSL(n,q)$

How many conjugacy classes of subgroups does GL(2,p) have?

Decomposition of GL(2,p) into irreducible representations

Centralizers in GL(n,p)

Products of Conjugacy Classes in S_n

The number of conjugacy classes and the order of the group

Arithmetic relations between degrees of irrchar and cardinals of conjugacy classes

Can we bound degrees of complex irreps in terms of the average conjugacy class size?

Symmetric group irreps in tensor products of exterior products of the standard representation

share|improve this question
The rational canonical form gives you an explicit (very nice btw) description for your problem over any field. I see now Geoff Robinson commented about this below. Or is there some additional detail you are looking for, what this theory does not provide? –  plusepsilon.de Aug 11 '12 at 11:31
Another reference is Exercise 1.190 of Enumerative Combinatorics, vol. 1, second ed. See math.mit.edu/~rstan/ec/ec1.pdf. For fixed $n$, the number of conjugacy classes is a polynomial in $q$ of the form $q^n-q^{\lfloor (n-1)/2\rfloor}+O(q^{\lfloor (n-1)/2\rfloor -1})$. Additional properties of this polynomial appear in this exercise. –  Richard Stanley Aug 12 '12 at 9:36
@Richard Statnley Thank you very much ! @Mrc Plm May be you are right... –  Alexander Chervov Aug 13 '12 at 6:32
Related question: mathoverflow.net/questions/8415/… –  Alexander Chervov Sep 8 '12 at 13:15
show 2 more comments

3 Answers

Thinking about Jordan form with rationality considerations taken into account a slightly different way than in the question may be useful: conjugacy classes are in bijection with "elementary divisor forms", meaning writing the vector space as a $R=\mathbb F_q[x]$-module of the form $R/d_1\oplus \ldots\oplus R/d_\ell$, where the monic elementary divisors satisfy $d_1|\ldots|d_\ell$, and (for invertibility) $x$ does not divide $d_\ell$.

Thus, the counting can be done without necessarily classifying or counting irreducibles and adding up. More simply, the number of monic polynomials of degree $d$ with non-vanishing constant term is obviously $q^d-q^{d-1}$.

share|improve this answer
That number incidentally gives a count of the number of conjugacy classes of elements of order prime to $p$ (ie semisimple conjugacy classes) in ${\rm GL}(n,q),$ where $q$ is a power of the prime $p.$ This is because for each choice of characteristic polynomial, there is just one way to make the minimum polynomial multiplicity free. –  Geoff Robinson Aug 11 '12 at 1:30
@Paul thank you very much ! –  Alexander Chervov Aug 11 '12 at 19:40
add comment

Edit: Unfortunately, the first version of this answer was wrong, so I had to rewrite it almost entirely.

So the formula you want to prove is: $$ \sum_{n=1}^\infty C_{n,q} t^n =\prod_{k=1}^\infty \frac{1-t^k}{1-qt^k} $$ where $C_{n,q}$ denotes the number of conjugacy classes in $\textrm{GL}_n(q)$.

Note that $$ \frac{1-t^k}{1-qt^k} =1+\sum_{i=1}^\infty (q^i-q^{i-1}) t^{ki} $$ As Paul Garrett notes in his answer, $q^i-q^{i-1}$ is the number of monic polynomials in $\mathbb F_q[x]$ of degree $i$ with non-vanishing constant term. One usual way of counting conjugagy classes of matrices in $\textrm{GL}_n(q)$ (or $\textrm{Mat}_n(\mathbb F_q)$, if one admits the eigenvalue $0$) is counting isomorphism classes of $\mathbb F_q[x]$-modules of dimension $n$, which by the structure theorem on f.g. modules over PID's are given by $$ \mathbb F_{q}[x]/(p_k(x)) \oplus \mathbb F_{q}[x]/(p_k(x)\cdot p_{k-1}(x)) \ldots \oplus F_{q}[x]/(p_k(x)\cdot p_{k-1}(x)\cdots p_{1}(x)) $$ where $p_1,\ldots,p_k$ are monic polynomials with constant term $\neq 0$ (uniquely determined by the isomorphism type of the module) such that $1\cdot \textrm{deg}(p_1)+2\cdot \textrm{deg}(p_2) \ \ldots + k \cdot \textrm{deg}(p_k) = n \textrm{ (the dimension of the module)}$. Note that some of the $p_i$ may very well be equal to $1$.

From the above considerations it is clear that we can parametrize isomorphism classes of $\mathbb F_q[x]$-modules by giving a sequence of monic polynomials which eventually becomes constant $=1$, by letting the module given above correspond to the sequence $$ (f_1,f_2,f_3,\ldots) =(p_k, p_{p-1},\ldots,p_1,1,1,\ldots) $$ Note that in this sequence, $f_m$ constributes $m\cdot \textrm{deg}(f_m)$ to the dimension of the module. It follows $$ \begin{array}{rcl} \sum_{n=1}^\infty C_{n,q} t^n &=& \prod_{m=1}^{\infty}\left(\sum_{i=0}^\infty \#\textrm{(choices for $f_m$ that contribute $mi$ to the dimension)}\cdot t^{mi}\right)\newline &=&\prod_{m=1}^{\infty} \left(1+\sum_{i=1}^\infty (q^i-q^{i-1}) t^{mi}\right) =\prod_{m=1}^\infty \frac{1-t^m}{1-qt^m} \end{array} $$

share|improve this answer
Again, in the non-algebraically closed situation, it's rational canonical form which parametrizes the conjugacy classs in ${\rm GL}(n,q)$. –  Geoff Robinson Aug 11 '12 at 7:42
@Geoff: I really don't see your problem. What I'm counting here are rational canonical forms of matrices (or some sort of rational canonical form). This is often referred to as generalized Jordan normal form, I don't think using the term "Jordan normal form" exclusively in the algebraically closed context is necessarily standard terminology. –  Florian Eisele Aug 11 '12 at 9:11
There is no problem. I was just saying that the standard, well-known and classical way to parametrize the conjugacy classes of ${\rm GL}(n,F)$ for any field $F$ is via the rational canonical form. This is well-known and in many algebra texts. As for Jordan form, it is certainly true that people in algebraic groups speak of the Jordan decomposition of an an element in the form $su =us$ with $s$ semisimple and $u$ unipotent, and use that in a non-necessarily algebraically closed situation. –  Geoff Robinson Aug 11 '12 at 9:52
The original version of this answer was wrong. The edit should take care of those issues. –  Florian Eisele Aug 11 '12 at 11:15
@Florian Thank you very much for yours kind answer, give time to wrap my mind over it:). –  Alexander Chervov Aug 11 '12 at 19:38
show 2 more comments

The correct paper is J.A. Green's 1955 paper.

share|improve this answer
That goes much further, and constructs the irreducible complex characters of ${\rm GL}(n,q).$ –  Geoff Robinson Aug 11 '12 at 7:39
I believe this is the primary source for the result the OP alludes to. –  Igor Rivin Aug 11 '12 at 15:34
I don't think the result is in there. The generating function for the number of conjugacy classes given on page 408 isn't the same as the one given by the OP (at least not obviously so). And the existence of this generating function is more of a side-remark in this paper. –  Florian Eisele Aug 11 '12 at 16:00
@Igor OEIS cites Feit, Fine. –  Alexander Chervov Aug 11 '12 at 19:36
@alexander: Feit and Fine five years later, and in a slightly different subject. OEIS is just wrong. –  Igor Rivin Aug 11 '12 at 23:16
add comment

Your Answer


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.