The Language of Symmetry

In many ways, group theory gives language to symmetries. And the most symmetric idea we have yet is, uncreatively, the symmetric group.

Definition 1. For any set $K$ , define the symmetric group on $K$ by

$\mathrm{Sym}(K) := \{f \in \mathcal F(K, K) : f\ \text{is bijective}\}.$

In the context of linear algebra, for any finite-dimensional vector space $V$ ,

$\mathrm{Sym}(V) \cong \mathrm{Sym}(\mathbb R^{\dim(V)}).$

Theorem 1. For any set $K$ , $\mathrm{Sym}(K)$ forms a group under function composition.

Proof. For any $f, g \in \mathrm{Sym}(K)$ , $g \circ f : K \to K$ is bijective, so that $g \circ f \in \mathrm{Sym}(K)$ , so that composition yields a well-defined binary operation. Associativity holds for function composition, the identity element is given by $\mathrm{id}_K$ , and the inverse of $f$ is the inverse function $f^{-1}$ .

For any $n \geq 1$ , define $\mathcal S_n := \mathrm{Sym}(\{1,\dots, n\})$ .

Lemma 1. Given distinct $x_i$ , $\mathrm{Sym}(\{x_1,\dots, x_n\}) \cong \mathcal S_n$ .

Proof. For any $f \in \mathcal S_n$ , define $\Phi_f \in \mathrm{Sym}(\{x_1,\dots, x_n\})$ by

$\Phi_f(x_i) = x_{f(i)}.$

We claim that the map $\Phi : \mathcal S_n \to \mathrm{Sym}(\{x_1,\dots, x_n\})$ defined by $\Phi(f) = \Phi_f$ is bijective.

For injectivity, suppose $\Phi(f_1) = \Phi(f_2)$ . Then for any $x_i$ ,

$x_{f_1(i)} = \Phi_{f_1}(x_i) = \Phi_{f_2}(x_i) = x_{f_2(i)}.$

Since the $x_j$ terms are distinct, $f_1(i) = f_2(i)$ . Since this equation holds for $i = 1,\dots, n$ , we have $f_1 = f_2$ , as required.

For surjectivity, fix $g \in \mathrm{Sym}(\{x_1,\dots, x_n\})$ . Since $g$ is bijective, for each $x_i$ , there exists a unique $x_{i'}$ such that $g(x_i) = x_{i'}$ . Define $f \in \mathcal S_n$ by $f(i) = i'$ . We claim that $\Phi_f = g$ , which holds since for any $x_i$ ,

