Cycle and Cycle Decomposition

cycle

A cycle is a string of integers which represents the elements of $S_{n}$ which cyclically permutes these integers. The cycle $(a_{1} \dots a_{m})$ is the permutation which sends $a_{i}$ to $a_{i + 1}$ for $1 \leq i \leq m - 1$ and sends $a_{m}$ to $a_{1}$ .

For example, $(3 1 2)$ maps 2 to 1, 1 to 3, 3 to 2. In general, for $σ \in S_{n}$ the numbers from $1$ to $n$ will be rearranged and groups into $k$ cycles of the form:

(a_{1} a_{2} \dots a_{m_{1}}) (a_{m_{1} + 1} a_{m_{1} + 2} \dots a_{m_{2}}) \dots (a_{m_{k - 1} + 1} a_{m_{k - 1} + 2} \dots a_{m_{k}})

from which the action of $σ$ on any number from $1$ to $n$ can easily be read, as follows. For any $x \in {1, 2, 3, \dots, n}$ first locate $x$ in the above expression. If $x$ is not followed immediately by a right parenthesis (ie: $x$ is not at the right end of one of the $k$ cycles) then $σ (x)$ is the integer appearing immediately to the right of $x$ . If $x$ is followed by a right parenthesis, then $σ (x)$ is the number which is at the start of the cycle ending with $x$ (ie: if $x = a_{m_{i}}$ for some $i$ , then $σ (x) = a_{m_{i - 1} + 1}$ (where $m_{0}$ is taken to be 0)). We can represent this description of $σ$ by:

Pasted image 20250112172735.png

cycle decomposition of

σ

The product of all the cycles is called the cycle decomposition of $σ$ .

Cycle Decomposition Algorithm

Pasted image 20250112172929.png

length

The length of a cycle is the number of integers which appear in it.

By convention 1-cycles aren't written (so if an integer is missing, it's in it's own cycle). For example $(2 3)$ in $S_{6}$ is the cycle that swaps $2, 3$ and keeps everything else the same.

Why Use the Convention?

We can count the number of cycle decompositions of $S_{n}$ since these are equivalent to permutations. For example $(2 3)$ for $S_{6}$ is the permutations:

(\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 3 & 2 & 4 & 5 & 6 \end{matrix})

For any $σ \in S_{n}$ the cycle decomposition of $σ^{- 1}$ is obtained by writing the numbers in each cycle of the cycle decomposition of $σ$ in reverse order. For example if $σ = (1 12 8 10 4) (2 13) (5 11 7) (6 9)$ is:

σ^{- 1} = (4 10 8 12 1) (13 2) (7 11 5) (9 6)

Right to left for products

For successive products we read from right to left:

σ_{2} σ_{1} = (4 5) (1 2 3)

In particular the example $(1 2) \circ (1 3) = (1 3 2) \neq (1 2 3) = (1 3) \circ (1 2)$ is an example of showing $S_{3}$ is not an Abelian Group. Namely, similar to Dihedral Groups, $S_{n}$ is not abelian for $n \geq 3$ .

Furthermore, since integers that don't show up fix all those integers, then disjoint cycles commute (they can apply in any order).

Lastly, you can permute (cyclically move) the numbers in any permutation and get the same cycle. Namely:

(a_{1} a_{2} \dots a_{m}) = (a_{2} a_{3} \dots a_{m} a_{1}) = \dots

By convention the smallest number is usually written first.

Some notes:

The cycle decomposition is the unique way to express a permutation as a product of disjoint cycles (up to rearranging its cycles and cyclically permuting the numbers within each cycle)
We can use this to show that the order of a permutation is the $lcm$ of the lengths of the cycles in its cycle decomposition