GAP QA #8
Expressing an element as word in Generators
Keywords:
Word, Factorization
Respondent:
Alexander Hulpke (
hulpke@math.colostate.edu)
Question:
I have Co1 represented as a matrix group with dimension 24 over GF(2)
(using the standard generators a & b from the www-ATLAS) and several group
elements in matrix form. I would like to express these elements as words in
the generators. I have tried constucting a free group of rank 2 and creating
an appropriate homomorphism using "GroupHomomorphismByImages" but this
exhausts the workspace I am using. Any ideas about other ways of proceeding?
Answer:
Essentially decomposition works via a permutation representation. The
default for obtaining a permutation representation for a matrix group is by
action on some vectors. Thus there is no reason for this to be the
representation of smallest degree. This is likely the problem you ran into.
Therefore the first attempt would be to construct (find suitable vectors,
say eigenvectors of random elements) an action homomorphism that will
translate your matrix group to a permutation group of degree ~98000
(which happens to be the smallest deg. perm rep for Co1).
In this representation I checked that GAP (using about 250MB of memory) is
able to decompose into generators; however the resulting words I got were of
Length several 100000, which might not have been, what you had in mind. You
can reduce the length a bit by adding further generators that are known
short words, but this will not help that much, you will have trouble getting
below Length a few 1000.
A much better approach for such a group about which you know a lot is to
construct the word ``bespoke'' by hand:
- Determine (trace, Order etc.) the class of this element x.
- Use the ATLAS webpages from Birmingham to find a word for a representative
r of this class
- Now start computing conjugates of r and x by random short words. If you
find a,b s.t. r^a=x^b you found a conjugating element which will give you
a word.
- If you have a small subgroup generated by short words, you can look at
conjugation orbits under this subgroup instead to reduce the search space.
There are various refinements to this technique. The papers of Robert Wilson
on Standard generators (e.g.
- 1.
Wilson, Robert A.(4-BIRM-SM)
Standard generators for sporadic simple groups.
J. Algebra 184 (1996), no. 2, 505--515.
- 2.
Suleiman, Ibrahim A. I.(JOR-MUT-MS); Wilson, Robert A.(4-BIRM-SM)
Standard generators for $J\sb 3$. (English. English summary)
Experiment. Math. 4 (1995), no. 1, 11--18.
describe some such methods.
Back
to the GAP QA list