7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ A simple transposition is a transposition in the form $(i,i+1)$ so (7,8) is a simple transposition but (7,10) is not. $\endgroup$ – Vafa Khalighi Mar 21 '11 at 23:47
  • $\begingroup$ Please help me. Thank you. math.stackexchange.com/questions/423297/… $\endgroup$ – Maizon Jun 18 '13 at 2:53
9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ In other words assume without loss $i+1<j$ and write $(i\ j)^{(i\ i+1)} = (i+1\ j)$. Repeat until satisfied. $\endgroup$ – Myself Mar 21 '11 at 23:59

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.