# Is any transposition a product of simple transpositions?

Is any transposition a product of simple transpositions? If yes, how can you prove this?

-

A simple transposition is a transposition in the form $(i,i+1)$ so (7,8) is a simple transposition but (7,10) is not. – Vafa Khalighi Mar 21 '11 at 23:47

## 3 Answers

Every element of $S_n$ can be written as a product of simple transpositions. This fact can be proven by induction on $n$.

As a first step, prove that $(1,m)$ is always a product of simple transpositions by induction of $m$. The case $m = 2$ is trivial, so we assume that $(1,m-1)$ is a product of simple transpositions. But $(1,m) = (m-1,m)(1,m-1)(m-1,m)$, so $(1,m)$ is a product of simple transpositions.

Now we show that all transpositions in $S_n$ are products of transpositions of the form $(1,m)$. The case $n = 2$ is trivial, so we assume that any transposition of $S_{n-1}$ is such a product. Given the transposition $t$, we must have some $m$, possibly $1$ which exchanges position with 1. If we perform the transposition $(1,m)$, we only have $n-1$ positions left to permute, which can be done using simple transpositions by the inductive hypothesis. This completes the proof.

-

There is an algorithm that takes a permutation and writes it as a product of simple transpositions. It's called bubble sort.

What you do is : if $f(i) > f(i+1)$, write $f$ = $f' \circ (i,i+1)$. Repeat on $f'$ until you get the identity and are left with a product of simple transposition.

-

Yes. One way to see this is to notice what happens when you conjugate transpositions by transpositions. For example, $(5,6)(3,6)(5,6)=(3,5)$ shows that you can get one step closer to a simple transposition, from $(3,6)$ to $(3,5)$, by conjugating by $(5,6)$. Then $(4,5)(3,5)(4,5)=(3,4)$, so we've gotten to a simple transposition after $2$ conjugations. To write $(3,6)$ as a product of simple transpositions, you can just unwind this: $(3,6)=(5,6)(4,5)(3,4)(4,5)(5,6)$.

-

In other words assume without loss $i+1<j$ and write $(i\ j)^{(i\ i+1)} = (i+1\ j)$. Repeat until satisfied. – Myself Mar 21 '11 at 23:59
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8940734267234802, "perplexity_flag": "head"}