In the Dummit-Foote text the algorithm for cycle decomposition is given as:enter image description here

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?



Since we can decompose any permutation $\sigma$ into product of commuting cycles $c_i$: $$\sigma=c_1c_2\cdots c_p$$ and suppose that the order of $c_i$ is $m_i$: $o(c_i)=m_i$ so prove that: $$o(\sigma)=\mathrm{lcm}(m_1,\ldots,m_p)$$


So all you need now is to show that any cycle can be written as the product of transposition...:


Oberve that there are $\,n-1\,$ transpositions in the RHS above...

  • $\begingroup$ But the $2$-cycles in the RHS need not be commuting. $\endgroup$ – Sriti Mallick Aug 29 '13 at 11:18
  • $\begingroup$ Yes, I know...so? $\endgroup$ – DonAntonio Aug 29 '13 at 11:23
  • $\begingroup$ errr... why my solution is incomplete? Where should I insert that any cycle can be written as... $\endgroup$ – Sriti Mallick Aug 29 '13 at 11:26
  • $\begingroup$ I really didn't read your whole solution: too long and complicated for me. What I remark is that if you already know that any permutation is the product of disjoint cycles and if you know that it is an even permutation iff the number of even cycles is even, then with what I wrote you're done... $\endgroup$ – DonAntonio Aug 29 '13 at 11:32

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.