# Prove that a cycle of length $k\geq 2$ can be written as a product of $k-1$ transpositions.

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.

• Did you try induction on $k$?
– bof
May 28, 2020 at 7:58
• 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.
– bof
May 28, 2020 at 8:03
• @bof I thought of induction but wasn't exactly sure how to handle the cases. May 28, 2020 at 8:16

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.