In the Dummit-Foote text the algorithm for cycle decomposition is given as:
Based on the above algorithm the following exercise is asked to solve: Show that an element has order $2$ in $S_n$ if and only if its cycle decomposition is a product of
commuting $2$-cycles.
The problem, even though, is not hard to interpret, I still want it to leave for verification since the solutions of problems on symmetric group often contain less symbol and more word. Please have a look to the logic I used and comment on its validity
My attempt:
Lemma: Cycle decomposition decomposes permutation into disjoint cycles: For otherwise, let the cycles $C_1,C_2$ have some element in common, x say. Let in course of the decomposition $C_1$ (whose first element is assumed to be $a$) is constructed earlier than $C_2$ (whose first element is assumed to be $b$). Then $x=\sigma^i(a)=\sigma^j(b)\implies\sigma^{i-j}(a)=b,$ a contradiction.
Proof of the Exercise: Let $\sigma\in S_n$ be such that $|\sigma|=2.$ Since $\sigma\ne1,$ the cycle decomposition of $\sigma$ must contain a cycle (of length greater than 1). If possible, let the decomposition of $\sigma$ contains a cycle of length $\ge3,$ say $(a_1~a_2~a_3~…).$ Then $\sigma^2(a_1)=a_3$ (by the construction of the algorithm) $\ne a_1,$ a contradiction to $\sigma^2=1.$ Thus cycle decomposition is a product of $2$-cycles and since they are disjoint (Ref: Lemma) they must be commuting.
Conversely, let $\sigma$ be such that it's cycle decomposition is a product of commuting $2$-cycles. Since those cycles appear due to cycle decomposition they must be mutually disjoint. Clearly $|\sigma|\ge2$ for otherwise $\sigma$ won't consider any $2$-cycle. Choose $x\in\{1,2,…,n\}.$
-
If $x$ doesn't appear in any $2$-cycle $\sigma^2(x)=x.$
-
If $x$ appears in any $2$-cycle $\sigma^2(x)=x$ (by the construction of the algorithm).
Thus $\sigma^2=1\implies|\sigma|=2.$
Am I correct?
Best Answer
So all you need now is to show that any cycle can be written as the product of transposition...:
$$(i_1\,i_2\,\ldots\,i_n)=(i_2\,i_3)(i_3\,i_4)\cdot\ldots\cdot(i_{n-1}\,i_n)(i_n\,i_1)$$
Oberve that there are $\,n-1\,$ transpositions in the RHS above...