3
$\begingroup$

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

3 Answers 3

9

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. 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)$

  • 0
    @Jeff $f=(ac)$ is$a$*family* of functions of *one* input. More concretely, say, $f=(12) \in S_3$ ($S_3$ is the group of permutations on $\{1,2,3\}$) is the function: $f(1)=2$, $f(2)=1$, and $f(3)=3$. If you view permutations purely in terms of the outputs of these functions, then $f=(12)$ corresponds to $2\;1\;3$ (the first and second position have been swapped). However, if you insist upon viewing permutations this way, when you start composing permutations (think *function* not *list of numbers*) you're going to get really really confused.2012-04-03
1

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.

  • 0
    i meant parallel translate one line containing dots to the other line containing dots and watch what happens to the moving dots each time they cross one gets a transposition.[ technically i am supposing only one crossing occurs at one level]2018-07-31
0

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

  • 0
    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)2013-01-29