Posted by: Steven Sam | September 14, 2009

GLFq I: Conjugacy classes of a finite general linear group

I’d like to start a series of posts, GLFq (general linear group over a finite field), in which I hope to explain the representation theory of $G = {\bf GL}_n({\bf F}_q)$ (n and q will remain fixed). In this first post, I’ll explain how to write down the conjugacy classes of G. In later posts, I plan to introduce Hall–Littlewood polynomials and the characteristic map. I would like to also go into how to construct the actual representations, and discuss things related to Hall–Littlewood polynomials, like the q-Kostka polynomials and a lot of the interesting algebra/geometry behind them.

There are two pieces of data we would like to know. First, what is the size of G? Second, how do we parameterize the conjugacy classes? The first question is easy to answer since an invertible matrix is given by the data of n linearly independent vectors. The first one can be chosen to be any nonzero vector, so there are $q^n - 1$ of them. In general, the ith one can be chosen to be any vector not in the span of the last i-1 (so we are just avoiding some i-1 dimensional subspace, which has $q^{i-1}$ elements), and hence there are $q^n - q^{i-1}$ choices for such a vector. All together, the number of elements of G is $\prod_{i=1}^n (q^n-q^{i-1})$. We can rewrite this as $q^{\binom{n}{2}} (q-1)^n [n]_q!$ to make it more analogous to the number of elements of the symmetric group.

The second question requires the rational canonical form. If we were dealing with an algebraically closed field, conjugacy classes would of course be parameterized by Jordan normal forms, so we need some kind of substitute for that. First, we need the structure theorem for finitely generated modules over a principal ideal domain R. This says that any such module is a direct sum of its torsion submodule and a free submodule. Furthermore, the torsion submodule is uniquely a direct sum of cyclic modules, which can be written in the form $R/(f^m)$ for some irreducible element f and some positive integer m.

Given a matrix A, we’ll apply this to the case $R = {\bf F}_q[t]$ and the module $V = {\bf F}_q^n$ where the action of a polynomial p(t) on V is given by p(A). Irreducible elements of R are the same as irreducible polynomials, but we will never see the polynomial x show up if A is invertible, and we will only need to use the monic ones. Let $\Phi$ be the set of all monic irreducible polynomials over ${\bf F}_q$ which are different from the constant polynomial x. Hence, we see that the data of the decomposition is given by a partition valued function $\boldsymbol{\mu}$ on $\Phi$. Explicitly, the function $\boldsymbol{\mu}$ gives the module $\bigoplus_{f \in \Phi} \bigoplus_{i \ge 0} R / (f^{\boldsymbol{\mu}(f)_i})$.

Since the dimension of $R / (f^m)$ is $\deg(f) \cdot m$, the conjugacy classes of G are given by those partition valued functions $\boldsymbol{\mu}$ such that $\| \boldsymbol{\mu} \| := \sum_{f \in \Phi} \sum_i \deg(f) \boldsymbol{\mu}(f)_i = n$.

As an aside, if we look at the conjugacy classes of all matrices instead of invertible matrices, i.e., we allow the domain of the partition valued functions above to include the polynomial x, then the number of such classes is $\sum_j p_j(n) q^j$ where $p_j(n)$ is the number of partitions of n into j parts. I think it’s a really nice formula (though it takes some work to show). See Chapter 1, Section 10 of the second edition of Enumerative Combinatorics I for a derivation of this formula.

Let’s look at the case of n=2. The only valid partition valued functions can only have nonempty values on polynomials of degree at most 2. There are 3 types of functions:

• There exists a single monic irreducible polynomial f of degree 1 such that $\mu = \boldsymbol{\mu}(f) \ne \emptyset$ and we have $\sum_i \mu_i = 2$, so $\mu \in \{(2), (1,1)\}$. These correspond to matrices with a single eigenvalue, the partition (1,1) means that it’s a diagonal matrix, and the partition (2) means that it is conjugate to a size 2 Jordan block.
• There exists two distinct monic irreducible polynomials f and g of degree 1 such that $\boldsymbol{\mu}$ takes the value (1) on both and is empty on all other polynomials. These correspond to matrices with two distinct eigenvalues.
• There exists a single monic irreducible polynomial f of degree 2 such that $\boldsymbol{\mu}(f) = (1)$ and all other values are the empty partition. These are matrices without a Jordan normal form.

The only irreducible polynomials of degree 1 which are allowed are of the form x-a for a nonzero value of a. So there are 2(q-1) functions of the first kind and $\binom{q-1}{2} = (q-1)(q-2)/2$ functions of the second kind. For the third kind, we have $q^2$ monic polynomials of degree 2 over ${\bf F}_q$. There are q polynomials of the form $(x-a)^2$ and $\binom{q}{2} = q(q-1)/2$ of the form $(x-a)(x-b)$ for a and b distinct, so we must have $q^2 - q - q(q-1)/2 = q(q-1)/2$ monic irreducible degree 2 polynomials over ${\bf F}_q$. Thus in total we have $2(q-1) + (q-1)(q-2)/2 + q(q-1)/2 = q^2 - 1$ conjugacy classes.