Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Okay, I'm not sure if the title is correct but is there any general way of finding the number of distinct elements that are generated by some function (for example $*$) and a permutation (in this case the permutation group that shifts all number to the right, $p$) and an $n$-tuple (in this case a 4-tuple for example $(1,0,-1,0)$ ). So we have all combinations of $p(1,0,-1,0)*p(1,0,-1,0)$ so that:

$$ p_0(1,0,-1,0)*p_1(1,0,-1,0) = (1,0,-1,0)*(0,1,0,-1) = (0,0,0,0) $$

where p_n denotes n shifts of the tuple to the right.

Is there anyway of enumerating the combination such that the result of the multiplications, here $(0,0,0,0)$, are all distinct.

share|improve this question
    
By shift, you mean cyclic shift right? For example, $p_1(1,2,3,4) = (4,1,2,3)$. –  Jack Schmidt Jul 30 '12 at 16:48
    
Yeah, that's correct. –  user1170304 Jul 30 '12 at 20:26
add comment

1 Answer 1

up vote 3 down vote accepted

This answers names a few things and shows you a program that makes it easy to work with things like this.

Names

If you have a single permutation p and a single vector v and a single function f, then the values you are looking for are called the image under f of the orbit of v under the action of the permutation group generated by p.

In your particular case, the standard algorithm is going to be very natural but not very impressive. Find all the possible rotated n-tuples, and then multiply them. :-)

In general, you can have more complicated permutations and then the standard algorithm is much more impressive, and will find you the distinct n-tuples quickly and tell you how it got them using Schreier vectors.

I'll explain them in reverse order: the permutation group G generated by a permutation p includes not only $p=p_1$, but also $p\cdot p = p_2$, and $p \cdot p \cdot p = p_3$. This might seem like a very large thing, but in your example it doesn't take long to finish: $p_4$ of a 4-tuple actually just leaves everything alone. $p_5 = p_1$ effectively shifts things to the right by 1, rather than worrying about shifting 5 times. If you have more than one permutation p, then you need to allow applying any of the permutations over and over.

The orbit of v under the action of G is just everything that can happen to v. You apply every element of G to v once, and you get all the possible v. Alternatively you apply your (short) list of important permutations to v and keep track of the different answers in a simple way.

The image of the orbit under f is pretty simple: you take the tuples and you apply f to them. In your case, you just take pairs of n-tuples and multiply them.

If f has any relationship to G, then this last step can be improved. However, in your case there is no real relationship, and so one might as well do the naive thing.

Easy program

Should you want to do this in GAP you would use:

gap> p := (1,2,3,4);;
gap> G := Group( p );;
gap> v := [1,0,-1,0];;
gap> orbit := Orbit( G, v, Permuted );;
gap> f := function( x, y ) return List( [1..Size(x)], i -> x[i] * y[i] ); end;;
gap> values := Set( Tuples( orbit, 2 ), xy -> f( xy[1], xy[2] ) );
[ [ -1, 0, -1, 0 ], [ 0, -1, 0, -1 ], [ 0, 0, 0, 0 ], [ 0, 1, 0, 1 ], [ 1, 0, 1, 0 ] ]

If you allowed swapping q the first two elements in the vector too, then you'd do:

gap> p := (1,2,3,4);;
gap> q := (1,2);;
gap> G := Group( p, q );;
gap> v := [1,0,-1,0];;
gap> orbit := Orbit( G, v, Permuted );;
gap> f := function( x, y ) return List( [1..Size(x)], i -> x[i] * y[i] ); end;;
gap> values := Set( Tuples( orbit, 2 ), xy -> f( xy[1], xy[2] ) );;
gap> PrintArray(values);
[ [  -1,  -1,   0,   0 ],
  [  -1,   0,  -1,   0 ],
  [  -1,   0,   0,  -1 ],
  [  -1,   0,   0,   0 ],
  [   0,  -1,  -1,   0 ],
  [   0,  -1,   0,  -1 ],
  [   0,  -1,   0,   0 ],
  [   0,   0,  -1,  -1 ],
  [   0,   0,  -1,   0 ],
  [   0,   0,   0,  -1 ],
  [   0,   0,   0,   0 ],
  [   0,   0,   0,   1 ],
  [   0,   0,   1,   0 ],
  [   0,   0,   1,   1 ],
  [   0,   1,   0,   0 ],
  [   0,   1,   0,   1 ],
  [   0,   1,   1,   0 ],
  [   1,   0,   0,   0 ],
  [   1,   0,   0,   1 ],
  [   1,   0,   1,   0 ],
  [   1,   1,   0,   0 ] ]
share|improve this answer
    
Thanks, I had never heard of GAP and I get the feeling it will be very useful. –  user1170304 Jul 31 '12 at 9:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.