Given a small number of generators for a group of small (e.g. $3\times3$) matrices over a finite field $\mathbb{F}_p$ where $p$ is prime, how can we find all the elements of the group?

The best I've come up with so far is to keep taking all possible products of two elements of the group until we no longer get any new elements. This is fine when the groups are small, and it's the algorithm used here: . But some of the groups I'm considering have order over 10000 and therefore need over 100 million matrix multiplications and comparisons, which is taking Matlab far too long to compute!

Is there a way to know when we've got the whole group which is quicker than pairwise multiplication?

Many thanks for any help with this!


Short answer: Just use a program intended for this kind of thing, like GAP or magma.

Longer answer: If p ≤ 10, use Schreier–Sims on the underlying vector space, if p ≤ 100 use Schreier–Sims on a short orbit. If the dimension is larger or the prime is larger, use the composition tree approach.

If p is not too large, then you can view a matrix group as a permutation group on the $p^3$ vectors, and use the Schreier–Sims algorithm to compute a fast bijection between $\{1,2,\cdots, |G|\}$ and $G$ (so in particular, tells you how many groups elements you have, and gives you a constant time access list of the elements without wasting a bunch of memory storing the actual matrices). It also quickly answers the question if a given matrix is in your group, and can express it as a (long-ish) product of your original generators.

If p ≤ 10, this is approximately instantaneous. If p ≤ 100 it is usable. For larger p, this idea needs refinement, and sometimes is simply ill-suited.

If the dimension is larger, then there are techniques that use more structure of the vector spaces. “Composition tree methods” is the general name here, though they are still under development.

  • $\begingroup$ Thanks for this! I've looked up about the Schreier-Sims algorithm, but it seems a bit too complicated since the problem is quite simple. Using the fact that the generators are generators shortens my method down a lot: just multiplying each generator by each element got so far gives $O(|G|)^2$ matrix mults instead of $O(|G|^3$, which is enough to make the program run in a reasonable time! $\endgroup$ – Harry Macpherson Aug 29 '12 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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