# Difference between revisions of "Conjugacy class size formula in general linear group over a finite field"

This article gives formula(s) for the conjugacy class sizes in a general linear group of finite degree $n$ over a finite field with $q$ elements, which we denote by $GL(n,q)$.

## Case of semisimple elements

### Elements diagonalizable over $\mathbb{F}_q$

Suppose $g \in GL(n,q)$ is diagonalizable over $\mathbb{F}_q$, with eigenvalues $\lambda_1, \dots, \lambda_k$ having multiplicities $r_1,r_2,\dots,r_k$ respectively (the $\lambda_i$s are all distinct). Note that $\sum_{i=1}^k r_i = n$.

Further, let's say that among the $r_i$s, there are $s_1$ 1s, $s_2$ 2s, and so on till $s_n$ $n$s.

Then, the centralizer of the diagonal representative of this conjugacy class is isomorphic to:

$GL(r_1,q) \times GL(r_2,q) \times GL(r_3,q) \times \dots \times GL(r_k,q)$

In fact, if the diagonal entries are arranged so that all the $\lambda_1$s occur first, then the $\lambda_2$s, and so on, then the centralizer is the set of invertible block diagonal matrices with blocks of sizes $r_1, r_2, \dots, r_k$.

Item Value Degree as polynomial in $q$ Largest power of $q$ in polynomial for value Largest power of $q - 1$ in polynomial for value
Order of centralizer $q^{\sum_{i=1}^k \binom{r_i}{2}} \prod_{i=1}^k \prod_{j=0}^{r_i} (q^{r_i - j} - 1)$ $\sum_{i=1}^k r_i^2$ $\sum_{i=1}^k \binom{r_i}{2} = \frac{1}{2} \left(\sum_{i=1}^k r_i^2 \right) - \frac{n}{2}$ $n$
Size of conjugacy class (obtained as order of $GL(n,q)$ divided by order of centralizer) (complicated polynomial, but it is the $q$-analogue of the binomial coefficient and is written as $\binom{n}{r_1,r_2,\dots,r_k}_q$) $n^2 \ sum_{i=1}^k r_i^2$ $\frac{1}{2}\left(n^2 - \sum_{i=1}^k r_i^2 \right)$ 0
Number of such conjugacy classes $\binom{q - 1}{k} \binom{k}{s_1, s_2, \dots, s_n}$ $k$ 0 1

Some particular cases for the partition of $n$ as a sum of $r_i$s, and the corresponding sizes, are given below.

$n$ Partition of $n$ $k$ $|GL(n,q)|$ Order of centralizer of diagonal element Degree as polynomial of $q$ (equals $\sum_{i=1}^k r_i^2$) Size of conjugacy class Degree as polynomial of $q$ (equals $n^2 - \sum_{i=1}^k r_i^2$) Number of conjugacy classes (degree $k$ polynomial in $q$)
1 1 1 $q - 1$ $q - 1$ 1 1 0 $q - 1$
2 2 1 $q(q^2 - 1)(q - 1)$ $q(q^2 - 1)(q - 1)$ 4 1 0 $q - 1$
2 1 + 1 2 $q(q^2 - 1)(q - 1)$ $(q - 1)^2$ 2 $q(q + 1)$ 2 $\binom{q - 1}{2} = \frac{(q - 1)(q - 2)}{2}$
3 3 1 $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ 9 1 0 $q - 1$
3 2 + 1 2 $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ $q(q^2 - 1)(q - 1)^2$ 5 $q^2(q^2 + q + 1)$ 4 $2\binom{q-1}{2} = (q - 1)(q - 2)$
3 1 + 1 + 1 3 $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ $(q - 1)^3$ 3 $q^3(q^2 + q + 1)(q + 1)$ 6 $\binom{q-1}{3} = \frac{(q - 1)(q - 2)(q - 3)}{6}$
$n$ $n$ 1 $q^{\binom{n}{2}} \prod_{i=0}^{n-1} (q^{n - i} - 1)$ $q^{\binom{n}{2}} \prod_{i=0}^{n-1} (q^{n-i} - 1)$ $n^2$ 1 0 $q - 1$
$n$ $1 + 1 + \dots + 1$ $n$ $q^{\binom{n}{2}} \prod_{i=0}^{n-1} (q^{n - i} - 1)$ $(q - 1)^n$ $n$ $q^{\binom{n}{2}}\prod_{i=1}^{n-1} \left[\left(\sum_{j=0}^i q^j \right)\right]$ $n(n - 1)$ $\binom{q - 1}{n}$

