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

asked 2016-04-02 01:30:25 +0200

j0equ1nn
69 ●2 ●8 ●14

updated 2016-04-02 01:31:00 +0200

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/3293... 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)

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.

edit retag flag offensive close merge delete

Comments

Like that ?

sage: Words(['a','b'],5).list()

FrédéricC ( 2016-04-02 12:00:49 +0200 )edit

@FredéricC I did not know of that command for generating words, but there is a big difference between words in the free group <a,b> and reduced words in a matrix group. I'm interested in reducing run-time by avoiding repetition of equivalent words, and also being able to efficiently search through the words generated.

j0equ1nn ( 2016-04-04 01:30:44 +0200 )edit

add a comment

answered 2016-04-02 16:49:17 +0200

nbruin
4143 ●3 ●45 ●90

You can of course first generate the words, but if the group generated by your generators is far from free on those generators, you will be generating a lot of extraneous entries. In addition M in <List> is much slower than M in <Set>, and sets would take care of repetitions automatically.

Matrices and sets are a little inconvenient together, because matrices are by default "mutable" and it's a bad idea to put mutable objects in a set (if an element were to mutate into one that is equal to another one, it would need to be taken out!), but with a little helper function we can fix that.

def immutable(a):
  a.set_immutable()
  return a

m1=immutable(matrix(ZZ,2,2,[1,1,0,1]))
m2=immutable(matrix(ZZ,2,2,[0,1,-1,0]))
V={m1,m2,immutable(m1^(-1)),immutable(m2^(-1))}

G=[V]
for i in [1..5]:
    G.append( {immutable(m*g) for m in G[0] for g in G[-1]})

Note that for every i, a new Gi is computed. Furthermore, in python, negative indices mean from the end, so G[-1] is the last element in the list G, i.e., the last computed list G[i-1]. List indexing in python is 0-based, so G[0] is the first entry, i.e., V.

edit flag offensive delete link

Comments

This is great! I had improved my code a little from what I posted, but still a run-time long enough to go grocery shopping before getting the data. This approach by contract even runs in Sage cell online in a few seconds.

j0equ1nn ( 2016-04-03 06:07:44 +0200 )edit

Something strange about this though. We are not creating a set, but a list of sets, right? Because of this there is in fact a lot of repetition. For instance, every time a matrix can be written as a non-reduced word of length L in the generators, it will be included in the (L-1)th set in the list. Is there an easy modification that will put all these sets together, perhaps improving run-time further?

j0equ1nn ( 2016-04-03 07:02:48 +0200 )edit

Do you mean that you only want to keep track of the union of the G[i] ? Something like

R=set(V)
W=V
for i in [1..5]:
    W= {immutable(w*v) for w in W for v in V}
    R.update(W)

This might slightly reduce runtime, because memory use is a little lower, but we're still doing the same multiplication work.

I see one possible improvement: if you've just obtained an element by multiplying with v, you shouldn't multiply if with v^(-1) the next time around. That would at most bring you an improvement factor of (#V - 1)/(#V) and you'd have more overhead in administration, so I'm not sure it's worth it.

nbruin ( 2016-04-03 18:02:34 +0200 )edit

I want to be able to search for words satisfying certain properties, up to some chosen length. I can do that in the previous version, but I must search through each item in the list of sets G and I get a lot of repetition. It would be okay to have G be a list of sets by reduced word length (meaning if something simplifies to a shorter word, it doesn't get included in a new set). It would also be okay to have G just be a set of all words up to the given length. With the new version you've given I get the error "local variable 'W' referenced before assignment," which makes no sense to me since W=V, and V is the set of generators and their inverses.

j0equ1nn ( 2016-04-04 00:35:01 +0200 )edit

One solution I have is just, use your original answer, then in my function that searches through G I can tell it to make the collected output into a set before returning it. This will not reduce run-time, but does save me the trouble of looking through the output for distinct elements. BTW I really appreciate your help with this! There are many things that just take me forever being inexperienced and you've already saved me a lot of time.

j0equ1nn ( 2016-04-04 01:14:03 +0200 )edit

see more comments

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

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

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

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

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