# Orbit of a Permutation

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$$?

EDIT

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$$?

• How did they define $r$? – Mike Earnest Mar 14 '19 at 15:32
• $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$]. – M. Vinay Mar 14 '19 at 15:34
• 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.) – 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.