#### GAP QA #8

# Expressing an element as word in Generators

**Keywords:**
Word, Factorization
## Respondent:

Alexander Hulpke (
hulpke@math.colostate.edu)
## Question:

I have Co_{1} 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 Co_{1}).

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