# Can I get disjoint cycles decomposition of $\sigma \in S_n$ from the partition of $I_n$ into orbits under the action of $\langle \sigma \rangle$?

I'm aware of this similar post, whose answer, though, is too "implicit" for my understanding. Then, I reformulate as follows.

Given a permutation $$\sigma \in S_n$$, let's consider the cyclic subgroup generated by $$\sigma$$, $$\langle \sigma \rangle = \lbrace \sigma^k, k=1,\dots,o(\sigma) \rbrace \le S_n$$, and its action on the set $$I_n=\lbrace 1,\dots,n \rbrace$$. The orbit by $$j \in I_n$$ induced by this action is given by the collection $$O_\sigma(j)=\lbrace \sigma^k(j), k=1,\dots,o(\sigma) \rbrace \subseteq I_n$$. By the Orbit-Stabilizer Theorem, the size of the orbit -namely the cardinality of the set $$O_\sigma(j)$$- is given by:

$$|O_\sigma(j)|=\frac{o(\sigma)}{|\mathcal{Fix}_\sigma(j)|}=[\langle\sigma\rangle:\mathcal{Fix}_\sigma(j)] \tag 1$$

where $$\mathcal{Fix_\sigma(j)}:=\lbrace \sigma^k \in \langle\sigma\rangle \mid \sigma^k(j)=j \rbrace \le \langle \sigma \rangle$$. Furthermore, the number of the orbits is given by:

$$|\mathcal{O}_\sigma| = \frac{\sum_{j \in I_n}|\mathcal{Fix}_\sigma(j)|}{o(\sigma)} \tag 2$$

where $$\mathcal{O}_\sigma:=\lbrace O_\sigma(j), j \in I_n\rbrace$$.

Lemma. $$\forall \sigma \in S_n, \forall j \in I_n$$, $$\exists l, 1 \le l \le o(\sigma)$$, such that $$\sigma^i(j) \ne \sigma^k(j), \forall i,k, 1 \le i< k \le l$$.

Proof. Call $$V_\sigma(j):=\lbrace k \in I_{o(\sigma)} \mid \sigma^k(j)=j \rbrace$$; note that $$1 \le o(\sigma) \in V_\sigma(j)$$, so that $$V_\sigma(j) \cap \mathbb{Z}_+ \ne \emptyset$$. For the Well-Ordering Principle, $$\exists m=m(\sigma,j)$$ such that $$m=\operatorname{min}V_\sigma(j)$$. Suppose, by contrapositive, that $$\exists i,k, 1 \le i < k \le m$$ such that $$\sigma^i(j)=\sigma^k(j)$$; then, $$\sigma^{k-i}(j)=j$$ and then $$k-i \in V_\sigma(j)$$; but $$i \ge 1 \Rightarrow -i \le -1 \Rightarrow k-i \le k-1 \le m-1 < m = \operatorname{min}V_\sigma(j) \Rightarrow$$ $$k-i \notin V_\sigma(j)$$: contradiction. Therefore, the positive integer $$m$$ is the $$l$$ claimed in the Lemma. $$\Box$$

In turn, the positive integer $$l=l(\sigma,j)$$ claimed in the Lemma is $$|O_\sigma(j)|$$ given by $$(1)$$.

So, finally, $$\forall \sigma \in S_n, \exists \lbrace i_1,\dots,i_r \rbrace \subseteq I_n$$, with $$r=|\mathcal{O}_\sigma|$$ given by $$(2)$$, such that:

\begin{alignat}{1} \mathcal{O_\sigma}=\{O(i_k), k=1,\dots,r\}=\lbrace &\lbrace \sigma(i_1), \sigma^2(i_1),\dots,\sigma^{l(\sigma,i_1)}(i_1)=i_1 \rbrace, \\ &\lbrace \sigma(i_2), \sigma^2(i_2),\dots,\sigma^{l(\sigma,i_2)}(i_2)=i_2 \rbrace, \\ &\dots, \\ &\lbrace \sigma(i_r), \sigma^2(i_r),\dots,\sigma^{l(\sigma,i_r)}(i_r)=i_r \rbrace \rbrace \\ \tag 3 \end{alignat}

and $$\sum_{k=1}^r l(\sigma,i_k)=n$$.

Q1: Is this formulation correct?

Q2: Can I use it to derive the decomposition of $$\sigma$$ into its disjoint cycles, $$\sigma=c_{\sigma,i_1} c_{\sigma,i_2} \dots c_{\sigma,i_r}$$, by a suitable definition of the $$c_{\sigma,i_k}$$'s prompted by $$(3)$$? I expected so, but I can't conclude.

Edit. (Subscripts "$$_\sigma$$" omitted)

