2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Litho Sep 25 '17 at 13:19
  • $\begingroup$ @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. $\endgroup$ – Mitchell Faas Sep 25 '17 at 13:27
  • 2
    $\begingroup$ 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. $\endgroup$ – Qudit Sep 25 '17 at 13:28
1
$\begingroup$
  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.

$\endgroup$

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.