4
$\begingroup$

Consider the permutation $(2,6,3,4,5) \in S_6$. Then it's transposition form would be $(2,5), (2,4), (2,3), (2,6)$. But I don't understand how to show that $(2,6,3,4,5) \in S_6$ can be written as a product of simple transpositions. I know a transposition, $\sigma \in S_n$, is simple if it is of the form $\sigma = (i, i+1)$ for some $i \in \left \{ 1,2,...,n-1 \right \}$. I've looked at other examples, but I still don't think I understand. Below is what I've tried, but I really don't think this is right. How am I suppose to do this?

Given $(2,6,3,4,5) \in S_6$ which can be written as $(2,5), (2,4), (2,3), (2,6)$. Then

$(2,5) = (4,5), (3,4), (2,3), (3,4), (4,5)$

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

$(2,6) = (5,6),(4,5), (3,4), (2,3), (4,5), (5,6)$

Therefore, $(2,6,3,4,5) \in S_6= (4,5), (3,4), (2,3), (3,4), (4,5)(3,4), (2,3), (3,4)(2,3)(5,6),(4,5), (3,4), (2,3), (4,5), (5,6)$

$\endgroup$
  • $\begingroup$ @BillWallis Maybe you already know that, but the tag you have recently created has been discussed on meta: Should the (permutation-cycles) tag be deleted? and Tag management 2018. After you see this comment, feel free to ping me in tagging chatroom, so that I know it can be deleted. $\endgroup$ – Martin Sleziak Jul 23 '18 at 11:10
  • $\begingroup$ @MartinSleziak I did not know about the discussion. In fact, I was unaware that there was a tag management question at all --- had I known about it, I would've proposed the discussion myself (thank you for making me aware). I don't use the chatrooms so I'm not sure how to ping you on there, but before it gets deleted I would like to put forward my case for keeping the tag first on the tag management question. $\endgroup$ – Bill Wallis Jul 23 '18 at 12:51
1
$\begingroup$

You're Right!

What you have done is absolutely correct (minus a small error), so it seems you have a rough idea of how this works. I will elaborate a bit.

Notation

For clarification, it seems that you are multipliying right-to-left so you are treating the permutations as bijective maps, and their product is the composition of maps. My personal preference is to avoid using commas in the permutations, so what you would write as $$ (2, 3), (3, 4) $$ myself and some others would write as $$ (2\quad 3)(3\quad 4). $$ I will write my answer in this notation, but note that this has no bearing on the validity of your solution and is just a preference.

A Handy Rule

Let $\sigma$ and $\gamma$ be permutations in $S_{n}$, and suppose that $\sigma$ consists of a single cycle so that $\sigma = (s_{1}\quad s_{2}\quad\ldots\quad s_{k})$ for $s_{1}, \ldots, s_{k} \in \{1, 2, \ldots, n\}$. A handy rule to remember is $$ \gamma\sigma\gamma^{-1} = \gamma(s_{1}\quad s_{2}\quad\ldots\quad s_{k})\gamma^{-1} = \big(\gamma(s_{1})\quad \gamma(s_{2})\quad\ldots\quad \gamma(s_{k})\big). $$ The notation $\gamma(s_{i})$ means the element that $s_{i}$ maps to under $\gamma$, which is usual function notation. It is common in the literature to see the product $\gamma\sigma\gamma^{-1}$ written as $\sigma^{\gamma}$ (and called conjugation), so that the permutation in the exponent ($\gamma$) is applied to each of the entries of the base ($\sigma$). In particular, if $\sigma$ and $\gamma$ are transpositions with $\sigma = (i\quad j)$ and $\gamma = (j\quad k)$, then $\gamma^{-1} = \gamma$ and $$ (i\quad j)^{(j\enspace k)} = \sigma^{\gamma} = \gamma\sigma\gamma^{-1} = \gamma\sigma\gamma = (j\quad k)(i\quad j)(j\quad k) = (i\quad k).\tag{$\ast$} $$ With this, it becomes easy to determine how to write a transposition as a product of simple transpositions.

The Solution

In the example you have given, we have that $$ (2\quad 6\quad 3\quad 4\quad 5) = (2\quad 5)(2\quad 4)(2\quad 3)(2\quad 6). $$ The transposition $(2\quad 3)$ is already simple. We quickly see that $(2\quad 4) = (2\quad 3)^{(3\enspace4)}$, so that $$ (2\quad 4) = (3\quad 4)(2\quad 3)(3\quad 4). $$ The other two transpositions are quickly seen to be the products that you describe, so that we can write $$ (2\quad 6\quad 3\quad 4\quad 5) $$ as the product $$ \color{red}{(4\quad 5)(3\quad 4)(2\quad 3)(3\quad 4)(4\quad 5)} \color{blue}{(3\quad 4)(2\quad 3)(3\quad 4)}(2\quad 3)\\ \color{green}{(5\quad 6)(4\quad 5)(3\quad 4)(2\quad 3)(3\quad 4)(4\quad 5)(5\quad 6)}. $$ (The colours only indicate the different original transpositions.) This is exactly what you have (except the penultimate $(3\quad 4)$ that you missed). Since these are each simple transpositions, you can quickly check that this is correct by calculating their multiple and observing that it is indeed $(2\quad 6\quad 3\quad 4\quad 5)$.

An Exercise

In fact, the set of all simple transpositions $$ \big\{\, (i\quad j) \in S_{n} : i \in \{1, 2, \ldots, n-1\} \,\big\} $$ generates $S_{n}$. This means that any element of $S_{n}$ can be written as a product of simple transpositions. The proof isn't terribly difficult, and is a good exercise in applying the rule $(\ast)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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