Recall a definition.
3. Definition 1: Independent cycles
We say that cycles $\sigma=\left(i_{1}, \ldots, i_{k}\right)$ and $\mu=\left(j_{1}, \ldots, j_{l}\right)$ are independent if
$$
\left{i_{1}, \ldots i_{k}\right} \cap\left{j_{1}, \ldots, j_{k}\right}=\varnothing
$$
i.e., the sets of elements, which they cyclically permute, do not intersect.
4. The following proposition is obvious.
If cycles $\sigma$ and $\mu$ are independent, then they commute:
$$
\sigma \circ \mu=\mu \circ \sigma
$$
If cycles are not independent, then might not commute, for example for cycles of length two $(1,2)$ and $(2,3)$ in $S_{3}$ we have (remember composing from right to left!)
$$
(1,2)(2,3)=(3,1,2)
$$
while
$$
(2,3)(1,2)=(2,1,3)
$$
are two different cycles of length $3 .$
7. Theorem 1: Factorization into independent cycles
If $\sigma \in S_{n}$ is any permutation, then there exist a collection of mutually independent cycles $\mu_{1}, \ldots, \mu_{l} \in S_{n}$ such that
$$
\sigma=\mu_{1} \circ \mu_{2} \cdots \circ \mu_{s}
$$
Proof. Start with any element $a$ in ${1,2, \ldots, n}$ which is not fixed by $\sigma .$ Consider iterations
$$
a \mapsto \sigma(a) \mapsto \sigma^{2}(a) \mapsto \ldots \sigma^{k}(a) \mapsto \ldots .
$$
At some step $l_{1}$ we again encounter $a$. Denote the corresponding cycle as
$$
\mu_{1}=\left(a, \sigma(a), \ldots, \sigma^{l_{1}-1}(a)\right)
$$
Then $\mu_{1}$ and $\sigma$ act in the same way on all the elements $\left{a, \sigma(a), \ldots, \sigma^{l_{1}-1}(a)\right}$ (equivalently $\mu_{1}^{-1} \circ \sigma$ fix these elements).
Pick another element $b \in{1, \ldots, n}$ not fixed by $\mu_{1}^{-1} \circ \sigma$, and repeat the procedure, identifying new cycle $\mu_{2}$. This cycle will be independent with $\mu_{1}$, and now $\mu_{2}^{-1} \circ \mu_{1}^{-1} \circ \sigma$ fixes even more elements then $\mu_{1}^{-1} \circ \sigma$. Iterate this procedure, until we end up with the permutation $\mu_{s}^{-1} \circ \cdots \circ \mu_{2}^{-1} \circ \mu_{1}^{-1} \circ \sigma$ which fixes all the elements. It means that this permutation is the identity permutation, thus
$$
\sigma=\mu_{1} \ldots \mu_{s}
$$
is the factorization of $\sigma$ into independent cycles, as claimed.
Consider
$$
\sigma=\left(\begin{array}{lllll}
1 & 2 & 3 & 4 & 5 \
3 & 4 & 5 & 2 & 1
\end{array}\right)
$$
Then following the above procedure we find a factorization
$$
\sigma=(1,3,5)(2,4)
$$
Factorization into independent cycles is unique up to a reordering of $\mu_{i}$ ‘s.
Factorization into independent cycles comes in handy, when we need to find the order of a given permutation.
10. Theorem 2: Order of permutation
- If $\mu$ is a cycles of length $l$, then order of $\mu$ is $l$.
- If $\sigma=\mu_{1} \ldots \mu_{s}$ is a factorization of $\sigma$ into independent cycles of length $l_{1}, \ldots, l_{s}$, then the order of $\sigma$ is $\operatorname{lcm}\left(l_{1}, \ldots, l_{s}\right)$
Proof. 1. If $\mu=\left(i_{1}, \ldots, i_{l}\right)$ is a cyclic permutation of $\left{i_{1}, \ldots, i_{l}\right}$, then for any $k<l$ we have
$$
\mu^{k}\left(i_{1}\right)=i_{k+1} \neq i_{1}
$$
thus $\mu^{k}$ cannot be identity for $k<l$. On the other hand, after $l$ iterations of $\mu$ each of the elements $i_{1}, \ldots, i_{l}$ makes a full circle, returning back to its place, thus $\mu^{l}=i d$.
- Let $L:=\operatorname{lcm}\left(l_{1}, \ldots, l_{s}\right)$. First we check that $\sigma^{L}=i d$. Using the fact (identity $*$ below) that independent cycles commute with each other, we find:
$$
\sigma^{L}=\left(\mu_{1} \ldots \mu_{s}\right)^{L} \stackrel{*}{=} \mu_{1}^{L} \ldots \mu_{s}^{L}=i d,
$$
where in the last identity we used the fact that each $\mu_{i}^{L}=i d$ as length $\left(\mu_{i}\right) \mid L$.
Finally it remains to check that if $d<\operatorname{lcm}\left(l_{1}, \ldots, l_{s}\right)$, then $\sigma^{d} \neq i d .$ Indeed, since $d<L$ we have that one of the lengths $l_{i}$ of $\mu_{i}$ does not divide $d$. But then $\sigma^{d}$ does not fix elements of cycles $\mu_{i}$ and cannot be identity.
The order of permutation
$$
\sigma=\left(\begin{array}{lllll}
1 & 2 & 3 & 4 & 5 \
3 & 4 & 5 & 2 & 1
\end{array}\right)
$$
is $\operatorname{lcm}(3,2)=6$.
Problem 1: Find all possible orders of elements of $S_{7}$.