Showing simple transpositions given a permutation
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$ 21 Answer
$\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$
