# 抽象代数代写| Permutations. Cycles

1. Permutation group

Let $X$ be a finite set. For concreteness rename its elements so that

$$X={1,2, \ldots, n}$$

Recall that $\mathcal{B}(X)$ denotes the set of all bijections (or shuffles of $X$ )

$$f: X \rightarrow X$$

2. Example 1: $n=3$

Below are diagrams of two bijections $f_{1}: X \rightarrow X$ and $f_{2}: X \rightarrow X$ for $X={1,2,3} .$

Given two maps $f_{1}: X \rightarrow X$ and $f_{2}: X \rightarrow X$ we can compose them in any order we like. In terms of mapping diagrams as above this amounts to stacking the together. For instance $f_{1} \circ f_{2}$ (first $f_{2}$, then $f_{1}-$ right to left, as usual with compositions) has the mapping diagram as follows

Problem 1: Find the mapping diagram of $f_{2} \circ f_{1}$ and verify that $f_{2} \circ f_{1} \neq f_{1} \circ f_{2}$.

The set of bijections $\mathcal{B}(X)$ together with the composition operation form a group. Traditionally it is denoted by $S_{n}$, where $n=|X|$ is the cardinality of $X$, and its elements (bijections of $X$ ) are denoted by Greek letters $(\sigma, \tau, \mu, \ldots)$.

3. Definition 1: Permutation group

Permutation group $S_{n}$ of the set $X={1,2, \ldots, n}$ is the set of all bijections

$$\sigma:{1,2, \ldots, n} \rightarrow{1,2, \ldots n}$$

endowed with the composition operation.

4. Specifying elements of $S_{n}$.

The most straightforward way to specify an element $\sigma$ of $S_{n}$ is to encode all the images $\sigma(i)$ of individual elements $1 \leqslant i \leqslant n$. It is convenient to store this data in a table of size $2 \times n$ :

$$\sigma=\left(\begin{array}{cccc} 1 & 2 & \ldots & n \ \sigma(1) & \sigma(2) & \ldots & \sigma(n) \end{array}\right)$$

For example map $f_{2}$ from above would be

$$f_{2}=\left(\begin{array}{lll} 1 & 2 & 3 \ 2 & 3 & 1 \end{array}\right)$$

Problem 2: Consider a permutation $\sigma$ given by a table

$$\left(\begin{array}{cccc} 1 & 2 & \ldots & n \ i_{1} & i_{2} & \ldots & i_{n} \end{array}\right)$$

Prove that the table of $\sigma^{-1}$ is obtained from

$$\left(\begin{array}{cccc} i_{1} & i_{2} & \ldots & i_{n} \ 1 & 2 & \ldots & n \end{array}\right)$$

by reordering its columns according to the top values in the first row.

The neutral element of $S_{n}$ is given by the “trivial” table

$$i d=\left(\begin{array}{llll} 1 & 2 & \ldots & n \ 1 & 2 & \ldots & n \end{array}\right)$$

5. Proposition 1

$\left|S_{n}\right|=n !$, where $n !=1 \cdot 2 \cdot 3 \cdots \cdots$

Proof. To specify the number of bijections $\sigma:{1,2, \ldots, n} \rightarrow{1,2, \ldots, n}$ we need to

1. set $\sigma(1)$-we have $n$ choices for it (any element of ${1,2, \ldots, n}$ )
2. set $\sigma(2)$ – we have $(n-1)$ choices left (any element of ${1,2, \ldots, n}$ except for $\sigma(1)$, since $\sigma$ is bijective) 3. …

n. set $\sigma(n)$ – we have exactly one choice left (the unique element other that $\sigma(1), \sigma(2), \ldots, \sigma(n-1))$.

Overall this gives $n \cdot(n-1) \cdots \cdots 1=n !$ options.

6. Cycles

7. Definition 2: Cycle

Permutation $\sigma \in S_{n}$ is called as cycle of length $k \geqslant 2$, if there exist $k$ distinct elements $i_{1}, \ldots, i_{k} \in{1,2, \ldots n}$ such that $\sigma$ cyclically rotates $i_{1}, \ldots, i_{k}$ :

$$i_{1} \stackrel{\sigma}{\rightarrow} i_{2} \stackrel{\sigma}{\rightarrow} i_{3} \stackrel{\sigma}{\rightarrow} \ldots \stackrel{\sigma}{\rightarrow} i_{k} \stackrel{\sigma}{\rightarrow} i_{1}$$

and all the remaining elements are kept in place.

For $\sigma$ as above, we will use a shorthand

$$\sigma=\left(i_{1}, i_{2}, \ldots i_{k}\right)$$

This presentation is clearly not uniques, as we can also write the same $\sigma$ as

$$\sigma=\left(i_{2}, i_{3}, \ldots i_{k}, i_{1}\right)$$

8. Example 2

Element $\sigma \in S_{3}$

$$\sigma=\left(\begin{array}{lll} 1 & 2 & 3 \ 3 & 2 & 1 \end{array}\right)$$

is a cycle of length 2, as it cyclically permutes 1 and $3 .$

On the contrary element $\tau \in S_{4}$

$$\tau=\left(\begin{array}{llll} 1 & 2 & 3 & 4 \ 3 & 4 & 1 & 2 \end{array}\right)$$

is not a cycle, since it simultaneously swaps 1 with 3 and 2 with $4 .$

9. Definition 3: 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.

10. The following proposition is obvious.

11. Proposition 2

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

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

12. 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_{l}$$

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 the permutation $\sigma$ is decomposed into a product of independent cycles.

13. Example 3

Consider

$$\sigma=\left(\begin{array}{lllll} 1 & 2 & 3 & 4 & 5 \ 3 & 4 & 5 & 2 & 1 \end{array}\right)$$

The following the above procedure we find a factorization

$$\sigma=(1,3,5)(2,4)$$

14. Remark 1

Factorization into independent cycles is unique up to a reordering of $\mu_{i}$ ‘s.