$\displaystyle \Phi_f (x_i) = x_{f(i)} = x_{i'} = g(x_i),$

so that $\Phi(f) = \Phi_f = g$ , as required.

Hence, to understand the symmetries on any finite set, it suffices to understand the symmetries on $\mathcal S_n$ .

For simplicity, we now zoom in on $\mathcal S_n$ . Each element $f \in \mathcal S_n$ is a bijection, and thus, corresponds to a permutation of the ordered $n$ -tuple $(1,\dots, n)$ . Thanks to ideas in combinatorics, there are $n!$ possible bijections, so that $|\mathcal S_n| = n!$ .

Lemma 2. For any $f \in \mathcal S_n$ , define $N$ -fold composition by

$f^N := \underbrace{f \circ \cdots \circ f}_N.$

Then for any $k = 1,\dots, n$ , there exists a unique $1 \leq N_k \leq n$ such that $f^{N_k}(k) = k$ and for any $0 < i < N_k$ , $f^i(k) \neq k$ .

Proof. Fix $k = 1,\dots, n$ . Define

$\langle k \rangle := \{ f^N(k) : N \in \mathbb N^+\} \subseteq \{1,\dots, n\}.$

Consider the set

$\{ k, f(k), \dots, f^{n-1}(k), f^n(k) \} \subseteq \{1,\dots, n\}.$

Since the left-hand side has at most $n$ elements, we must have some $i < j$ such that

$f^i(k) = f^j(k) \quad\Rightarrow \quad f^{i-j}(k) = k.$

Therefore, the set

$\{N \in \mathbb N^+ : f^N(k) = k\}$

contains some $j-i \leq n$ and thus is nonempty. By the well-ordering principle, it contains a unique least integer $N_k$ , so that $f^{N_k}(k) = k$ .

In what follows, fix a non-identity permutation $f \in \mathcal S_n$ .

Lemma 3. The relation $\sim_f$ on $\mathcal S_n$ defined by

$i \sim_f j \quad \iff \quad \exists k \in \mathbb N^+: f^k(i) = j$

is an equivalence relation on $\{1,\dots, n\}$ . Furthermore, if $i \sim_f j$ , then $N_i = N_j$ as per Lemma 2.

Proof. We need to check that $\sim_f$ is reflexive, symmetric, and transitive.

For reflexivity, for any $i$ , Lemma 2 furnishes some $N_i \in \mathbb N^+$ such that $f^{N_i}(i) = i$ .

For symmetry, suppose $i_1 \sim_f i_2$ , so that there exists $k \in \mathbb N^+$ such that $f^k(i) = i_2$ . Find $m > 0$ such that $mN_{i_2} > k$ . Then

$f^k(i_1) = i_2 = f^{mN_{i_2}}(i_2) \quad \Rightarrow \quad f^{mN_{i_2} - k}(i_2)= i_1.$

Hence, $i_2 \sim_f i_1$ . Finally for transitivity, if $i_1 \sim_f i_2$ and $i_2 \sim_f i_3$ , then there exists $k_1, k_2$ such that

$f^{k_1}(i_1) = i_2, \quad f^{k_2}(i_2) = i_3.$

By substituting, $f^{k_1+k_2}(i_1) = f^{k_2}(f^{k_1}(i_1)) = i_3$ . Hence, $i_1 \sim_f i_3$ , as required.

Finally, suppose $i \sim_f j$ for $i \neq j$ . Then there exist some smallest $k \in \mathbb N^+$ such that

$f^{k}(i) = j.$

Since $f^k(i) \neq j$ , we can assume $k < N_i$ . By definition,

$f^{N_i - k}(j) = f^{N_i-k}(f^{k}(i)) = f^{N_i}(i) = i.$

By back-substituting,

$f^{N_i}(j) = f^k(f^{N_i - k}(j)) = f^k(i) = j.$

By minimality, $N_j \leq N_i$ . By a symmetric argument, $N_i \leq N_j$ . Therefore, $N_i = N_j$ , as required.

Lemma 4. Using $\sim_f$ Lemma 3, find elements $i_1,\dots, i_m$ such that

$\displaystyle \{1,\dots, n\} = \bigsqcup_{k=1}^m [i_k].$

Then for each $k$ , $[i_k] = \{f^N(i_k) : N \in \mathbb N\}$ . In this case, we write

$\displaystyle f = \prod_{k=1}^m (i_k\ f(i_k)\ \cdots\ f^{N_{i_k}-1}(i_k)).$

Each cycle is an $N_{i_k}$ -cycle.

Proof. Exercise.

In particular, cyclic permutations within each cycle do not change the result: for instance,

$(1\ 2\ 3) = (2\ 3\ 1) = (3\ 1\ 2).$

As such, we can now properly define a special kind of permutation: a cycle.

Example 1. Consider the permutation $f \in \mathcal S_4$ defined by

$(f(1), f(2), f(3), f(4)) = (2, 1, 4, 3).$

Evaluate $f$ as a product of cycles.

Solution. We have $f(1) = 2$ ,

$f^2(1) = f(f(1)) = f(2) = 1,$

$f(3) = 4$ , and

$f^2(3) = f(f(3)) = f(4) = 3.$

Hence, $f = (1\ 2)(3\ 4) = (3\ 4)(1\ 2)$ .

Definition 2. A cycle is a permutation in $\mathcal S_n$ of the form $(i_1\ i_2\ \cdots\ i_m)$ for $m$ distinct integers in $\{1,\dots, n\}$ . Given the cycles

$f = (i_1\ i_2\ \cdots\ i_m),\quad g = (j_1\ j_2\ \cdots\ j_n),$

we denote the composition permutation by the product

$g \circ f = (j_1\ j_2\ \cdots\ j_n)(i_1\ i_2\ \cdots\ i_m).$

Lemma 5. Every non-identity permutation in $\mathcal S_n$ is a product of unique, disjoint cycles in $\mathcal S_n$ .

Proof. Since composition of disjoint cycles is commutative, applying Lemma 4 gives the desired result.

Can we decompose cycles further? Surprisingly, yes.

Definition 3. A transposition is a cycle in $\mathcal S_n$ of the form $(i\ j)$ . It is clear that $(i\ j)(i\ j) = \mathrm{id}$ , so that $(i\ j)^{-1} = (i\ j)$ is also a transposition.

Example 2. Evaluate the permutations

$(1\ 3)(1\ 2),\quad (1\ 2)(1\ 3),\quad (2\ 3)(1\ 2),\quad (3\ 4)(1\ 2).$

giving your answers as products of disjoint cycles.

Solution. Denote $f = (1\ 2)$ and $g =(1\ 3)$ . Then

$\begin{aligned} (g \circ f)(1) &= g(f(1)) = g(2) = 2 ,\\ (g \circ f)(2) &= g(f(2)) = g(1) = 3, \\ (g \circ f)(3) &= g(f(3)) = g(3) = 1. \end{aligned}$

Furthermore, $(1\ (g\circ f)(1)\ (g \circ f)^2(1)) = (1\ 2\ 3)$ . Therefore,

$(1\ 3)(1\ 2) = (1\ 2\ 3).$

We leave it as an exercise to check that

$(1\ 2)(1\ 3) = (1\ 3\ 2) = (2\ 3)(1\ 2).$

Finally, since $(3\ 4)(1\ 2)$ is a product of unique cycles, there is nothing to simplify.

Theorem 2. Every non-identity permutation in $\mathcal S_n$ is a product of transpositions in $\mathcal S_n$ .

Proof. Let $f \in \mathcal S_n$ be a permutation. By Lemma 5, $f$ can be written as a product of (disjoint) cycles. Hence, it suffices to prove the case for a non-trivial cycle $f$ . Without loss of generality, assume

$f = (1\ 2\ \cdots \ k),$

with the general case obtained via relabeling. We will prove by induction on $k$ , where $2 \leq k \leq n$ . The case $k = 2$ is obvious: $(1\ 2)$ is itself already a transposition. For the general case, suppose the cycle

$f := (1\ 2\ \cdots \ i).$

can be written as a product of transpositions. Note that $f(i+1) = i+1$ . Consider the cycle

$g := (1\ 2\ \cdots \ i \ i+1)$

of length $i+1$ . Define the transposition $\phi := (1, i+1)$ . We observe that

$\begin{aligned} (\phi \circ f)(i) &= \phi(f(i)) = \phi(1) = i+1 = g(i) \end{aligned}$

and

$\begin{aligned} (\phi \circ f)(i+1) &= \phi(f(i+1)) = \phi(i+1) = 1 = g(i+1). \end{aligned}$

Furthermore, for $1 \leq k \leq i-1$ , $g(k) = k+1$ , so that

$( \phi \circ f )(k) = \phi(f(k)) = \phi(k+1) = k+1 = g(k).$

Therefore, $g = \phi \circ f$ , which means

$g = (1\ i+1)f$

is a product of transpositions, as required.

Strictly speaking, any permutation can be lengthened arbitrarily by composing with $(1\ 2)(1\ 2) = \mathrm{id}$ on either side. Nonetheless, the number of transpositions either remains even or remains odd, which motivates the next definition.

Definition 4. Call a permutation even (resp. odd) if it is a product of an even number (resp. odd number) of transpositions. Define the alternating group $\mathcal A_n$ by

$\mathcal A_n := \{f \in \mathcal S_n : f\ \text{is even}\}.$

Lemma 6. $\mathcal A_n \triangleleft \mathcal S_n$ . Furthermore, $|\mathcal A_n| = |\mathcal S_n|/2$ .

Proof. Fix $f \in \mathcal A_n$ and $g = \phi_n \circ \cdots \circ \phi_1 \in \mathcal S_n$ for transpositions $\phi_1,\dots, \phi_n$ . It is clear that

$g^{-1} = \phi_1^{-1} \circ \cdots \circ \phi_n^{-1} \in \mathcal S_n$

and each $\phi_i^{-1}$ is a transposition. Suppose $f$ is a product of $m$ transpositions for some even number $m$ . Then $g^{-1} \circ f \circ g$ is a product of $m + 2n$ transpositions. Since $m+2n$ is even, $g^{-1} \circ f \circ g \in \mathcal A_n$ . Hence, $\mathcal A_n \triangleleft \mathcal S_n$ .

For the counting claim, we note that $\mathcal A_n \sqcup (1\ 2)\mathcal A_n = \mathcal S_n$ , and that there exists an obvious bijection $\mathcal A_n \to (1\ 2)\mathcal A_n$ given by $f \mapsto (1\ 2)f$ . Hence,

$\begin{aligned} |\mathcal S_n| &= |\mathcal A_n \sqcup (1\ 2)\mathcal A_n| \\ &= |\mathcal A_n| + |(1\ 2)\mathcal A_n| \\ &= |\mathcal A_n| + |\mathcal A_n| = 2 |\mathcal A_n|,\end{aligned}$

so that $|\mathcal A_n| = |\mathcal S_n|/2$ .

Lemma 7. Given $\mathcal K \triangleleft \mathcal A_n$ with $\mathcal K \neq \{\mathrm{id}\}$ , if $\mathcal K$ contains a $3$ -cycle, then $\mathcal K = \mathcal A_n$ .

Proof. Suppose $\mathcal K \triangleleft \mathcal A_n$ and $\mathcal K \neq \{\mathrm{id}\}$ so that $\mathcal K$ contains some non-identity $3$ -cycle $f = (1\ 2\ 3) \in \mathcal A_n$ without loss of generality.

We claim that $\mathcal K$ contains all $3$ -cycles. Indeed, let $g = (i_1\ i_2\ i_3)$ be a $3$ -cycle. Define $h \in \mathcal S_n$ by

$h(k) = i_k,\quad k=1,\dots,n.$

If $h$ is even, then $h \in \mathcal A_n$ , and

$g = h \circ f \circ h^{-1} \in \mathcal K.$

If $h$ is odd, then repeat the argument by replacing $h$ with $(i_4\ i_5)h$ . Thus, $\mathcal K$ contains all $3$ -cycles.

Fix $f \in \mathcal A_n$ . We claim that $f$ can be written as a product of $3$ -cycles, so that $f \in \mathcal K$ .

We observe that without loss of generality,

$\begin{aligned} (1\ 2)(3\ 4) &= (1\ 3\ 2)(1\ 3\ 4) \in \mathcal K, \\ (1\ 2)(1\ 3) &= (1\ 3\ 2) \in \mathcal K, \\ (1\ 2)(1\ 2) &= \mathrm{id} \in \mathcal K. \end{aligned}$

Therefore, since $f$ can be written as a product of $k$ terms of the form $(a\ b)(c\ d)$ , we have $f \in \mathcal K$ . Therefore, $\mathcal K = \mathcal A_n$ .

Definition 5. Given a group $G$ and $H \leq G$ , call $H$ simple if for any $K \triangleleft H$ , $K = \{e\}$ or $K = H$ .

Remark 1. The definition of a simple group resembles that of a prime number: a positive integer $p$ is prime if it is not composite. That is, if $d \mid p$ , then $d = 1$ or $d = p$ .

Lemma 8. $\mathcal A_5$ is simple.

Proof. Fix $\mathcal K \triangleleft \mathcal A_5$ with $\mathcal K \neq \{\mathrm{id}\}$ and a non-identity permutation $f \in \mathcal K$ . By Lemma 7 it suffices to check that $\mathcal K$ has a $3$ -cycle.

Write $f$ as a product of disjoint cycles or identity maps

$f = f_k \circ \cdots \circ f_1, \quad k \leq 5.$

If all $f_i$ are the identity map, then $f$ is the identity map, a contradiction. Hence, suppose $f_1$ is not an identity map. If $f$ has no $3$ -cycles, then either $f = \phi_1$ , or $f = \phi_2 \circ \phi_1$ for some disjoint transpositions $\phi_1, \phi_2$ , or $f$ is a $4$ -cycle or $f$ is a $5$ -cycle.

In the first case, suppose without loss of generality that $f = (1\ 2)$ . Since $\mathcal K$ is normal,

$(2\ 4) = (4\ 3\ 1)(1\ 2)(1\ 3\ 4) \in \mathcal K.$

Hence, $(1\ 4\ 2) = (2\ 4) (1\ 2) \in \mathcal K$ , and $\mathcal K$ contains a $3$ -cycle.

In the second case, suppose without loss of generality that $f = (1\ 2)(3\ 4)$ . Since $\mathcal K$ is normal,

$(2\ 5)(3\ 4) = (1\ 5)(1\ 2)(3\ 4)(1\ 5) \in \mathcal K.$

Hence,

$(1\ 5\ 2) = (2\ 5)(3\ 4)(1\ 2)(3\ 4) \in \mathcal K,$

and $\mathcal K$ contains a $3$ -cycle.

In the third case, suppose $f = (1\ 2\ 3\ 4)$ . Write

$(1\ 2\ 3\ 4) = (1\ 4)(1\ 3)(1\ 2) \notin \mathcal A_5,$

so the third case is impossible.

In the fourth case, suppose $f = (1\ 2\ 3\ 4\ 5)$ . Define $g = (1\ 2)(3\ 4)$ . Then

$(2\ 5\ 4) = g \circ f \circ g^{-1} \circ f \in \mathcal K.$

Hence, no matter which case, $\mathcal K$ contains a $3$ -cycle.

By Lemma 7, $\mathcal K = \mathcal A_5$ . Hence, $\mathcal A_5$ is simple.

Lemma 9. $\mathcal A_6$ is simple.

Proof. Fix $\mathcal K \triangleleft \mathcal A_6$ with $\mathcal K \neq \{ \mathrm{id} \}$ . Let $f \in \mathcal K$ be a non-identity even permutation. By Lemma 7 it suffices to show that $\mathcal K$ contains a $3$ -cycle. Define the subset

$\mathcal G := \{g \in \mathcal K : g(6)= 6\} \subseteq \mathcal K.$

We claim that $\mathcal G \backslash \{\mathrm{id}\} \neq \emptyset$ . If $f(6) = 6$ , then we are done. Otherwise, after relabelling, $f = (1\ 2\ 3\ 4)(5\ 6)$ or $f = (1\ 2\ 3)(4\ 5\ 6)$ .

In the first case, $g := f^2 = (1\ 3)(2\ 4) \in \mathcal K$ and hence $g(6)= 6$ , as required. In the second case, define $h = (2\ 3\ 4) \in \mathcal A_6$ . Since $\mathcal K \triangleleft \mathcal A_6$ ,

$g := f\circ (h \circ f^{-1} \circ h^{-1}) \in \mathcal K$

and $g(6) = 6$ , as required. Therefore, the sub-group $\mathcal G := \{g \in \mathcal K : g(6)= 6\} \leq \mathcal K$ contains a non-identity element.

Identify $\mathcal A_{n-1} \cong \{ g \in \mathcal A_n : g(n) = n \} \leq \mathcal A_6$ so that $\{\mathrm{id}\} \neq \mathcal G \cap \mathcal A_5 \triangleleft \mathcal A_5$ .

By Lemma 8, $\mathcal A_5$ being simple implies that $\mathcal G \cap \mathcal A_5 = \mathcal A_5$ , so that $\mathcal A_5 \subseteq \mathcal G \subseteq \mathcal K$ .

Since $\mathcal A_5$ contains a $3$ -cycle, so does $\mathcal K$ . By Lemma 7, $\mathcal K = \mathcal A_6$ , so that $\mathcal A_6$ is simple, as required.

Theorem 3. $\mathcal A_n$ is simple for $n \geq 5$ .

Proof. By Lemmas 8 and 9, it suffices to prove that $\mathcal A_n$ is simple for $n \geq 7$ . Fix $\{\mathrm{id}\} \neq \mathcal K \triangleleft \mathcal A_n$ . Then there exists $f \in \mathcal K$ such that $f \neq \mathrm{id}$ .

Without loss of generality, suppose $f(1) = 2$ . Define $g := (2\ 3\ 4) \in \mathcal A_n$ . Define $h := f^{-1} \circ (g \circ f \circ g^{-1}) \in \mathcal K$ . Then $h(1) = f^{-1}(3) \neq 1$ , so $h \neq \mathrm{id}$ . Furthermore, if $f(i) \notin \{2, 3, 4\}$ , then

$(f^{-1} \circ g \circ f)(i)= i.$

Thus, $f^{-1} \circ g \circ f = (f^{-1}(2)\ f^{-1}(3)\ f^{-1}(4))$ and $g = (2\ 3\ 4)$ are $3$ -cycles. Hence, $h$ permutes at most $6$ elements. Suppose for simplicity that $h$ permutes $\{1,2,3,4,5,6\}$ . Since $n \geq 7$ , $h(n) = n$ .

Following the argument in Lemma 9, $\mathcal A_5 \subseteq \mathcal A_6 \subseteq \mathcal K$ . Since $\mathcal A_5$ contains a $3$ -cycle, so does $\mathcal K$ . By Lemma 7, $\mathcal K = \mathcal A_n$ . Hence, $\mathcal A_n$ is simple.

Theorem 3 turns out to be a key ingredient in establishing the non-existence of the quintic formula. But to get there, we will need to develop a lot more abstract algebra machinery.

For now, we conclude our discussions on $\mathcal S_n$ by making reference to Cayley’s theorem.

Theorem 4 (Cayley). If $G$ is a finite group, then there exists $H \leq \mathcal S_{|G|}$ such that $G \cong H$ .

Proof. For each $g \in G$ , define $\Phi_g \in \mathrm{Sym}(G)$ by $\Phi_g(x) = gx$ . Define the map $\Phi : G \to \mathrm{Sym}(G)$ by $\Phi(g) = \phi_g$ . We claim that $\Phi$ is an injective homomorphism. For injectivity, suppose $\Phi(g_1) = \mathrm{id}$ so that $\Phi_{g_1} = \mathrm{id}$ . Then

$g_1 = g_1 e = \mathrm{id}(e) = e,$

as required. For the homomorphism property, fix $x \in G$ . Then

$\Phi_{g_1 g_2}(x) = (g_1 g_2)x = g_1(g_2 x) =g_1 \Phi_{g_2}(x) = (\Phi_{g_1} \circ \Phi_{g_2})(x).$

Hence, $\Phi(g_1 g_2) = \Phi_{g_1 g_2} = \Phi_{g_1} \circ \Phi_{g_2}$ , as required. By Lemma 1,

$G \cong \Phi(G) \leq \mathrm{Sym}(G) \cong \mathcal S_{|G|}.$

Letting $f : \mathrm{Sym}(G) \to \mathcal S_{|G|}$ denote a group isomorphism, define $H := (f \circ \Phi)(G)$ so that

$G \cong \Phi(G) \cong (f \circ \Phi)(G) = H.$

Remark 2. If $G$ is infinite, we still have the relationship

$G \cong \Phi(G) \leq \mathrm{Sym}(G).$

This means that any study of finite groups, at its core, reduces to a study of $\mathcal S_n$ .

Next time, we re-visit an important finite group $\mathbb Z_k = \mathbb Z/k\mathbb Z$ , and consider multiplication, venturing our toes into an extension of groups—rings.

—Joel Kindiak, 31 Dec 25, 2210H

KindiakMath

The Language of Symmetry

Leave a comment Cancel reply

The Language of Symmetry

Share this:

Leave a comment Cancel reply