Skip to content

抽象代数代写| Cycles factorizations

1. Permutation group

2. Cycles factorization

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.

5. Proposition 1

If cycles $\sigma$ and $\mu$ are independent, then they commute:

$$
\sigma \circ \mu=\mu \circ \sigma
$$

6. Remark 1

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.

8. Example 1

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

9. Remark 2

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

  1. If $\mu$ is a cycles of length $l$, then order of $\mu$ is $l$.
  2. 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$.

  1. 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.

11. Example 2

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

发表回复

您的电子邮箱地址不会被公开。