### Regular semisimple elements not necessarily diagonalizable over the original field

Some elements may be semisimple but not diagonalizable over $\mathbb{F}_q$, i.e., they can be diagonalized over a suitable field extension of $\mathbb{F}_q$. We begin by considering the regular semisimple case -- elements that can be diagonalized over some field extension of $\mathbb{F}_q$ such that all their diagonal entries are pairwise distinct. We can show that these elements are precisely the ones that can be converted over $\mathbb{F}_q$ to a block diagonal form for some partition $r_1 + r_2 + \dots + r_k = n$, where the entry in block $r_i$ is diagonalizable with distinct diagonal entries over the field $\mathbb{F}_{q^{r_i}}$ and no smaller field.

In this case, the centralizer of the element in this block diagonal form is:

$\mathbb{F}_{q^{r_1}}^\ast \times \mathbb{F}_{q^{r_2}}^\ast \times \dots \times \mathbb{F}_{q^{r_k}}^\ast$

Item Value Degree as polynomial in $q$ Largest power of $q$ in polynomial for value Largest power of $q - 1$ in polynomial for value
Order of centralizer $\prod_{i=1}^k (q^{r_i} - 1)$ $n$ 0 $k$
Size of conjugacy class (obtained as order of $GL(n,q)$ divided by order of centralizer) (complicated polynomial) $n(n - 1)$ $\binom{n}{2}$ $n - k$
Number of such conjugacy classes $\prod_{j=1}^n \binom{M(q,j)- E(j)}{s_j}$ (where $M(q,j)$ is a necklace polynomial and $E$ is the characteristic function at 1; see explanation below) $n$ $\sum_{j=2}^n s_j \frac{j}{\operatorname{square-free part of } j}$ $k$

Thenecklace polynomial $M(q,j)$ is also the number of irreducible monic polynomials of degree $j$ over $\mathbb{F}_q$.

The formula for $M(q,j)$ is as follows:

$M(q, j) = \frac{1}{j} \sum_{d \mid j} \mu\left( \frac{j}{d} \right) q^d$

The definition of $E$ is as follows: $E$ is the function that takes the value 1 at 1 and 0 elsewhere.

The number of irreducible polynomials corresponding to entries in $\mathbb{F}_{q^j}^\ast$ is thus: $M(q,j) - E(j)$

In other words, it equals $M(q,j)$ when $j > 1$ and $M(q,1) - 1 = q - 1$ when $j = 1$.

The reason we need to subtract 1 in the special case $j = 1$ is in order to eliminate the case of the irreducible polynomial $x$, whose root is 0. For $j > 1$, the root of the irreducible polynomial must be nonzero and hence invertible, so there is no need to subtract 1.

Some particular values of necklace polynomials for a few cases of $j$ are below:

Value of $j$ $M(q,j)$ $M(q,j) - E(j)$
1 $q$ $q - 1$
a prime number $\frac{q^i - q}{i}$ $\frac{q^i - q}{i}$
a power of a prime $t$ $\frac{q^i - q^{i/t}}{i}$ $\frac{q^i - q^{i/t}}{i}$

Note that in the particular cases of the partition $1 +1 + \dots + 1$, this simplifies to $\binom{q - 1}{n}$; also this special case is the only case that overlaps with the previous section.

