Efficiently Computing Conjugacy Classes in GL(n,Fp)

[simba31415]

Homework Statement

As the title says, I'm trying to find an efficient algorithm in order to write a program for computing conjugacy classes in subgroups of the general linear group $GL(n,\mathbb{F}_p)$ (n x n matrices over a finite field of p elements, p prime) efficiently. In particular, I am looking at conjugacy classes of subgroups of $GL(n,\mathbb{F}_p)$ generated by a small number of elements (say 2 or 3 generating matrices, though I'd like to be able to theoretically do it for arbitrarily many).

Is there an especially nice/clever/efficient way to compute the conjugacy classes? Whilst I am writing a program for this (so I can't really take a method which is ad hoc for lots of different situations), I believe the maths and not the programming is where the difficulty lies; I want a good reasonably fast algorithm which guarantees me all the elements in the subgroup generated by a small number of matrices, and also either then sorts them into conjugacy classes or (certainly preferable:) actually generates all the elements of the subgroup in their conjugacy classes, eliminating the need to sort them afterwards (which I'm not sure how I'd go about doing anyway). I can easily calculate the order of the generating matrices if that's any use, though since we can combine even just 2 matrices in many different ways I'm not sure it will be. At any rate, I'll either need to be able to figure out the total order of the subgroup of $GL(n,\mathbb{F}_p)$, so I can tell when I'm done calculating the conjugacy classes, or perhaps more preferably the process will automatically stop generating the cclasses when done and I can just add up their sizes to get the size of the subgroup - but how do even I approach this this? Say the group $H \subset GL(n,\mathbb{F}_p)$ is generated by $M_1,\,...,\,M_t$, how do we determine the conjugacy classes in a way which works for any given n, p and generating matrices? Could anyone suggest anything?

I'm happy with mathematical ideas of any complexity so don't hold back, though I would prefer the programming to be relatively simple, as I'm not going to rely on lots of prewritten programs to figure things out for me! Thanks very much in advance. -Simba

 

[lippyka]

Homework Equations N/AThe Attempt at a Solution My attempt so far has been to use the fact that the conjugacy classes of subgroups H \subset GL(n,\mathbb{F}_p) are in bijection with the cosets of the normalizer N_G(H) in GL(n,\mathbb{F}_p), where G is the general linear group. I then thought that I could calculate the normalizer (which I can do in polynomial time using the orbit-stabilizer theorem) and then use the coset decomposition to get the conjugacy classes, but this doesn't really help me because the normalizer is usually much larger than the subgroup itself and so the number of cosets is much larger than the number of conjugacy classes I actually want. Is there a way to get around this bottleneck? Note that any algorithm should work for arbitrary n and p, as this is a problem in computational group theory.