On page 66 of these notes is proposition 4.26:

Every permutation can be written (in essentially one way) as a product of disjoint cycles.

The proof begins as follows:

Let $\sigma \in S_n$, and let $O \subseteq \{1,...,n\}$ be an orbit for $\langle \sigma \rangle$....

What does it mean for $O$ to be an orbit for $\langle \sigma \rangle$? I am unfamiliar with this terminology. From what I gather, the implicit action is of $S_n$ on $\{1,...,n\}$ by functional evaluation. So, $O$ will be the orbit of some element in $\{1,...,n\}$. How can it be an orbit for $\langle \sigma \rangle$?


Also, the author writes $O = \{i,\sigma (i),..., \sigma^{r-1}(i)\}$. How do we know this equality holds? What if $\sigma$ has order smaller than $r-1$?

  • 2
    $\begingroup$ How did they define $r$? $\endgroup$ – Mike Earnest Mar 14 '19 at 15:32
  • 2
    $\begingroup$ $O$ is the orbit of $i$ under the action of the cyclic subgroup $\langle \sigma \rangle$ [this action naturally being the restriction of the action of $S_n$]. $\endgroup$ – M. Vinay Mar 14 '19 at 15:34
  • $\begingroup$ See also Exercise 7 on UMN Fall 2017 Math 4990 homework set #7 for a version of this proof with all details filled in. It is one of the most painful to formalize proofs in basic abstract algebra. (Note that my $\sim$-equivalence classes are exactly the orbits of $\sigma$, although I define them a bit differently.) $\endgroup$ – darij grinberg Mar 14 '19 at 15:37

Call $I_n:=\{1,\dots,n\}$. For any given $\sigma \in S_n$, consider the map $\mathcal{A}_\sigma\colon \langle\sigma\rangle \times I_n \rightarrow I_n$, $(\sigma^k,i) \mapsto \sigma^k(i)$. Now:

  1. for $k=o(\sigma)$, $\iota_{S_n}=\sigma^{o(\sigma)} \in \langle \sigma \rangle$ and $(\iota_{S_n},i)=\iota_{S_n}(i)=i, \forall i \in I_n$;
  2. $(\sigma^k\sigma^l,i)=(\sigma^k\sigma^l)(i)=\sigma^k(\sigma^l(i))=(\sigma^k,(\sigma^l,i))$

so that $\mathcal{A}_\sigma$ is an action. In particular, the orbit "by the point" $j \in I_n$ is the set:

$$O_\sigma(j):=\{\sigma(j),\dots,\sigma^{l_j}(j)=j\} \tag 1$$

where $l_j$ $(\le o(\sigma))$ is the least value of the exponent $k$ such that $\sigma^k(j)=j$.

The number of orbits is given by:

$$r=\frac{1}{o(\sigma)}\sum_{k=1}^{o(\sigma)}\operatorname{Fix}(\sigma^k)=\frac{1}{o(\sigma)}\sum_{j=1}^{n}\operatorname{Stab}(j) \tag 2$$

where $\operatorname{Fix}(\sigma^k):=\{j \in I_n\mid \sigma^k(j)=j\}$ and $\operatorname{Stab}(j):=\{\sigma^k \in \langle\sigma\rangle\mid \sigma^k(j)=j\} \le \langle\sigma\rangle$. Therefore, $\exists \{j_1,\dots,j_r\} \subseteq I_n$ such that:

$$I_n = \bigsqcup_{k=1}^{r}O_\sigma(j_k) \tag 3$$

Note that $\sigma_{|O_\sigma(j_k)}$ is a bijection on $O_\sigma(j_k)$, so that its extension to $I_n$ by the identity map, say $\alpha_k$, is a bijection on $I_n$, namely $\alpha_k \in S_n$. One could prove that $\alpha_k^{l_k}=\iota_{S_n}$, where $l_k$ is defined above (so, $\alpha_k$ is a $l_k$-cycle), and that $\sigma=\alpha_1\dots\alpha_r$: this is the decomposition of a permutation into disjoint cycles, which depends on $\sigma$ solely. "Disjoint" because $supp(\alpha_k)=O_\sigma(j_k)$. This is addressed in the Edit of this post of mine.


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.