Definition 1.35. Permutations.
A permutation of a set \(S\) is a bijective function \(\sigma:S\to S\text{.}\) The set of all permutations of a set \(S\) is denoted \(\Perm(S)\text{.}\)
Section 1.3 Permutations and Symmetric Groups
“Symmetry is overrated. Overrated is symmetry.”―Larry Wall
Subsection Symmetric Groups
Let’s introduce another very important example: symmetric groups.
Definition 1.36. Symmetric Group \(S_n\).
For any \(n\in\N\text{,}\) the symmetric group is the set \(S_n=\Perm(\{1,\dots,n\})\) equipped with the composition of functions as its binary operation.
Exercise 1.37. Order of \(S_n\).
Prove \(|S_n|=n!\text{.}\)
Subsection Cycles and Transpositions
Definition 1.38. Cycles and Transpositions.
If \(i_1, \dots, i_m\) are distinct integers between \(1\) and \(n\text{,}\) then \(\sigma=(i_1 \, i_2 \, \dots i_m)\) denotes the element of \(S_n\) that satisfies
\begin{equation*}
\sigma(i_1)=i_2, \sigma(i_2)=i_3, \dots, \sigma(i_{m-1})=i_m, \sigma(i_m)=i_1 \text{ and } \sigma(k)=k
\end{equation*}
for \(k\in[n] \setminus \{i_1, \dots, i_m\}\text{.}\) Such a permutation is called a cycle or an \(m\)-cycle if we want to emphasize its length. A \(2\)-cycle is often called a transposition.
Example 1.39. Cycle.
When regarded as an element of \(S_{13}\text{,}\) \((1 \, 3 \, 7)\) sends \(1\) to \(3\text{,}\) \(3\) to \(7\) and \(7\) to \(1\text{,}\) and it fixes \(2,4,5,7,8,9,10,11,12,13\text{.}\) (Note that the value of \(n\) in cycle notation is sometimes ambiguous.)
Remark 1.40.
Note that distinct lists of integers represent the same cycle if they are cyclical rearrangements of each other, e.g., \((1 \, 2 \, 3) = (2 \, 3 \, 1)\text{.}\) However, \((1 \, 2 \, 3) \neq (2 \, 1 \, 3)\text{.}\)
We compose cycles the same way we compose functions.
Example 1.41. Composing Cycles.
Consider
\begin{equation*}
(1 \, 3 \, 7) (2 \, 3 \, 5) = (1 \, 3 \, 5 \, 2 \,7).
\end{equation*}
This equation might lead you to the false belief that every element of \(S_n\) is a cycle. This is not true — for example, the product \((1 \, 2) (3 \, 4)\) cannot be written as a single cycle. What is true is that every element of \(S_n\) is uniquely (up to ordering) the product of disjoint cycles. We’ll prove that soon in Theorem 1.44.
Proposition 1.42. Disjoint Commutes.
Disjoint cycles commute, that is, if \(i_1 , i_2 \, \dots i_m, j_1 , j_2 \, \dots j_k\in [n]\text{,}\)
\begin{equation*}
\sigma_1=(i_1 \, i_2 \, \dots i_m), \quad \sigma_2=(j_1 \, j_2 \, \dots j_k)
\end{equation*}
and
\begin{equation*}
\{i_1 , i_2 , \dots i_m\}\cap \{j_1 , j_2 , \dots j_k\}=\emptyset
\end{equation*}
then \(\sigma_1 \circ \sigma_2=\sigma_2\circ \sigma_1\text{.}\)
Proof.
Let’s consider two disjoint cycles, denoted as \((a_1\;a_2\;\cdots\;a_m)\) and \((b_1\;b_2\dots\;b_n)\text{,}\) where \(a_i\)’s and \(b_i\)’s are distinct elements. Let’s analyze the composition \((a_1\;a_2\;\cdots\;a_m) \circ (b_1\;b_2\dots\;b_n)\text{:}\) When we apply the composition to an element \(ai\text{,}\) we have:
\begin{align*}
(a_1\;a_2\;\cdots\;a_m) \circ (b_1\;b_2\dots\;b_n)(a_i) &= (a_1\;a_2\;\cdots\;a_m)(b_1\;b_2\dots\;b_n(a_i))\\
&= (a_1\;a_2\;\cdots\;a_m)(a_i)\\
&= a_{i+1} (\text{ if } a_i \neq a_m) \text{ or }a_1 (\text{ if }a_i = a_m)
\end{align*}
Similarly, when we apply the composition to an element \(b_j\text{,}\) we have:
\begin{align*}
(b_1\;b_2\dots\;b_n) \circ (a_1\;a_2\;\cdots\;a_m)(b_j) &= (b_1\;b_2\dots\;b_n)(a_1\;a_2\;\cdots\;a_m(b_j))\\
&= (b_1\;b_2\dots\;b_n)(b_j)\\
&= b_{j+1} (\text{ if } b_j \neq b_n) \text{ or }b_1 (\text{ if } b_j = b_n)
\end{align*}
From these calculations, we can observe that the composition \((a_1\;a_2\;\cdots\;a_m) \circ (b_1\;b_2\dots\;b_n)\) maps each element \(a_i\) to \(a_{i+1}\) (if \(a_i \neq a_m\)), and it maps \(a_m\) to \(a_1\text{.}\) Similarly, the composition \((b_1\;b_2\dots\;b_n) \circ (a_1\;a_2\;\cdots\;a_m)\) maps each element \(b_j\) to \(b_{j+1}\) (if \(b_j \neq b_n\)), and it maps \(b_n\) to \(b_1\text{.}\)
Now, let’s consider the composition \((b_1\;b_2\dots\;b_n) \circ (a_1\;a_2\;\cdots\;a_m)\) and evaluate its effect on the elements \(a_i\) and \(a_m\text{:}\)
\begin{align*}
(b_1\;b_2\dots\;b_n) \circ (a_1\;a_2\;\cdots\;a_m)(a_i) &= (b_1\;b_2\dots\;b_n)(a_1\;a_2\;\cdots\;a_m(a_i))\\
&= (b_1\;b_2\dots\;b_n)(a_i)\\
&= a_{i+1} (\text{ if } a_i \neq a_m) \text{ or } a_1 (\text{ if } a_i = a_m)
\end{align*}
and
\begin{align*}
(b_1\;b_2\dots\;b_n) \circ (a_1\;a_2\;\cdots\;a_m)(a_m) &= (b_1\;b_2\dots\;b_n)(a_1\;a_2\;\cdots\;a_m(a_m))\\
&= (b_1\;b_2\dots\;b_n)(a_1\;a_2\;\cdots\;a_m)\\
&= a_{m+1} (\text{ if } a_m \neq a_1) \text{ or } a_2 (\text{ if } a_m = a_1)
\end{align*}
Comparing these results with the previous composition, we see that the effects on \(a_i\) and \(a_m\) are the same in both compositions. This implies that the compositions \((a_1\;a_2\;\cdots\;a_m) \circ (b_1\;b_2\dots\;b_n)\) and \((b_1\;b_2\dots\;b_n) \circ (a_1\;a_2\;\cdots\;a_m)\) are identical.
Therefore, we have shown that disjoint cycles commute, meaning that the order in which they are composed does not affect the final result.
While sufficent, this is not a necessary condition.
Exercise 1.43. Non-Disjoint Commutes.
Find elements \(\s,\tau\in S_n\) that commute but are not disjoint.
Theorem 1.44. Cycle Decompostion.
- Each \(\sigma\in S_n\) can be written as a product (composition) of disjoint cycles, and such a factorization is unique up to the ordering of the factors.
- Each \(\sigma\in S_n\) can be written a product of transpositions.
Remark 1.45.
For the uniqueness part of statement (1) in Theorem 1.44 one needs to establish a convention regarding \(1\)-cycles, that is one needs to stipulate either that the \(1\)-cycles will not be recorded (which gives the shortest such factorization) or that all the \(1\)-cycles will be recorded (which gives the longest such factorization, but also the only one that makes it clear what the number \(n\) is).
Now that we know that every permutation can be written as a product of transpositions, we can utilize this to gain insight into many aspects of the group structure, such as the order of elements.
Proposition 1.46. Permutation Order.
The order of a permutation is the least common multiple of the lengths of the cycles it is a product of. In particular, every transposition is its own inverse and the order of a \(k\)-cycle in \(S_n\) is \(n\text{.}\)
Proof.
Coming soon!
Subsection Even and Odd Permutations
We can also categorize elements of permutation groups by the number of transpositions it is a product of.
Definition 1.47. Even and Odd Permutaitons.
A permutation \(\s\) is even is if is the product of an even number of transpositions, otherwise it is odd.
Proposition 1.48. Even and Odd Properties.
- A \(k\)-cycle is even if and only if \(k\) is odd.
- Products of even permutations are even, products of odd permutations are even, products of even and odd permutations are odd.
- The identity permutation in \(S_n\) is even, but not odd.
- No permutation in \(S_n\) is both even and odd.
Definition 1.49. Alternating Group.
The alternating group \(A_n\) is the subset of all even cycles of \(S_n\text{.}\)
Exercise 1.50. Order of \(A_n\).
Prove \(|A_n|=\frac{n!}{2}\text{.}\)
Summary
- The Dihedral Group is the group of reflections and rotations of a regular polygon. Every element in \(D_{2n}\) can be written as a product of rotations and reflections.
1
See: Example 1.55 and Proposition 1.58. - The Definition 1.36 \(S_n\) is set of all Permutations of a set with \(n\) elements. The order of \(S_n\) is \(n!\text{.}\)
2
See: Exercise 1.37. - Permutations are either even or odd; the Alternating Group is the set of even permutations. The order of \(A_n\) is \(\frac{n!}{2}\text{.}\)
3
See: Exercise 1.50. - Cycles and Transpositions are special permutations. Every cycle can be written as a product of transpositions.
4
See: Theorem 1.44, though we don’t have the tools to prove this explicitly just yet.