$n$ Partition of $n$ $|GL(n,q)|$ Order of centralizer of representative (degree $n$ polynomial in $q$) Size of conjugacy class (degree $n(n - 1)$ polynomial in $q$) Number of conjugacy classes (degree $n$ polynomial in $q$)
1 1 $q - 1$ $q - 1$ 1 $q - 1$
2 2 $q(q^2 - 1)(q - 1)$ $q^2 - 1$ $q(q - 1)$ $M(q, 2) = \frac{q^2 - q}{2} = \frac{q(q - 1)}{2}$
2 1 + 1 $q(q^2 - 1)(q - 1)$ $(q - 1)^2$ $q(q + 1)$ $\binom{M(q,1) - 1}{2} = \binom{q - 1}{2} = \frac{(q - 1)(q - 2)}{2}$
3 3 $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ $q^3 - 1$ $q^3(q - 1)^2(q + 1)$ $M(q, 3) = \frac{q^3 - q}{3} = \frac{q(q^2 - 1)}{3}$
3 2 + 1 $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ $(q^2 - 1)(q - 1)$ $q^3(q^3 - 1)$ $M(q, 2)(M(q,1) - 1) = \frac{q^2 - q}{2}(q - 1) = \frac{q(q - 1)^2}{2}$
3 1 + 1 + 1 $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ $(q - 1)^3$ $q^3(q^2 + q + 1)(q + 1)$ $\binom{M(q,1) - 1}{3} = \binom{q - 1}{3} = \frac{(q - 1)(q - 2)(q - 3)}{6}$
4 4 $q^6(q^4 - 1)(q^3 - 1)(q^2 - 1)(q - 1)$ $q^4 - 1$ $q^6(q^3 - 1)(q^2 - 1)(q - 1)$ $M(q,4) = \frac{q^4 - q^2}{4} = q^2(q^2 - 1)/4$
4 3 + 1 $q^6(q^4 - 1)(q^3 - 1)(q^2 - 1)(q - 1)$ $(q^3 - 1)(q - 1)$ $q^6(q^4 - 1)(q^2 - 1)$ $M(q,3)(M(q,1) - 1) = \frac{q^3 - q}{3}(q - 1) = \frac{q(q^2 - 1)(q - 1)}{3}$
4 2 + 2 $q^6(q^4 - 1)(q^3 - 1)(q^2 - 1)(q - 1)$ $(q^2 - 1)^2$ $q^6(q^3 - 1)(q^2 + 1)(q - 1)$ $\binom{M(q,2)}{2} = \frac{q(q - 1)(q + 1)(q - 2)}{8}$
4 2 + 1 + 1 $q^6(q^4 - 1)(q^3 - 1)(q^2 - 1)(q - 1)$ $(q^2 - 1)(q - 1)^2$ $q^6(q^4 - 1)(q^2 + q + 1)$ $M(q,2)\binom{M(q,1) - 1}{2} = \frac{q^2 - q}{2} \binom{q - 1}{2} = q(q - 1)^2(q - 2)/2$
4 1 + 1 + 1 + 1 $q^6(q^4 - 1)(q^3 - 1)(q^2 - 1)(q - 1)$ $(q - 1)^4$ $q^6(q^3 + q^2 + q + 1)(q^2 + q + 1)(q + 1)$ $\binom{M(q,1) - 1}{4} = \binom{q - 1}{4} = \frac{(q - 1)(q - 2)(q - 3)(q - 4)}{24}$

### General semisimple case

The general semisimple case combines ideas from both the preceding cases (the diagonalizable over $\mathbb{F}_q$ case, and the regular semisimple case), and generalizes both of them.

For a given conjugacy class in $GL(n,q)$, and for $i,j \in \{ 1, 2, \dots, n \}$ define $s_{i,j}$ to be the number of distinct cases where the conjugacy class contains exactly $j$ conjugate elements of $\mathbb{F}_{q^i}^\ast$ (i.e., a multiplicity of $j$ for an extension of degree $i$ over $\mathbb{F}_q$).

