Let $\sigma \in S_n$, be a permutation, and $X = \{1, 2, ..., n\}$. The cycle decomposition of $\sigma$ can be recovered by considering the orbits of the action of $\langle\sigma\rangle$ on $X$.

Let $\langle \sigma \rangle := G$. By the Orbit-Stabilizer Theorem, the action of $G$ partitions $X$ into unique orbits $O(X)$, and there exists a bijection $f : g \cdot \mathrm{Stab}(X) \mapsto g \cdot X$.

$G = \{e, \sigma, \sigma^2, ..., \sigma^{k-1}\}$ for $G$ of order $k$.

$\mathrm{Stab(X)} = \{\sigma^i \in G : \sigma^i(X) = X\} = O(X)$

Thus the bijection maps $\sigma^i(X) \mapsto \sigma^i(O(X))$ $G$ is cyclic, therefore $G/O(G)$ is cyclic and by Lagrange's theorem we get that $|O(X)| = |G : O(X)| = k$

Thus the cosets of $O(X)$ in $G$ correspond to the permutation $\{O(X), \sigma(O(X)), ..., \sigma^{k-1}(O(X))\}$ where, by the bijection, each of these terms corresponds to $\{X, \sigma(X), ..., \sigma^{k-1}(X)\}$ respectively. Therefore, an orbit $|O(X)| = k$ corresponds to some $k$-cycle, and we get a cycle decomposition.

  • $\begingroup$ Are you looking for a proof verification? $\endgroup$ – Mauve Apr 6 '18 at 17:50
  • $\begingroup$ I could swear I saw a very similar question earlier today (without solution), but I can't find it... Was that you? If yes, did you delete the question to post a new one? $\endgroup$ – Arnaud D. Apr 6 '18 at 18:01
  • $\begingroup$ Yes and yes. It was me, and I am looking for a verification, or to point out any mistakes in the proof, please. $\endgroup$ – The Bosco Apr 6 '18 at 18:03
  • 1
    $\begingroup$ Then you could have simply edited your first question with your attempt. But it's not a big deal ;) $\endgroup$ – Arnaud D. Apr 6 '18 at 18:08
  • $\begingroup$ Remark that $G/O(G)$ (it is a typo I think you mean $G/O(X)$) has no reason to be a group. I also don't understand why $X$ is $\{1,\dots,n\}$ at the beginning and seems to be an element of $X$ at the end (because as it is defined for the moment $Stab(X)=G$). To prove the claim, I think you are forced to write down explicitly the cycles arising in the decomposition of $\sigma$. My advice would be to work with $\sigma$ a cycle (I think I have already given the advice) and maybe work on some explicit example, for instance $(1,2)(4,5,6)$ in $S_6$. $\endgroup$ – Clément Guérin Apr 7 '18 at 3:09

Your claim is obviously true: the cycle decomposition of$~\sigma$ is the collection of orbits of$~\sigma$ on$ ~X$. Or more precisely, that is the combinatorial cycle decomposition, which allows for cycles of length$~1$; a separate one for each fixed point. For the group theoretic cycle decomposition, there is a cyclic permutation for each combinatorial cycle of length${}>1$, obtained from$~\sigma$ by acting as$~\sigma$ on that cycle and as the identity on its complement (and $\sigma$ is then the product of those commuting cyclic permutations).

However your proposed "proof" is completely confused. The orbit-stabiliser theorem needs a base point $x_0\in X$, which you do not choose. The stabiliser then is $\operatorname{Stab}_G(x_0)=\{\,g\in G\mid g\cdot x_0=x_0\}\,$; your $\operatorname{Stab}(X)$ is meaningless (since every $g\in G$ globally maps $X$ to itself, the only meaning one could ascribe to that notation would be all of $G$, but that makes the notation pointless). When you say "bijection" you forget to mention the sets between which the bijection runs; for the orbit-stabiliser theorem it would be between $G/\operatorname{Stab}_G(x_0)$ and the orbit $G\cdot x_0$, but that does not correspond to what you write. So you are off to a very bad start, and there is no sense to be made of the remainder either.


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.