# Transposition decomposition of permutations?

Does there exist a reference table or software that gives the transposition decomposition of permutations in $S_n$ (for relatively small $n$ I suppose).

-

The decomposition of a permutation into a product of transpositions is not unique. I doubt you'll find a table anywhere because the procedure for writing such a decomposition down is very easy.

For example: If $\sigma = (143)(27689)$ then $\sigma=(13)(14)(29)(28)(26)(27)$

In general, each cycle in a permutation can be written as a product of transpositions as follows: $(a_1a_2\dots a_n) = (a_1a_n)(a_1a_{n-1})\cdots (a_1a_3)(a_1a_2)$.

But keep in mind this is just one (of many) ways to write a permutation as a product of transpositions.

Suppose $a<b$. If $b=a+1$, then we're done otherwise notice that $(ab)=(a+1,b)(a,a+1)(a+1,b)$. Now either $a+2=b$ or replace each $(a+1,b)$ with $(a+2,b)(a+1,a+2)(a+2,b)$. etc. Eventually you'll have rewritten $(ab)$ as a product of adjacent transpositions.

Since we can write any permutation as a product of transpositions and we can rewrite any transposition as a product of adjacent transpositions, we can write any permutation as a product of adjacent permutations.

So there's an "algorithm" but it ain't pretty. By the way, I make no claim this is the best way to go about this.

Example: $(123)(47) = (13)(12)(47) = (23)(13)(23)(12)(57)(45)(57)$ $=(23)(13)(23)(12)(67)(56)(67)(45)(67)(56)(67)$

-
That is quite easy, thanks. By the way, is there a general approach for writing a permutation in terms of adjacent transpositions? –  36maf Feb 8 '12 at 21:08
@36maf: $(i,j) = (i,i+1)(i+1,i+2)\cdots(j-2,j-1)(j-1,j)(j-1,j-2)\cdots(i,i+1)$. Just note that $(a,c)(a,b)(a,c)=(c,b)$. (Intuitively: if you want to exchange the first and 10th volume of an encyclopedia, and you can only exchange two adjacent ones at a time, shuffly the first one up to the last position, then shuffle the last volume back down to the first position). –  Arturo Magidin Feb 8 '12 at 21:20
Thanks both, I appreciate it. –  36maf Feb 8 '12 at 21:25
I edited my response to take care of that case. The idea comes from "conjugating" permutations -- if $\sigma$ is a permutation, then $\sigma (ab) \sigma^{-1} = (\sigma(a),\sigma(b))$. Thus $(ac)(ab)(ac)^{-1} = (ac)(ab)(ac) = (cb)$ –  Bill Cook Feb 8 '12 at 21:28
Thanks @ArturoMagidin as usual your approach is a bit cleaner and clearer. :) –  Bill Cook Feb 8 '12 at 21:29

Any comparison based sorting algorithm does this. It gives you the transpositions needed to 'sort' a sequence - if you save those that's your decomposition into transpositions.

-

In a canonical sense, a permutation can be represented as a unique product of transpostions. Inductively, we choose on transposition introduced from each S_n. This is similar to Durstenfeld's method for generating a random permutation.

For example, in S_4, we have

e 12 13 23 12 13 12 23

14 12 14 13 14 23 14 12 13 14 12 23 14

24 12 24 13 24 23 24 12 13 24 12 23 24

34 12 34 13 34 23 34 12 13 34 12 23 34

-
Theseparatation did not come out as intended in the above. Here is a re-try, separated by commas: e, 12, 13, 23, 12 13, 12 23 14, 12 14, 13 14, 23 14, 12 13 14, 12 23 14 24, 12 24, 13 24, 23 24, 12 13 24, 12 23 24 34, 12 34, 13 34, 23 34, 12 13 34, 12 23 34 –  Nick Hann Jan 28 '13 at 21:31
OK, a third try, four groups of 6 transpositions each, extending S_3 to S_4. (e, 12, 13, 23, 12 13, 12 23) (14, 12 14, 13 14, 23 14, 12 13 14, 12 23 14) (24, 12 24, 13 24, 23 24, 12 13 24, 12 23 24) (34, 12 34, 13 34, 23 34, 12 13 34, 12 23 34) –  Nick Hann Jan 29 '13 at 13:53