# Writing a given permutaion as a product of generators

Anonymous

Suppose that I have a group generated by three elements (written in cycle notation). I know that Sage will find all of the elements of this group.

What I need is to be able to write a given permutation as a product of these generators.

Any ideas?

For refernce, I am working in S_16. My generators are a=(13,14,15,16), b=(1,2,3,4)(5,6,7,8)(9,10,11,12), and c=(1,5,9,13,12,8,4). I want to "factor" (1,2) and (1,5) as a product of a,b,c.

edit retag close merge delete

Sort by ยป oldest newest most voted

What you are asking for is known as the word problem.

In your case, you can do (the answer is quite a huge product):

sage: P = PermutationGroup([[(13,14,15,16)], [(1,2,3,4),(5,6,7,8),(9,10,11,12)], [(1,5,9,13,12,8,4)]])
sage: P.gens()
[(13,14,15,16), (1,2,3,4)(5,6,7,8)(9,10,11,12), (1,5,9,13,12,8,4)]
sage: p = P((1,2))
sage: ans = p.word_problem(P.gens(), display=False)
sage: ans[0]
'x3*x2^-1*x3*x2^2*x3^-1*x2^-1*x3^-1*x2^-1*x3^-1*x2^-2*x3*x2^-1*x3^-2*x2^-1*x3^\n-1*x2^-2*x3*x2^-2*x3*x2^-2*x3^-1*x2^-1*x3*x2^-1*x3^-1*x2^-2*x3*x2^-2*x3*x2^\n-2*x3^-1*x2^-1*x3*x2*x1*x3*x1^-1*x3^-1*x1^-1*x3*x1*x3^-1*x1^2*x3*x1^-3*x3^\n-1*x1^-1*x2^-1*x1^-1*x3*x2^-1*x3*x2^2*x3^-1*x2^-1*x3^-1*x2^-1*x3^-1*x2^\n-2*x3*x2^-1*x3^-2*x2^-1*x3^-1*x2^-2*x3*x2^-2*x3*x2^-2*x3^-1*x2^-1*x3*x2^-1*x3^\n-1*x2^-2*x3*x2^-2*x3*x2^-2*x3^-1*x2^-2*x3^-1*x2*x3*x2^-1*x3*x2'
sage: ans[1]
'(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^2*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^-2*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^\n-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^\n-2*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)*(13,14,15,16)*(1,5,9,13,12,8,4)*(13,14,15,16)^-1*(1,5,9,13,12,8,4)^-1*(13,14,15,16)^-1*(1,5,9,13,12,8,4)*(13,14,15,16)*(1,5,9,13,12,8,4)^-1*(13,14,15,16)^2*(1,5,9,13,12,8,4)*(13,14,15,16)^-3*(1,5,9,13,12,8,4)^\n-1*(13,14,15,16)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(13,14,15,16)^-1*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^2*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^\n-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^-2*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)^\n-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-2*(1,5,9,13,12,8,4)^-1*(1,2,3,4)(5,6,7,8)(9,10,11,12)*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)^-1*(1,5,9,13,12,8,4)*(1,2,3,4)(5,6,7,8)(9,10,11,12)'

more