Ask Your Question

# Revision history [back]

### How do I identify the set of words of given length in matrix generators

I should mention that I am a beginner with Sage so please bear with me. Also this question regards a small sub-step of what this question is about: http://ask.sagemath.org/question/32935/how-to-efficiently-test-whether-a-matrix-can-be-written-as-a-certain-type-of-word/ But I expect the current issue would be much more common.

Take a small set of matrices, let's say 3 of them: m1, m2, m3. Let G be the group generated by these matrices. I want to be able to work with words of a given length in these generators. Let Gn be the words of length n in G. Then for example

G1 = (m1,m2,m3,m1^(-1),m2^(-1),m3^(-1)).


Is there a pre-built module for working with words of length n for n arbitrary? If not, I'm sure someone can find improvements on the approach I am taking. For instance to get G2, I have been doing this:

G2 = []
for g in G1:
for h in G1:
if g*h not in G2:
G2.append(g*h)
if h*g not in G2:
G2.append(h*g)
G2


This gives me everything in G2, and avoids repitition, but does not extend well to Gn.

To get G3 I have been doing this:

G3 = []
for g in G2:
for h in G1:
if g*h not in G2:
if g*h not in G1:
G2.append(g*h)
if h*g not in G2:
if h*g not in G1:
G2.append(h*g)


If I want to go to G4 in this way, I need to add a line that makes sure my new addition isn't in G3, and I need to keep adding new lines at each increase in word length. I would like to define a function which outputs all words of length n, but as you can imagine from my approach above that is not working out well.

### How do I identify the set of words of given length in matrix generators

I should mention that I am a beginner with Sage so please bear with me. Also this question regards a small sub-step of what this question is about: http://ask.sagemath.org/question/32935/how-to-efficiently-test-whether-a-matrix-can-be-written-as-a-certain-type-of-word/ But I expect the current issue would be much more common.

Take a small set of matrices, let's say 3 of them: m1, m2, m3. Let G be the group generated by these matrices. I want to be able to work with words of a given length in these generators. Let Gn be the words of length n in G. Then for example

G1 = (m1,m2,m3,m1^(-1),m2^(-1),m3^(-1)).


Is there a pre-built module for working with words of length n for n arbitrary? If not, I'm sure someone can find improvements on the approach I am taking. For instance to get G2, I have been doing this:

G2 = []
for g in G1:
for h in G1:
if g*h not in G2:
G2.append(g*h)
if h*g not in G2:
G2.append(h*g)
G2


This gives me everything in G2, and avoids repitition, but does not extend well to Gn.

To get G3 I have been doing this:

G3 = []
for g in G2:
for h in G1:
if g*h not in G2:
if g*h not in G1:
G2.append(g*h)
if h*g not in G2:
if h*g not in G1:
G2.append(h*g)


If I want to go to G4 in this way, I need to add a line that makes sure my new addition isn't in G3, and I need to keep adding new lines at each increase in word length. I would like to define a function which outputs all words of length n, but as you can imagine from my approach above that is not working out well.