For every orbit, let's define $$\alpha_k$$ the extension by the identity map of the restriction of $$\sigma$$ to the orbit $$O(i_k)$$, namely:

\begin{alignat}{1} \alpha_k(j):=\sigma(j), j \in O(i_k) \\ \alpha_k(j):=j, j \in O(i_{l\ne k}) \\ \tag 4 \end{alignat}

Firstly, $$\alpha_k \in S_n, k=1,\dots,k$$, because $$\sigma_{|O(i_K)} \in \operatorname{Sym}(O(i_k))$$. Then, since $$j \in O(i_m) \Rightarrow$$ $$\sigma(j) \in O(i_m)$$, it is:

\begin{alignat}{1} &\alpha_k^{l_k}(\sigma^j(i_k))=\sigma^{l_k}(\sigma^j(i_k))=\sigma^j(\sigma^{l_k}(i_k))=\sigma^j(i_k), j=1,\dots,l_k \Leftrightarrow \alpha_k^{l_k}(j)=j, j \in O(i_k)\\ &\alpha_k^{l_k}(j)=j, j \in O(i_{j\ne k}) \end{alignat}

and finally

$$\alpha_k^{l_k}=\iota_{S_n}, k=1,\dots,r \tag 5$$

So, $$\alpha_k$$ is a $$l_k$$-cycle, $$k=1,\dots,r$$.

Moreover, by definition $$(4)$$, for $$l\ne k$$ we get:

\begin{alignat}{1} &(\alpha_l\alpha_k)(j)=\alpha_l(\alpha_k(j))=\alpha_l(\sigma(j))=\sigma(j), j \in O(i_k) \\ &(\alpha_l\alpha_k)(j)=\alpha_l(\alpha_k(j))=\alpha_l(j)=\sigma(j), j \in O(i_l)\\ &(\alpha_l\alpha_k)(j)=\alpha_l(\alpha_k(j))=\alpha_l(j)=j, j \in O(i_{j\ne k,l}) \\ \end{alignat}

or, equivalently:

\begin{alignat}{1} &(\alpha_l\alpha_k)(j)=\sigma(j), j \in O(i_k) \sqcup O(i_l) \\ &(\alpha_l\alpha_k)(j)=j, j \in O(i_{j\ne k,l}) \\ \end{alignat}

By induction,

\begin{alignat}{1} &(\alpha_1\dots\alpha_r)(j)=\sigma(j), j \in O(i_1) \sqcup \dots \sqcup O(i_r)=I_n \\ &(\alpha_l\alpha_k)(j)=j, j \in \emptyset \\ \end{alignat}

and finally:

$$\alpha_1\dots\alpha_r=\sigma \tag 6$$

• I cannot tell what you are trying to ask, and why it's not addressed by the answer to the other question. – jgon Jul 18 '19 at 17:48
• That said, I'm pretty sure you need to require $l$ to be minimal. – jgon Jul 18 '19 at 17:54
• Then your lemma is the claim that the image of $\sigma$ has a finite order in the symmetric group of an orbit of $\sigma$. – jgon Jul 18 '19 at 17:56

Let $$X$$ be a set. Let $$\newcommand\scrA{\mathscr{A}}\scrA$$ be a partition of $$X$$, so $$\bigcup_{A\in\scrA} A = X,$$ and if $$A\ne B \in \scrA$$, we have $$A\cap B = \varnothing$$. Then we can define the symmetric group of the partition $$\scrA$$ to be the subset of the symmetric group of $$X$$, $$S_\scrA := \{ \sigma \in S_X : \sigma A= A,\forall A\in \scrA\}.$$
Then, observe that $$S_\scrA \simeq \prod_{A\in \scrA} S_A,$$ and that if $$\sigma\in S_X$$ is a permutation, then we can let $$\newcommand\scrO{\mathscr{O}}\scrO$$ be the partition of $$X$$ into orbits under $$\langle\sigma\rangle$$, and observe that $$\langle \sigma\rangle \subseteq S_\scrO$$. Thus by the natural isomorphism above, $$\sigma$$ can be written as the product of the permutations it induces on each orbit.
Thus we just need to show that $$\sigma$$ induces a cyclic permutation on each orbit of $$\langle \sigma \rangle$$. However this is immediate, since an orbit $$\langle \sigma\rangle x$$ is by definition the set of $$\sigma^ix$$ where $$x\in X$$, and $$\sigma(\sigma^ix)=\sigma^{i+1}x$$. Thus on an orbit $$\langle \sigma \rangle x$$, $$\sigma$$ is the cycle $$\begin{pmatrix} x&\sigma x & \sigma^2 x & \cdots & \sigma^{k-1}x\end{pmatrix},$$ where $$k$$ is the order of $$\sigma$$ when restricted to this orbit.