C4 - properties

permutation of disjoint cycles

every permutation is a product of disjoint cycles

let $α$ be a permutation on $A = {1, 2, \dots, n}$ , and $a_{2} = α (a_{1})$ , $a_{3} = α (α (a_{1})) = α^{2} (a_{2})$ and so on until $a_{1} = α^{m} (a_{1})$ , where $a_{i} \in A$
such an $m$ exists as the sequence must be finite, and there must eventually be a repitition
suppose $α^{i} (a_{1}) = α^{j} (a_{1})$ for some $i$ and $j$ such that $i < j$ , then $a_{1} = α^{m} (a_{1})$ , where $m = j - 1$
this relationship can be expressed as:

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

note that the cycle of $a_{1}$ to $a_{m}$ may not have exhausted the set $A$ , and a new cycle can be created similarly:

α = (a_{1} a_{2} \dots a_{m}) (b_{1} b_{2} \dots b_{k}) \dots (c_{1} c_{2} \dots c_{s})

note that every new cycle will not share any elements in common with the previous cycles
eg:

\begin{matrix} [\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 1 & 2 & 9 & 8 & 5 & 3 & 6 & 4 \end{matrix}] \\ = (\begin{matrix} 1 & 7 & 3 & 2 \end{matrix}) (\begin{matrix} 4 & 9 \end{matrix}) (\begin{matrix} 5 & 8 & 6 \end{matrix}) \end{matrix}

disjoint cycles commute

let $α = {a_{1}, a_{2}, \dots a_{r}} \in S_{n}$ and $β = {b_{1}, b_{2}, \dots b_{k}} \in S_{n}$ such that $α \cap β = Φ$ , then $α β = β α$

considering $S = {a_{1} a_{2} \dots a_{m} b_{1} b_{2} \dots b_{n} c_{1} c_{2} \dots c_{k}}$ with permutations $α$ and $β$ , defined as above
since $β$ fixes all $a$ 's:

\begin{matrix} β α (a_{i}) = β (α (a_{i})) = β (a_{i + 1}) = a_{i + 1} \\ α β (a_{1}) = α (β (a_{i})) = α (a_{i}) = a_{i + 1} \end{matrix}

since both fix all $c$ 's:

\begin{matrix} β α (c_{i}) = β (α (c_{i})) = β (c_{i}) = c_{i} \\ α β (c_{1}) = α (β (c_{i})) = α (c_{i}) = c_{i} \end{matrix}

order of permutation

let $α \in S_{n}$ ,then $| α | =$ LCM of the length of disjoint cycles

consider $(\begin{matrix} a & b & c \end{matrix}) (\begin{matrix} d & e \end{matrix}) (\begin{matrix} f \end{matrix})$ , so LCM of disjoint cycles is $6$
$α^{3 m} = ϵ$ and $β^{2 n} = ϵ$ , which happens for $m = 2$ and $n = 3$ , ie. they both need to be raised to the power of $6$

product of 2-cycles

every permutation in $S_{n}$ , $n > 1$ , is a product of 2-cycles