More Finite Groups - MATH-CS COMPASS

Group of Integers Modulo $n$

In Intro to Abstract Algebra, we established the foundational group axioms and core structural concepts like Abelian groups and subgroups. In this page, we pivot from general concepts to specific examples of finite groups, which are crucial building blocks of abstract algebra.

We start with a fundamental finite cyclic group. (By the way, every cyclic group is Abelian. You can check this fact from definition of cyclic groups and Abelian groups. The key is commutativity: $a^m a^n = a^{m+n} = a^{n+m} = a^n a^m$. Note that the converse of this statement is NOT true.)

Group of Integers Modulo $n$: The set \[ \mathbb{Z}_n = \{0, 1, \cdots, n-2, n-1\}, \, (n \geq 1) \] is a finite cyclic group under addition modulo $n$. For any $k > 0$ in $\mathbb{Z}_n$, the inverse of the element $k$ is $n - k$. The identity is $0$.

For example, consider: \[ \mathbb{Z}_8 = \{0, 1, 2, 3, 4, 5, 6, 7\}. \]

$1$ (Generator):

$3$ (Generator):

$5$ (Generator):

$7$ (Generator):

Thus, $1, 3, 5, \text{ and } 7$ are generators of (\mathbb{Z}_8 \): \[ \mathbb{Z}_8 = \langle 1 \rangle = \langle 3 \rangle = \langle 5 \rangle = \langle 7 \rangle, \] whereas $2, 4, \text{ and } 6$ are not generators of $\mathbb{Z}_8 $. For instance, \[ \langle 2 \rangle = \{2, 2+2, 4+2, 6+2\} (\bmod 8) \] Thus, we have: \[ \langle 2 \rangle = \{2, 4, 6, 0\} \neq \mathbb{Z}_8. \]

In general, the element $n-1$ is a generator of $\mathbb{Z}_n $ because it is the unique additive inverse of the generator $1$. Remember that in abstract additive notation, the inverse of $1$ is written as $-1$. Working in $\mathbb{Z}_n$, we define the notation: \[ \mathbf{-1} = \mathbf{n-1} \pmod n. \] Thus, for $\mathbb{Z}_8 $, the two guaranteed generators are $1$ and $7$.

Indeed, the inverse of any generator of $\mathbb{Z}_n$ is also always a generator. This fact is supported by the full classification theorem for generators of $\mathbb{Z}_n$:

Theorem 1: Generators of $\mathbb{Z}_n$ An integer $k \in \mathbb{Z}_n$ is a generator of $\mathbb{Z}_n$ if and only if $k$ and $n$ are relatively prime: \[ \gcd (n, k) = 1. \]

This fact comes from more general settings. First, we introduce the following theorem:

Theorem 2: Let $a$ be an element of order $n$ in a group, and let $k$ be a positive integer. Then \[ \langle a^k \rangle = \langle a^{\gcd(n, k)} \rangle \] and \[ |a^k| = \frac{n}{\gcd(n, k)}. \]

Proof:

Let $k = \gcd(n, k) \cdot r$. Since $a^k = (a^{\gcd(n, k)})^r$, we have: \[ \langle a^k \rangle \subseteq \langle a^{\gcd(n, k)} \rangle. \] There are integers $s$ and $t$ such that \[ \gcd(n, k) = ns + kt \] since the greatest common divisor is a linear combination of two integers.
Thus, we can rewrite $a^{\gcd(n, k)}$ as following: \[ \begin{align*} a^{\gcd(n, k)} &= a^{ns+kt} \\\\ &= (a^n)^s (a^k)^t \\\\ &= e (a^k)^t \\\\ &= (a^k)^t \in \langle a^k \rangle. \end{align*} \] This implies \[ \langle a^{\gcd(n, k)} \rangle \subseteq \langle a^k \rangle. \] Therefore, we conclude that \[ \langle a^k \rangle = \langle a^{\gcd(n, k)} \rangle. \] For the second part of the theorem, it is clear that \[ (a^{\gcd(n, k)})^{\frac{n}{\gcd(n, k)}} = a^n = e. \] So, \[ |a^{\gcd(n, k)}| \leq \frac{n}{\gcd(n, k)}. \] Now, consider any positive integer $i < \frac{n}{\gcd(n, k)}$. Then the exponent $\gcd(n, k) i < n$. Since $|a| = n$, the identity $e$ cannot be generated by any positive power of $a$ strictly less than $n$. Therefore, \[ (a^{\gcd(n, k)})^i \neq e \] Thus, the smallest positive power to yield the identity $e$ is exactly $\frac{n}{\gcd(n, k)}$: \[ \begin{align*} |a^k| &= |\langle a^k \rangle| \\\\ &= |\langle a^{\gcd(n, k)} \rangle| \\\\ &= | a^{\gcd(n, k)} | \\\\ &= \frac{n}{\gcd(n, k)}. \end{align*} \]

Subgroups of Cyclic Groups

Suppose a cyclic group $G = \langle a \rangle$ has order 30. Then we can find subgroups of $G$ as follows: \[ \begin{align*} &\langle a^{30} \rangle = \{e\} \\\\ &\langle a^{15} \rangle = \{e, a^{15}\} \\\\ &\langle a^{10} \rangle = \{e, a^{10}, a^{20}\} \\\\ &\langle a^6 \rangle = \{e, a^6, a^{12}, a^{18}, a^{24} \} \\\\ &\langle a^5 \rangle = \{e, a^5, a^{10}, a^{15}, a^{20}, a^{25}\} \\\\ &\langle a^3 \rangle = \{e, a^3, a^6, \cdots, a^{27}\} \\\\ &\langle a^2 \rangle = \{e, a^2, a^4, \cdots, a^{28}\} \\\\ &\langle a^1 \rangle = \{e, a, a^2, \cdots, a^{29}\} \end{align*} \]

Theorem 3: Fundamental Theorem of Cyclic Groups Let $G = \langle a \rangle$ be a cyclic group of order $n$.

Every subgroup of $G$ is cyclic. Moreover, the order of any subgroup of $G$ is a divisor of $n$.
For each positive divisor $k$ of $n$, the group $G$ has exactly one subgroup of order $k$, namely $\langle a^{n/k} \rangle$.

Proof:

Part 1:

Let $H$ be a subgroup of $G = \langle a \rangle$. If $H = \{e\}$, then $H$ is cyclic.
Now assume $H \neq \{e\}$. We first show that $H$ contains an element of the form $a^t$ for some positive integer $t$. Since $G = \langle a \rangle$, every element of $H$ has the form $a^t$. When $a^t$ belongs to $H$ with $t < 0$, then $a^{-t}$ belongs to $H$ also and $-t$ is positive. Thus, our claim is verified.
Now let $m$ be the least positive integer such that $a^m \in H$. By closure, $\langle a^m \rangle \subseteq H$.

Next, we claim that $H = \langle a^m \rangle$. Let $b$ be any element in $H$. Since $b \in G$, we have $b = a^k$ for some integer $k$. By the Division Algorithm, we can write $k = mq + r$ where $0 \leq r < m$. Then: \[ a^k = a^{mq+r} = a^{mq}a^r \implies a^r = a^{-mq}a^k. \] Since $a^k \in H$ and $a^{-mq} = (a^m)^{-q} \in H$, it follows that $a^r \in H$. However, $m$ is the least positive integer such that $a^m \in H$ and $0 \leq r < m$. Thus, $r$ must be $0$. Therefore, \[ b = a^k = a^{mq} = (a^m)^q \in \langle a^m \rangle. \] This implies every element in $H$ is generated by $a^m$, and hence $H = \langle a^m \rangle$. Therefore, every subgroup of a cyclic group is cyclic.

