0
$\begingroup$

Prove that a cycle of length $k\geq 2$ can be written as a product of $k-1$ transpositions as follows: $$ (a_1 ... a_{k-1} a_{k})=(a_1 a_{k})(a_1 a_{k-1})...(a_1 a_2).$$ I found an answer here: Permutations as a product of transpositions but I'm not able to generalize.
It has kind of been an intuition that it will be correct, but I'm not able to present logical mathematical arguements.

$\endgroup$
3
  • $\begingroup$ Did you try induction on $k$? $\endgroup$
    – bof
    May 28, 2020 at 7:58
  • $\begingroup$ If you just want to show that a cycle of length $k$ can be written as a product of $k-1$ transpositions, another way is $$(a_1\ a_2\ \dots\ a_k)=(a_1\ a_2)(a_2\ a_3)\cdots(a_{k-1}\ a_k).$$ Don't know if that identity is any easier or harder to verify than the other one. $\endgroup$
    – bof
    May 28, 2020 at 8:03
  • $\begingroup$ @bof I thought of induction but wasn't exactly sure how to handle the cases. $\endgroup$ May 28, 2020 at 8:16

1 Answer 1

1
$\begingroup$

Prove by induction. For $k = 2$, $(a_1a_2)$ is already a transposition. Now suppose: $$ (a_1\cdots a_{k-1}a_k) = (a_1a_k)(a_1a_{k-1})\cdots(a_1a_2) $$ Then: $$ (a_1\cdots a_ka_{k+1}) =^! (a_1a_{k+1})(a_1\cdots a_{k-1}a_k) = (a_1a_{k+1})(a_1a_k)(a_1a_{k-1})\cdots(a_1a_2) $$ So the only non-trivial part of this proof is the equality $=^!$.


To show this, we want to show that applying the permutation $(a_1\cdots a_ka_{k+1})$ to any $a_i$ is the same as applying the permutation $(a_1a_{k+1})(a_1\cdots a_{k-1}a_k)$. We consider a few cases.

Case 1: $i = k$. Then applying $(a_1\cdots a_ka_{k+1})$ to $a_k$ clearly gives $a_{k+1}$. On the other hand, applying $(a_1\cdots a_{k-1}a_k)$ to $a_k$ gives $a_1$, and composing it with $(a_1a_{k+1})$ gives $a_{k+1}$.

Case 2: $i = k+1$. Applying $(a_1\cdots a_ka_{k+1})$ to $a_{k+1}$ clearly gives $a_1$. $(a_1\cdots a_{k-1}a_k)$ has no effect on $a_{k+1}$, but $(a_1a_{k+1})$ swaps it to give $a_1$.

Case 3: $i = 1,2,\dots,k-1$. Applying $(a_1\cdots a_ka_{k+1})$ to $a_i$ clearly gives $a_{i+1}$, and same for applying $(a_1\cdots a_{k-1}a_k)$. Since $i+1 \neq 1,k+1$, $(a_1a_{k+1})$ has no effect on $a_{i+1}$, so it still gives $a_{i+1}$.

In all cases, both permutations permutate $a_i$ to the same position.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .