# Proof that any $x\in S_n$ can be written as a product of $2$ permutations of order $2$.

I'm working on the following problem:

Show that if $n$ is at least 4, every element of $S_n$ can be written as a product of two permutations, each of with has order 2.

Now I've got a proof, but my proof works for $n\geq 2$, so I'm sceptical about the validity.

Remark$\quad$ Note how for any product of cycles $E = (a,b)(c,d)...(e,f)$ the order of $E$ is 2 if $a\neq b\neq c\ldots$ ($E$ is a product of disjoint cycles with order 2.) Note also how $E_1E_2$ then has order $2$ for the same reason. It thus suffices to show that $S_n$ can be written as a product of 2-cycles.
Proof$\quad$ Consider $x = (a,b) \in S_2$. In this case, the proof is trivial. So assuming any $x\in S_n$ can be written as a product of 2-cycles, we will show that any $y \in S_{n+1}$ can be written as a product of 2-cycles.

Let $y \in S_{n+1} = (y_1\;y_2\;...\;y_{n+1})$. Then $y = x \cdot c$ for some $x\in S_n$ and $c$ a 2-cycle that transposes $y_{n+1}$ to the $i$'th place in the permutation. Then since $x$ can be written as a product of 2-cycles, so can $y$. This completes the proof.

It'd be great if someone could point out any mistakes.

• Try to present $(1, 2)\in S_2$ as a product of two permutations of order 2. Also, what are $E_1$ and $E_2$ and why do you need their product to be of order 2? – Litho Sep 25 '17 at 13:19
• @Litho Yeah, I picked that one up after posting it. $E_1, E_2$ are products of 2 cycles, to satisfy the wording of the question. Should probably rename $E$ to $E_i$ or something. Their product has to be two because each is a product of 2 cycles and thus has order 2. That said, they may not necessarily be disjoint (probably aren't). So that's worth looking at in some more detail. – Mitchell Faas Sep 25 '17 at 13:27
• It isn't true that "it thus suffices to show that $S_n$ can be written as a product of $2$-cycles" so your whole proof is based on a faulty premise. Also, the product of two permutations of order $2$ need not have order $2$ (or even order divisible by $2$) as you claim. – Qudit Sep 25 '17 at 13:28

1. Identity = (1 2) x (1 2).
2. Factor $E$ into disjoint cycles.
3. If $E$ is a single transposition then e.g. (1 2) = (1 2)(3 4) x (3 4). Otherwise distribute disjoint transpositions into the 2 factors, such that each factor gets at least one transposition if more than one disjoint transposition.
4. Each disjoint cycle of length $n \geq 3$ can be factored separately into a product of 2 involutions e.g.

(1 2 3) = (1 3) x (2 3)

(1 2 3 4) = (1 4)(2 3) x (2 4)

(1 2 3 4 5) = (1 4)(2 3) x (2 4)(1 5)

(1 2 3 4 5 6) = (1 4)(2 3)(5 6) x (2 4)(1 5)

(1 2 3 4 5 6 7) = (1 4)(2 3)(5 7) x (2 4)(1 5)(6 7)

(1 2 3 4 5 6 7 8) = (1 4)(2 3)(5 8)(6 7) x (2 4)(1 5)(6 8)

(1 2 3 4 5 6 7 8 9) = (1 4)(2 3)(5 9)(6 8) x (2 4)(1 5)(6 9)(7 8)

(1 2 3 4 5 6 7 8 9 10) = (1 4)(2 3)(5 10)(6 9)(7 8) x (2 4)(1 5)(6 10)(7 9)

If $n \geq 6$ then the factorization of the cycle of length $n$ is derived from the factorization of the cycle of length $n-1$, increasing the number of transpositions in the first factor if $n$ is even, increasing the number of transpositions in the second factor if $n$ is odd.