Decomposing a permutation into multiplication of transpositions [duplicate]

This question already has an answer here:

Logic for decomposing permutation into transpositions

2 answers

I have a permutation in cyclic notation, for example (132)(132), and i want to represent it as multiplication of transpositions.

What is the fastest way to do it?



1 Answer


First, it matters what (132)(132) means (i.e. whether it means 1→3→2→11\to3\to2\to1 or 2→3→1→22\to3\to1\to2). If it means the former (which is the convention I use),
then (132)=(13)(32)=(13)(23)(132)=(13)(32)=(13)(23). In general, you can write (a1,a2,…,an)=(a1a2)(a2a3)⋯(an−1an).(a_1,a_2,\ldots,a_n)=(a_1a_2)(a_2a_3)\cdots(a_{n-1}a_n).