Two cycle $[i_1,..., i_r]$ and $[j_1,...,j_s]$ are said disjoint if no integer $i_\eta$ is equal to any integer $j_{\mu}$. Prove that a pemutation is equal to a product of disjoint cycles.

I was thinking prove it by induction but I get in a problem because I don't know exactly on what I should do induction. I mean if I have any permutation $\sigma \in S_n$ and an element $i\in \{1,2,...,n\}$ we can form a cycle from $i$ by $\sigma i, \sigma^2 i, \sigma ^2 i...\sigma^r i$ written as $\tau=[i_1,i_2,...,i_r ]$ for some $r$. Any element $i_j$ is a fixed point of $\tau^{-1}\sigma$ then we can think $\tau^{-1}\sigma$ as a biyection on a set with less than $n$ elements and apply induction. But this set is no necessarily of the form $\{1,...,s\}$ with $s<n$ then I don't know if an induction argument would be well use.


Outline: For the induction step, we use "strong" induction. We suppose that a permutation of a set of $\lt n$ objects is a product of disjoint cycles, and show that a permutation of a set of $n$ objects is a product of disjoint cycles.

Let $A$ be an $n$-element set. If the permutation $\sigma$ does not move anything, we are finished. Otherwise, suppose that $\sigma$ moves $a$. Consider the cycle $\alpha$ generated by $a$. If $\alpha=\sigma$, we are finished. If not, look at $\sigma$ restricted to the set of all objects not of the form $\sigma^k a$. This is a permutation of a set with fewer than $n$ elements.

  • $\begingroup$ You did exactly what I did. Then I assume what I did is well done. But why this argument is fine if we permutate a subset of $\{1,...,n\}$ not of the form $\{1,...,s\}$ with $s<n$?. $\endgroup$ – YTS Jun 22 '14 at 16:01
  • 2
    $\begingroup$ Note that the induction assumption that I used is that a permutation of any set with $\lt n$ elements is a product of disjoint cycles. $\endgroup$ – André Nicolas Jun 22 '14 at 16:05

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.