This question already has an answer here:

I'm trying to understand why the product of transpositions for a specific permutation is not unique. Intuitively, it somewhat makes sense to me since I can get the answer but I don't actually know why it works.

The example I am particularly confused over is: say I have a permutation which in cycle notation is of the form:


Then I have been given two examples of transpositions that work:

1) (1,4)(1,3)(1,2)

2) (2,3)(1,3)(3,5)(3,4)(4,5)

Is it like you treat each transposition as a bijection that belongs to (in this case) S5 (or for any N>5) and so you consider the product of transpositions as a composition of all these bijections - which is why you start from the right and work your way backwards bracket by bracket and you stop once that number doesn't appear anymore? Is this also the case for a product of permutations?



marked as duplicate by Namaste abstract-algebra May 22 '18 at 17:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ Yes, this is usually the case. $\endgroup$ – Bernard May 5 '18 at 14:35
  • $\begingroup$ It's helpful to note that while the transposition decomposition is not unique, the number of transpositions is. $\endgroup$ – Bill Wallis May 5 '18 at 15:01
  • 1
    $\begingroup$ @BillWallis: you mean the parity of the number of transpositions. $\endgroup$ – Rob Arthan May 5 '18 at 15:08
  • $\begingroup$ Yes, I did! That was a silly blunder. $\endgroup$ – Bill Wallis May 5 '18 at 15:09

Your sketch of the method is right and it works for a product of cycles not just a product of transpositions. E.g., to check or derive:

$$ (1\,2\,3)(1\,3\,4) = (2\,3\,4) $$

you would work on the left-hand side from right to left, and say to yourself something like:

"$1$ goes to $3$ and then back to $1$. $2$ is unchanged and then goes to $3$. $3$ goes to $4$ and then is unchanged. $4$ goes to $1$ and then goes to $2$. Put together that gives $(2\,3\,4)$."

Now you can check that there are many ways of writing a single transposition as a product of transpositions. E.g., $$ (3\,5)(3\,4)(4\,5) = (3\,4) $$ So looking at your example 2, that gives yet another representation of $(1\,2\,3\,4)$: $$ (1\,2\,3\,4) = (2\,3)(1\,3)(3\,5)(3\,4)(4\,5) = (2\,3)(1\,3)(3\,4) $$ Also, note that: $$ (1\,2\,3\,4) = (2\,3\,4\,1) = (3\,4\,1\,2) = (4\,1\,2\,3) $$ So if you take any expression for $(1\,2\,3\,4)$ as a product of transpositions (or any other kind of permutation) and then cyclically permute the appearances of $1, 2, 3$ and $4$ in that product, you will get a different representation of $(1\,2\,3\,4)$.

The above shows just two of many ways of deriving different representations of a given permutation as a product of transpositions.


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