Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

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.

Edit: For adjacent 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)$

share|improve this answer
    
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
2  
@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
show 5 more comments

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.