Part 2:

Let $H$ be any subgroup of $G = \langle a \rangle$, where $|G| = n$. From Part 1, $H = \langle a^m \rangle$, where $m$ is the least positive integer such that $a^m \in H$. By Theorem 2, $a^{\gcd(m, n)} \in \langle a^m \rangle = H$. Since $\gcd(m,n) \leq m$ and $m$ is minimal, we have $m = \gcd(n,m)$, hence $m$ divides $n$. Therefore, \[ |H| = |a^m| = \frac{n}{m}, \] which divides $n$. This proves that the order of any subgroup of $G$ is a divisor of $n$.

Now let $k$ be any positive divisor of $n$. Then $\langle a^{n/k} \rangle$ is a subgroup of order \[ |\langle a^{n/k} \rangle | = \frac{n}{\gcd(n, n/k)} = \frac{n}{n/k} = k. \] Suppose $K$ is any subgroup of $\langle a \rangle$ of order $k$. Then $K$ has the form $\langle a^s \rangle$, where $s$ divides $n$ and \[ |K| = \frac{n}{s} = k \implies s = \frac{n}{k}. \] Thus, $K = \langle a^{n/k} \rangle$.

Euler Phi Function

Using Theorem 2 and Theorem 3, we are able to count the number of elements of each order in a finite cyclic group. Here, we introduce a number-theoretic function for convenience.

For instance, to find the number of generators of a cyclic group of order $n$, we need to count how many integers $k$ satisfy $\gcd(k, n) = 1$. This count is provided by the Euler Phi Function.

Euler Phi Function $\phi(n)$: Let $\phi (1) = 1$, and for any integer $n > 1$, let $\phi (n)$ denote the number of positive integers less than $n$ and relatively prime to $n$.

Theorem 4: Number of Elements of Each Order in a Cyclic Group If $d$ is a positive divisor of $n$, the number of elements of order $d$ in a cyclic group of order $n$ is $\phi (d)$.

Corollary: Number of Generators of a Cyclic Group The number of generators of a cyclic group of order $n$ is $\phi(n)$.

Corollary: Number of Elements of Order $d$ in a Finite Group In a finite group, the number of elements of order $d$ is a multiple of $\phi (d)$.

Permutation Groups

Here, we introduce a family of non-Abelian groups, namely permutation groups. Remember, a permutation of a set $A$ is a function from $A$ to itself that is a bijective function (one-to-one and onto). For example, consider a set $A = \{1, 2, 3\}$. A permutation of $A$ is essentially an ordered arrangement of its elements. So, the total number of permutations for $A$ is given by the factorial $3! = 3 \cdot 2 \cdot 1 = 6$.

Permutation Groups: A permutation group of a set $A$ is a set of permutations of $A$ that forms a group under function composition.

For example, the permutation group of $A = \{1, 2, 3\}$ is the set of all one-to-one functions from $\{1, 2, 3\}$ to itself.

To represent these permutations explicitly, we use the two-row matrix notation. In this format, the elements of the set $A$ are listed in the top row, and directly below each element is its image (where it is mapped to) under the permutation.

For a permutation $\sigma$ on a set of $n$ elements, the notation is structured as follows: \[ \sigma = \begin{bmatrix} i_{1} & i_{2} & \cdots & i_{n} \\\\ \sigma(i_{1}) & \sigma(i_{2}) & \cdots & \sigma(i_{n}) \end{bmatrix} \] This means the element $i_k$ in the top row maps to the element $\sigma(i_k)$ directly beneath it.

