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

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

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.


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.