Does there exist a reference table or software that gives the transposition decomposition of permutations in $S_n$ (for relatively small $n$ I suppose).
Transposition decomposition of permutations?
3 Answers
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)$
-
0That is quite easy, thanks. By the way, is there a general approach for writing a permutation in terms of adjacent transpositions? – 2012-02-08
-
3@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). – 2012-02-08
-
0Thanks both, I appreciate it. – 2012-02-08
-
0I 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)$ – 2012-02-08
-
0Thanks @ArturoMagidin as usual your approach is a bit cleaner and clearer. :) – 2012-02-08
-
0@BillCook: Perhaps the parenthetical comment, but the rest is exactly the same as yours (-: – 2012-02-08
-
0If you start with cycle $(a,b,c)$ and you are using adjacent transpositions, you write $(a,c)(a,b)(a,c)$. Does the middle $(a,b)$ mean you're swapping the $a$ and the $b$ from the positions they're currently in, or does it mean you're swapping the element is currently in the position where $a$ started with the element currently in $b$'s position (nevermind that $b$ hasn't moved in this example). – 2012-04-02
-
1@Jeff I think you're viewing permutations in terms of scrambling lists. That's the wrong viewpoint for permutation groups (and cycle decompositions). Instead view cycles as functions. So $(ac)(ab)(ac)$ is the composition of three functions, say $f=(ac)$ and $g=(ab)$. For example: The function $f$ sends $a$ to $c$ and $c$ to $a$ and leaves everything else fixed. Thus $fgf(a)=f(g(f(a))=f(g(c))=f(c)=a$ since $f$ swaps $a$ and $c$ and $g$ leaves $c$ fixed. Likewise, $fgf(b)=f(g(f(b)))=f(g(b))=f(a)=c$ and $fgf(c)=f(g(f(c)))=f(g(a))=f(b)=b$. Thus $fgf$ swaps $b$ and $c$ so $(ac)(ab)(ac)=(bc)$ – 2012-04-02
-
0OK, but you are defining two functions which have two inputs, $f=(ac), g=(ab)$, and then using them with only one input, e.g., $f(g(f(a))$. Does the definition of $g$ mean it swaps position $a$ with position $b$, no matter what input it gets? – 2012-04-03
-
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
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.
-
0It's not clear to me what you mean by "To see this slide on line over to the other allowing the dots to follow along their segments." Do you mean something like braiding and unbraiding? – 2018-07-29
-
0i 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
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
-
0Theseparatation 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 – 2013-01-28
-
0OK, 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