The elements of $S_3$ are expressed using this notation as follows: \[ \begin{align*} \epsilon &= \begin{bmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{bmatrix} , \quad \alpha = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{bmatrix}, \\\\ \alpha^2 &= \begin{bmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{bmatrix} , \quad \beta = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{bmatrix}, \\\\ \alpha \beta &= \begin{bmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{bmatrix} , \quad \alpha^2 \beta = \begin{bmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{bmatrix}. \end{align*} \] This group is called the symmetric group of degree $3$ and is denoted by $S_3$. The order of this group is given by $|S_3| = 3! = 6.$ In general, we define the symmetric group as follows:

Symmetric Groups: Let $A = \{1, 2, \cdots, n-1, n\}$. The set of all permutations of $A$ is called the symmetric group of degree $n$ and is denoted by $S_n$. Elements of this group are written by: \[ \alpha = \begin{bmatrix} 1 & 2 & \cdots & n-1 & n \\ \alpha(1) & \alpha(2) & \cdots & \alpha(n-1) & \alpha(n) \end{bmatrix}. \] $S_n$ has the $n \cdot (n-1) \cdots 3 \cdot 2 \cdot 1 = n!$ elements.

While the two-row matrix notation is explicit, it becomes cumbersome for composition and order calculation. For practical use, we employ the more compact and functional cycle notation.

Cycle Notation: A permutation $\alpha$ that maps $i_1 \to i_2 \to \cdots \to i_k \to i_1$, and leaves all other elements fixed, is written as the $\mathbf{k}$-cycle $\left(i_{1}\, i_{2}\, \ldots\, i_{k}\right)$. Elements that are fixed (map to themselves) are usually omitted, unless they are the only element, in which case the identity element is represented by $(1)$ or $\epsilon$.

Let's list all elements of $S_3$ again using cycle notation. We compute them by tracking where each element $1, 2, 3$ maps to.

1. Identity and Rotations (Subgroup of order 3): \[ \begin{align*} \epsilon &= \begin{bmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{bmatrix} = (1) \\\\ \alpha &= \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{bmatrix} = (1\, 2\, 3) \quad (\text{since } 1\to 2\to 3\to 1) \\\\ \alpha^2 &= \begin{bmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{bmatrix} = (1\, 3\, 2) \quad (\text{since } 1\to 3\to 2\to 1) \end{align*} \]

2. Reflections (Transpositions): To find the cycle notation for products like $\beta$, $\alpha\beta$, and $\alpha^2\beta$, we perform the composition. Remember, composition works from right to left.

For $\beta$ (swaps 2 and 3, fixes 1): \[ \beta = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{bmatrix} = (2\, 3) \]

For $\alpha\beta$ (Compose $\beta$ then $\alpha$):
1. Start with $1$: $\beta(1)=1$, then $\alpha(1)=2$. Total: $1 \to 2$.
2. Next with $2$: $\beta(2)=3$, then $\alpha(3)=1$. Total: $2 \to 1$. (Cycle closes: $(1\, 2)$)
3. Check $3$: $\beta(3)=2$, then $\alpha(2)=3$. Total: $3 \to 3$. (Fixed) \[ \alpha\beta = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{bmatrix} = (1\, 2) \]

For $\alpha^2\beta$ (Compose $\beta$ then $\alpha^2$):
1. Start with $1$: $\beta(1)=1$, then $\alpha^2(1)=3$. Total: $1 \to 3$.
2. Next with $3$: $\beta(3)=2$, then $\alpha^2(2)=1$. Total: $3 \to 1$. (Cycle closes: $(1\, 3)$)
3. Check $2$: $\beta(2)=3$, then $\alpha^2(3)=2$. Total: $2 \to 2$. (Fixed) \[ \alpha^2\beta = \begin{bmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{bmatrix} = (1\, 3) \]

Permutation Properties

To efficiently calculate the order of a permutation and to simplify complex compositions, it is essential to master the properties of cycle decomposition. This section focuses on the structural theorems that allow us to uniquely represent any permutation and analyze its properties.

Two cycles $(i_1\, i_2\, \ldots \, i_k)$ and $(j_1\, j_2\, \ldots\, j_m)$ are disjoint if they have no numbers in common. That is, the sets $\{i_1, \ldots, i_k\}$ and $\{j_1, \ldots, j_m\}$ are mutually exclusive.

Theorem 5: Products of Disjoint Cycles Every permutation of a finite set can be written as a cycle or as a product of disjoint cycles. Moreover, this decomposition is unique up to the order of the factors.

Theorem 6: Disjoint Cycles Commute If the pair of cycles $\alpha = (a_1 \, a_2 \, \ldots \, a_m) $ and $\beta = (b_1 \, b_2 \, \ldots \, b_n) $ have no entries in common, then $\alpha \beta = \beta \alpha$.

Proof:

Let $S$ be the finite set on which $\alpha$ and $\beta$ act. Since the cycles are disjoint, the set $S$ can be partitioned into three mutually exclusive and exhaustive subsets:

$A = \{a_1, a_2, \ldots, a_m\}$, the set of elements moved by $\alpha$.
$B = \{b_1, b_2, \ldots, b_n\}$, the set of elements moved by $\beta$.
$C = \{ c_1, c_2, \ldots, c_k\}$, the set of all other elements in $S$ (fixed by both $\alpha$ and $\beta$).

To prove that the permutations are equal, we must show that the result of applying the compositions $\alpha \beta$ and $\beta \alpha$ is identical: \[ \forall x \in S, \, (\alpha \beta)(x) = (\beta \alpha)(x). \]

Case 1: $x \in A$ (The element is moved by $\alpha$)

Since $A$ and $B$ are disjoint, $\beta$ must fix every element in $A$. Thus, $\beta(x) = x$.
For the composition $\alpha \beta$: \[ (\alpha \beta)(x) = \alpha(\beta (x)) = \alpha(x). \] Since $x \in A$, $\alpha(x)$ is also in $A$. Because $A$ and $B$ are disjoint, $\beta$ fixes $\alpha(x)$.
For the composition $\beta \alpha$: \[ (\beta \alpha)(x) = \beta (\alpha (x)) = \alpha (x). \] Thus, for $x \in A$, $(\alpha \beta)(x) = \alpha(x) = (\beta \alpha)(x)$.

Case 2: $x \in B$ (The element is moved by $\beta$)

Since $B$ and $A$ are disjoint, $\alpha$ must fix every element in $B$. Thus, $\alpha(x) = x$.
For the composition $\alpha \beta$: \[ (\alpha \beta)(x) = \alpha(\beta (x)). \] Since $x \in B$, $\beta(x) \in B$. Because $B$ and $A$ are disjoint, $\alpha$ fixes $\beta(x)$. Therefore, \[ (\alpha \beta)(x) = \beta (x). \] For the composition $\beta \alpha$: \[ (\beta \alpha)(x) = \beta (\alpha (x)) = \beta (x), \] since $\alpha(x) = x$. Thus, for $x \in B$, $(\alpha \beta)(x) = \beta(x) = (\beta \alpha)(x)$.

Case 3: $x \in C$ (The element is fixed by both $\alpha$ and $\beta$)

By the definition of the set $C$, we have $\alpha(x) = x$ and $\beta(x) = x$.
For the composition $\alpha \beta$: \[ (\alpha \beta)(x) = \alpha(\beta (x)) = \alpha(x) = x. \] For the composition $\beta \alpha$: \[ (\beta \alpha)(x) = \beta (\alpha (x)) = \beta (x) = x. \] Thus, for $x \in C$, $(\alpha \beta)(x) = x = (\beta \alpha)(x)$.

Since the result of the two compositions is the same across all three exhaustive subsets, we conclude that $\alpha \beta = \beta \alpha$.

Theorem 7: Order of a Permutation The order of a permutation of a finite set is the least common multiple (LCM) of the lengths of its disjoint cycles.

Proof:

Let $\alpha$ be a permutation and its disjoint cycle decomposition be: \[ \alpha = \beta_1 \beta_2 \ldots \beta_r \] where $\beta_i$ is a cycle of length $k_i$. We recall that the order of a $k_i$-cycle is $|\beta_i| = k_i$. We must show that $|\alpha| = \text{lcm}(k_1, k_2, \ldots, k_r) = m$.

Step 1: Show that $\alpha^m = \epsilon$

Since the cycles $\beta_i$ are disjoint, they commute with each other (by Theorem 6). Therefore, for any positive integer $t$: \[ \alpha^t = (\beta_1 \beta_2 \ldots \beta_r)^t = \beta_1^t \beta_2^t \ldots \beta_r^t. \] By the definition of the least common multiple, $m$ is a multiple of each $k_i$. Since $|\beta_i| = k_i$, we have $\beta_i^m = \epsilon$ for every $i$. It follows that: \[ \alpha^m = \epsilon \cdot \epsilon \cdots \epsilon = \epsilon. \] By the properties of group element orders, this implies that the order $|\alpha|$ must divide $m$, and thus $|\alpha| \leq m$.

Step 2: Show that $m$ is the smallest such positive integer

Suppose $\alpha^t = \epsilon$ for some positive integer $t$. This means: \[ \beta_1^t \beta_2^t \cdots \beta_r^t = \epsilon. \] Since the cycles are disjoint, each $\beta_i$ moves a disjoint set of elements. For any element $x$ moved by the cycle $\beta_i$, the other cycles $\beta_j$ ($j \neq i$) fix $x$. Applying the permutation to such an $x$, we get: \[ \alpha^t(x) = \beta_i^t(x) = x. \] Since this holds for all $x$ in the support of $\beta_i$, we must have $\beta_i^t = \epsilon$. From the properties of cyclic groups, $\beta_i^t = \epsilon$ implies that the order $k_i$ divides $t$. Because this must hold for every $i \in \{1, \ldots, r\}$, $t$ must be a common multiple of all cycle lengths $k_1, \ldots, k_r$. By definition, the least common multiple $m$ is the smallest such integer. Thus, $t \geq m$.

We conclude that $|\alpha| = m = \text{lcm}(k_1, k_2, \ldots, k_r)$.

For example, consider the permutation $\alpha \in S_5$ defined in two-row notation as:

\[ \alpha = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{bmatrix} \]

Decomposition into Disjoint Cycles (Theorem 5):
We trace the elements: $1 \to 2 \to 3 \to 1$ (a 3-cycle) and $4 \to 5 \to 4$ (a 2-cycle). The disjoint cycle factorization is: \[ \alpha = (1\, 2\, 3)(4\, 5) \] This factorization is unique up to the order of the disjoint cycles (e.g., $(4\, 5)(1\, 2\, 3)$).
Order of the Permutation (Theorem 7):
The cycle lengths are $3$ for $(1\, 2\, 3)$and $2$ for $(4\, 5)$. The order of $\alpha$ is the Least Common Multiple (LCM) of the cycle lengths: \[ |\alpha| = \text{lcm}(3, 2) = 6. \] This means $\alpha$ must be composed with itself 6 times to return to the identity: $\alpha^6 = \epsilon$.

Theorem 8: Product of 2-Cycles Every permutation in $S_n, \, n > 1$, is a product of 2-cycles.

Proof:

Since every permutation can be written as a product of disjoint cycles (Theorem 5), it suffices to show that every cycle can be written as a product of 2-cycles (transpositions).

Consider an arbitrary $k$-cycle: $\sigma = (i_1\, i_2\, \ldots\, i_k)$. We claim that: \[ (i_1\, i_2\, \ldots\, i_k) = (i_1\, i_k)(i_1\, i_{k-1}) \cdots (i_1\, i_3)(i_1\, i_2) \] where the product of $k-1$ transpositions is evaluated from right to left.

Let $\tau$ denote the product on the right-hand side. We verify that $\sigma$ and $\tau$ agree on all elements.

For $i_1$:
The rightmost transposition $(i_1\, i_2)$ sends $i_1 \mapsto i_2$. Each subsequent transposition $(i_1\, i_m)$ for $m = 3, \ldots, k$ fixes $i_2$ (since $i_2 \neq i_1$ and $i_2 \neq i_m$). Thus $\tau(i_1) = i_2 = \sigma(i_1)$.
For $i_j$ where $2 \leq j \leq k-1$:
Reading right to left: the transpositions $(i_1\, i_2), (i_1\, i_3), \ldots, (i_1\, i_{j-1})$ all fix $i_j$. The transposition $(i_1\, i_j)$ sends $i_j \mapsto i_1$. The next transposition $(i_1\, i_{j+1})$ sends $i_1 \mapsto i_{j+1}$. The remaining transpositions $(i_1\, i_{j+2}), \ldots, (i_1\, i_k)$ all fix $i_{j+1}$. Thus $\tau(i_j) = i_{j+1} = \sigma(i_j)$.
For $i_k$:
Reading right to left: the transpositions $(i_1\, i_2), (i_1\, i_3), \ldots, (i_1\, i_{k-1})$ all fix $i_k$. The leftmost transposition $(i_1\, i_k)$ sends $i_k \mapsto i_1$. Thus $\tau(i_k) = i_1 = \sigma(i_k)$.
For any $x \notin \{i_1, \ldots, i_k\}$:
Every transposition $(i_1\, i_m)$ fixes $x$, so $\tau(x) = x = \sigma(x)$.

Since $\sigma$ and $\tau$ agree on all elements of $\{1, 2, \ldots, n\}$, we have $\sigma = \tau$. Therefore, every cycle is a product of transpositions. Since every permutation is a product of disjoint cycles, every permutation in $S_n$ is a product of transpositions.

Following Theorem 8, we can decompose our $\alpha \in S_5$ into the product of 2-cycles as follows: \[ \begin{align*} \alpha &= \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{bmatrix} \\\\ &= (1\, 2\, 3)(4\, 5) \\\\ &= (1\, 3)(1\, 2)(4\, 5). \end{align*} \]

Alternating Groups

Every permutation can be uniquely factored into a product of disjoint cycles, and subsequently, decomposed into a product of 2-cycles (transpositions). This decomposition, though NOT unique in the specific transpositions used, leads us to the concept of permutation parity. A key theorem guarantees the invariance of this property: the number of 2-cycles in any factorization of a given permutation will always be consistently even or consistently odd. This fundamental distinction establishes the alternating Group ($A_n$) as a crucial normal subgroup of the symmetric Group ($S_n$), which plays an important role in Galois theory and the determination of the solvability of polynomial equations.

Lemma: The Identity is Even If the identity $\epsilon = \beta_1 \beta_2 \cdots \beta_r$, where each $\beta_i$ is a 2-cycle, then $r$ must be an even number.

Proof (Sketch):

Suppose for contradiction that $r$ is odd. Since a single 2-cycle cannot be the identity, $r > 1$. Let $a$ be a symbol appearing in the 2-cycles. We focus on the rightmost 2-cycle that contains $a$. Let this be $\beta_i$.

We examine the pair $\beta_{i-1}\beta_i$. There are four possible configurations for these two adjacent transpositions (where $a, b, c, d$ are distinct):

$(a\,b)(a\,b) = \epsilon$ → These cycles cancel, reducing the total count $r$ by 2.
$(a\,c)(a\,b) = (a\,b)(b\,c)$ → This moves the symbol $a$ one position to the left.
$(b\,c)(a\,b) = (a\,c)(b\,c)$ → This moves the symbol $a$ one position to the left.
$(c\,d)(a\,b) = (a\,b)(c\,d)$ → Since they are disjoint, they commute, moving $a$ to the left.

By repeatedly applying this "shift-and-reduce" algorithm, we must eventually reduce the count $r$ by 2. If we started with an odd number, we would eventually be left with a single 2-cycle ($r=1$) equaling the identity: \[ (a\,b) = \epsilon \] However, this is impossible because a transposition moves two elements (swaps $a$ and $b$), whereas the identity permutation fixes all elements. Thus, our initial assumption that $r$ is odd must be false. We conclude that $r$ is even.

Theorem 9: The Parity Theorem (Always Even or Always Odd) If a permutation $\alpha$ can be expressed as a product of an even (odd) number of 2-cycles, then every decomposition of $\alpha$ into a product of 2-cycles must have an even (odd) number of 2-cycles.

In symbols, if \[ \alpha = \beta_1 \beta_2 \cdots \beta_r \text{ and } \alpha = \gamma_1 \gamma_2 \cdots \gamma_s \] where $\beta$'s and $\gamma$'s are 2-cycles, then $r$ and $s$ are both even or both odd.

Proof:

Suppose that a permutation $\alpha$ has two different decompositions into 2-cycles: \[ \alpha = \beta_1 \beta_2 \cdots \beta_r \quad \text{and} \quad \alpha = \gamma_1 \gamma_2 \cdots \gamma_s \] We want to show that $r$ and $s$ must have the same parity. Equating the two expressions: \[ \beta_1 \beta_2 \cdots \beta_r = \gamma_1 \gamma_2 \cdots \gamma_s \] Since every 2-cycle is its own inverse, we multiply both sides by $\beta_r \cdots \beta_1$ to isolate the identity: \[ \epsilon = \gamma_1 \gamma_2 \cdots \gamma_s \beta_r \cdots \beta_1 \] The identity is now expressed as a product of $s + r$ transpositions. By the Lemma above, the total number of transpositions $s + r$ must be even.

Note that if $s+r$ is even, then $s$ and $r$ must be both even or both odd. This confirms that the parity of $\alpha$ is well-defined and consistent across any possible decomposition.

Even and Odd Permutations: A permutation that can be expressed as a product of an even number of 2-cycles is called an even permutation. A permutation that can be expressed as a product of an odd number of 2-cycles is called an odd permutation.

Alternating Group of Degree $n$: The alternating group of degree $n$, denoted $A_n$, is the set of all even permutations in $S_n$.

Theorem 10: $|A_n|$ For $n > 1$, \[ |A_n| = \frac{|S_n|}{2} = \frac{n!}{2}. \]

To determine the parity (even or odd) of a permutation, we decompose it into 2-cycles (transpositions) and count them.

Odd Permutation ($\alpha$ in $S_5$):
The permutation $\alpha = (1\, 2\, 3)(4\, 5)$ is decomposed as: \[ \alpha = (1\, 3)(1\, 2)(4\, 5) \] This is a product of $r = 3$ two-cycles. Since $3$ is an odd number, $\alpha$ is an odd permutation.
Even Permutation ($\gamma$ in $S_5$):
Consider the 3-cycle $\gamma = (1\, 2\, 3)$. It is decomposed as: \[ \gamma = (1\, 3)(1\, 2) \] This is a product of $r = 2$ two-cycles. Since $2$ is an even number, $\gamma$ is an even permutation. (Note: Any cycle of odd length is an even permutation.)
Order of the Alternating Group $A_4$ (Theorem 10):
The symmetric group $S_4$ has $|S_4| = 4! = 24$ elements. The alternating group $A_4$ (the set of all even permutations in $S_4$) has order: \[ |A_4| = \frac{|S_4|}{2} = \frac{24}{2} = 12 \]

Linear Algebra to Algebraic Foundations

Group of Integers Modulo \(n\)

Subgroups of Cyclic Groups

Euler Phi Function

Permutation Groups

Permutation Properties

Alternating Groups