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

Question

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

Answer 1

I've written some comments on your question above. I don't entirely follow exactly what your question is, but hopefully this answer will be helpful.

A more general formulation of what it seems like you're writing is the following.

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.