Permutation into chained transpositions?

Question

I know that every permutation can be factored as a product of transpositions.

I wonder if every permutation can be factored as product of chained transpositions ?

For example

[5,1,3,0,4,2] = [(3,2),(2,5),(5,0)]
                    \__/  \__/

And, if so, starting with an arbitrary element ?

score 0 · Accepted Answer · answered Oct 08 '19 at 08:23

0

Hint: The product of chained transpositions is always a cycle.

answered Oct 08 '19 at 08:23

5xum

Ok. I guess the answer is no, since not all permutations are cycles. – Poor Standard Oct 08 '19 at 08:28
@PoorStandard Exactly. – 5xum Oct 08 '19 at 08:45

1 Answers1