# Group of permutations and disjoint cycles.

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.
• 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$?. – YTS Jun 22 '14 at 16:01
• 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. – André Nicolas Jun 22 '14 at 16:05