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

A chemist showed this way to factor a permutation into transpositions. Draw n dots on each of two parallel lines in the plane. Connect the dots on one line with those on the other line by straight segments according to the given permutation. There will be one transposition for each intersection point of two segments. To see this slide one line over to the other allowing the dots to follow along their segments. The order of the dots is changed by a transposition when an intersection point is crossed. This provides a fast mechanical way to compute the sign of a permutation , which was the motivation from theoretical chemistry.

-