We have:

$\sum_{i, j} ijs_{i,j} = n$

The formula for the order of the centralizer:

$\prod_{i,j} \left |GL(j,q^i) \right|^{s_{i,j}}$

The size of the conjugacy class can be calculated by dividing $|GL(n,q)|$ by the order of the centralizer as given above.

The formula for the number of conjugacy classes can now be given in terms of necklace polynomials $M(q,i)$:

$\prod_{i=1}^n \binom{M(q,i)}{s_{i,1}, s_{i,2},\dots,s_{i,n}} = \prod_{i=1}^n \left( \binom{M(q,i)}{\sum_j s_{i,j}} \binom{\sum_j s_{i,j}}{s_{i,1}, \dots, s_{i,n}} \right)$

Here, we define the necklace polynomial $M(q,i)$ as follows:

$M(q,i) = \frac{1}{i} \sum_{d \mid i} \mu \left(\frac{i}{d} \right) q^d$

## Case of non-semisimple elements

### Regular elements with all eigenvalues over $\mathbb{F}_q$

We begin by considering a very easy class of non-semisimple elements: those where all the eigenvalues are over $\mathbb{F}_q$, and where all distinct Jordan blocks correspond to distinct eigenvalues, i.e., they are regular elements. This means that the minimal polynomial coincides with the characteristic polynomial.

Suppose the Jordan block sizes are $r_1, r_2, \dots, r_k$.

The centralizer for each Jordan block of size $r_i$ is the invertible matrices in the subalgebra generated by the Jordan block. This corresponds to the units in $\mathbb{F}_q[t]/(t^{r_i})$, and the size of this group is $q^{r_i - 1}(q - 1)$.

The order of the centralizer is therefore:

$\prod_{i=1}^k (q^{r_i - 1}(q - 1)) = q^{n - k}(q - 1)^k$

The size of the conjugacy class is obtained by dividing the order of the group by this expression.

For each partition:

$n = r_1 + r_2 + \dots + r_k$

The number of conjugacy classes associated with that partition can be calculated as follows. Suppose that, among the $r_j$s, there are $s_1$ 1s, $s_2$ 2s, and so on. Then, the total number of conjugacy classes is:

$\binom{q - 1}{k}\binom{k}{s_1, s_2, \dots, s_n}$

The total number of conjugacy classes corresponding to a choice of $k$ is therefore:

$\binom{q - 1}{k} \sum \binom{k}{s_1, s_2, \dots, s_n}$

where the sum is across all the possible partitions.

$n$ Partition of $n$ $k$ (number of parts) $|GL(n,q)|$ Order of centralizer of representative (equals $q^{n-k}(q - 1)^k$, a degree $n$ polynomial over $q$) Size of conjugacy class (degree $n(n - 1)$ polynomial over $q$) Number of conjugacy classes (degree $k$ polynomial over $q$)
1 1 1 $q - 1$ $q - 1$ 1 $q - 1$
2 2 1 $q(q^2 - 1)(q - 1)$ $q(q - 1)$ $q^2 - 1$ $q - 1$
2 1 + 1 2 $q(q^2 - 1)(q - 1)$ $(q - 1)^2$ $q(q + 1)$ $\binom{q - 1}{2} = \frac{(q - 1)(q - 2)}{2}$
3 3 1 $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ $q^2(q - 1)$ $q(q^3 - 1)(q^2 - 1)$ $q - 1$
3 2 + 1 2 $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ $q(q - 1)^2$ $q^2(q^3 - 1)(q + 1)$ $2 \binom{q - 1}{2} = (q - 1)(q - 2)$
3 1 + 1 + 1 3 $q^3(q^3 - 1)(q^2 - 1)(q - 1)$ $(q - 1)^3$ $q^3(q^2 + q + 1)(q + 1)$ $\binom{q - 1}{3} = \frac{(q - 1)(q - 2)(q - 3)}{6}$