# program to find matrix group given generators (Matlab)?

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!

-

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.
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! –  Harry Macpherson Aug 29 '12 at 21:29