Applying Permutations to Group Theory

Mike

2021-06-10 (Last Modified: 2021-11-06)

Page content

This article is a continuation of More on Groups: Morphisms, Normal Subgroups, etc… In this article we’re going to continue looking into groups and apply some of our results from studying permutations to our study of them. Both fields of study enforce each other.

But first, we’re going to continue our investigation of subgroups, morphisms and equivalence relations. We saw in More on Groups: Morphisms, Normal Subgroups, etc… that if $ϕ$ is a homomorphism from a group $A$ to a group $B$ , then $K e r (ϕ)$ is a normal subgroup of $A$ . Now we’re going to show

Theorem (image is a subgroup)

Let $ϕ$ be a homomorphism from group $A$ into not necessarily all of group $B$ . If we let

$\begin{aligned} I m (ϕ) := \\ R a n g e (ϕ) = \\ {b \in B | \exists a \in A and ϕ (a) = b} \end{aligned}$

Then $I m (ϕ) \leq B$ . That is, $I m (ϕ)$ is a subgroup of $B$ .

Proof

Using the subgroup test, suppose that $x$ and $y \in I m (ϕ)$ , then we want to show that $x \cdot y^{- 1}$ is also in $I m (ϕ)$ . By definition of $I m (ϕ)$ , there are two (not necessarily distinct) elements of $A$ , $a$ and $b$ , say, such that $ϕ (a) = x$ , and $ϕ (b) = y$ . Now, since $A$ is a group, $a \cdot b^{- 1} \in A$ , so then

$\begin{aligned} ϕ (a \cdot b^{- 1}) = \\ ϕ (a) \cdot ϕ (b)^{- 1} \in I m (ϕ) \end{aligned}$

That means that, by what we assumed $a$ and $b$ were, that $x \cdot y^{- 1} \in I m (ϕ)$ .

QED

In the last entry, we proved that all kernels of homomorphisms were normal subgroups. Soon we’ll see that all normal subgroups are kernels for a homomorphism into another group. First we need to take a slight detour and discuss the notion of equivalence classes.

Definition (equivalence class)

Let $\equiv$ be an equivalence relation on a set, $S$ , let $s \in S$ be an element of $S$ . We define the equivalence class of $s$ , often written as $[s]$ , to be the set of all elements, $t \in S$ , such that $s \equiv t$ .

Definition (factor set)

Let $S$ be a set and $\equiv$ be an equivalence relation among pairs of elements of $S$ . Then the set of equivalence classes of $S$ form a set, sometimes written as $S /_{\equiv}$ . It is sometimes read “ $S$ mod $\equiv$ ”, and is referred to as a factor set.

Factor sets are similar to factor groups, but don’t have the added structure that comes from having a binary operator. In order to make a factor group, you have to have a factor set and a binary operator that operates on pairs of equivalence classes, mapping them to a third equivalence class, which obeys the group axioms.

When the factor set can be turned into a factor group, it’s typically written as $G / H := {[g] | g \in G}$ , where $H \leq G$ is a subgroup and $[g] = {g^{'} \in G | g^{'} \equiv g \mod H}$

Recall that

$g^{'} \equiv g \mod H \Leftrightarrow g^{'} H = g H$

However, for most subgroups, $H \leq G$ , this factor set cannot be made into a group. The reason is that a binary operator on the equivalence classes (which we’ll sometimes write as $\circ_{\equiv}$ to avoid confusion with the binary operator in $G$ ) can’t be both well-defined and preserve some of the structure of $G$ . What we want is for any two equivalence classes, $[r]$ , and $[s]$ , to have $[r] \circ_{\equiv} [s] = [r \circ_{G} s]$ . The good news is that sometimes this is possible. When $H$ is a normal subgroup of $G$ , then we can form a factor group, as we’ll show below.

Mini-Lemma (when aH = H)

$a H = H$ if and only if $a \in H$ .

Proof

Suppose $a H = H$ , then $a \cdot e \in a H = H$ , so $a \in H$ . Now suppose that $a \in H$ , then $a = a \cdot e \in a H$ , so $a \in H \cap a H$ , and since cosets are either equal or disjoint (i.e. their intersection is empty), $a H = H$ .

QED

Mini-Lemma (aN = Na)

Let $N ◃ G$ , then for all $g \in G$ , the cosets $g N$ and $N g$ are the same. (This is an alternate way to define normal subgroup).

Proof

Let $N$ be a normal subgroup of $G$ and $g \in G$ be an arbitrary element of $G$ . Then $g^{- 1} N g = N$ , which implies that if we apply $g$ to the left of every element, the cosets will remain equal. That gives us $N g = g N$ .

QED

Theorem (mod normal subgroup is a group)

Let $G$ be a group, and $N$ be a normal subgroup. Let $α (x) := [x]$ be a function which sends any $x \in G$ to its equivalence class in $G / N$ . Let $[r] \circ_{\equiv} [s] := [r \circ_{G} s]$ be a binary operator on $G / N$ .

$\circ_{\equiv}$ is well-defined. That is, for any two equivalence classes $[r]$ and $[s]$ in $G / N$ , $[r] \circ_{\equiv} [s] = [r \circ_{G} s]$ .
$G / N$ is a group with $\circ_{\equiv}$ its binary operator.
$α$ is an epimorphism from $G$ onto $G / N$ , and $K e r (α) = N$ .

Proof

Now we prove $\circ_{\equiv}$ is well defined. The issue that we have to make sure we avoid is having the binary operator give different results for different choices of equivalence class representatives. What we mean is that if $[s_{1}]$ is an equivalence class and $s_{2} \in [s_{1}]$ , then $[s_{1}] = [s_{2}]$ . We have to guarantee that if $[r_{1}] = [r_{2}]$ , that $[r_{1}] \circ_{\equiv} [s_{1}] = [r_{2}] \circ_{\equiv} [s_{2}]$ , whenever $r_{1} \equiv r_{2}$ and $s_{1} \equiv s_{2}$ .

Let $[r_{1}] = [r_{2}]$ and $[s_{1}] = [s_{2}]$ , we want to show that $[r_{1}] \circ_{\equiv} [s_{1}] = [r_{2}] \circ_{\equiv} [s_{2}]$ . This will happen if and only if $[r_{1} \circ_{G} s_{1}] = [r_{2} \circ_{G} s_{2}]$ , which means that $r_{1} \circ_{G} s_{1} \equiv r_{2} \circ_{G} s_{2} \mod N$ , and by definition that will happen if and only if $(r_{1} \circ_{G} s_{1}) N = (r_{2} \circ_{G} s_{2}) N$ .

Since $[r_{1}] \equiv [r_{2}]$ , we have $r_{1} \equiv r_{2} \mod N$ , which means $r_{1} N = r_{2} N$ , and likewise we also have $s_{1} N = s_{2} N$ . We want to show that $r_{1} \circ_{G} s_{1} N = r_{2} \circ_{G} s_{2} N$ . In the next calculation, we omit $\circ_{G}$ , and instead just write $r_{1} s_{1}$ , for example.

$\begin{aligned} r_{1} s_{1} N & = \\ r_{1} (s_{1} N) & = \\ r_{1} (s_{2} N) \end{aligned}$

then by the mini lemma above, since $N$ is a normal subgroup, we have

$\begin{aligned} r_{1} (s_{2} N) & = \\ r_{1} (N s_{2}) & = \\ (r_{1} N) s_{2} & = \\ (r_{2} N) s_{2} \end{aligned}$

Again, by the mini lemma we have, $r_{2} (N s_{2}) = r_{2} s_{2} N$ . Thus $\circ_{\equiv}$ is well-defined, and we have proven claim 1 above.

By what we’ve just shown, for any $g \in G$ , $[g] \circ_{\equiv} [g^{- 1}] = [e_{G}]$ , so $[g]^{- 1} = [g^{- 1}]$ , so every equivalence class has an inverse equivalence class. We’ve also seen that for every two equivalence classes $[r]$ , and $[s]$ , $[r] \circ_{\equiv} [s] = [r \circ_{G} s]$ , so $G / N$ is closed under $\circ_{\equiv}$ . The final step to proving that $G / N$ is a group with binary operator $\circ_{\equiv}$ is to show that this operator is associative, which is straight-forward.

Notice that for any three equivalence classes $[r]$ , $[s]$ , and $[t]$ , that

$\begin{aligned} [r] \circ_{\equiv} ([s] \circ_{\equiv} [t]) & = \\ [r] \circ_{\equiv} [s \circ_{G} t] \end{aligned}$

and that is equal to

$\begin{aligned} [r \circ_{G} s \circ_{G} \circ_{G} t] & = \\ [(r \circ_{G} s) \circ_{G} t] \end{aligned}$

which from what we showed in the proof of claim 1 is equal to $[r \circ_{G} s] \circ_{\equiv} [t]$ , which (again by what we showed from case 1) is equal to $([r] \circ_{\equiv} [s]) \circ_{\equiv} [t]$ . This finishes the proof of claim 2.

By the definition of $α$ , it is a homomorphism. Let’s determine its kernel.

Suppose $g \in G$ is such that $α (g) = [e]$ , that means that $g \in e N = N$ , so by the mini lemma above, $g \in N$ . We also see that $g \in N$ implies that $g N = N$ , so $α (g) = [g] = [e]$ . Therefore $K e r (α) = N$ .

The only thing left to check is that it is onto $G / N$ , which is easy. Let $g N$ be a left coset of $N \in G / N$ , then $[g]$ is an equivalence class in the range of $α$ . That finishes the proof of claim 3.

QED

We hope this isn’t getting too confusing. We’ve been sloppy about what exactly lives in $G / N$ , and the proof of claim 3 in the above theorem laid that bare. At times it seems like $G / N$ is a set of cosets of $N$ , and at other times it seems like it’s a set of equivalence classes of elements of $G$ . They’re really the same thing, though. We showed (in More on Groups: Morphisms, Normal Subgroups, etc…) that $\equiv \mod H$ is an equivalence relation on the set of cosets of a subgroup of $G$ . We defined two elements to be in the same equivalence class if they belong to the same coset.

Now we start to think about how a group can act on a set.

Definition (group actions)

Let $X$ be a set, $S_{X}$ be the group of all permutations of $X$ , and $G \leq S_{X}$ , then $g \in G$ is said to act on $X$ , and $G$ is said to be a group of actions on $X$ .

In fact, since $G$ itself is a set with a binary operation, $G$ can even act on itself. What’s more, every group acts on itself.

Theorem (originally due to Cayley)

Let $G$ be a group, then there is an isomorphism $ϕ : G \to H \leq S_{G}$ , from $G$ into a subgroup of $S_{G}$ , the group of all permutations of the elements of $G$ .

This means that any group can be thought of as a subgroup of a group of permutations.

Proof

Let $G$ be a group, but for this proof, let’s refer to the set of all of the elements of $G$ as $Y$ . That is, $Y = {g | g \in G}$ . Then a permutation of $G$ is a permutation of $Y$ , and belongs to $S_{Y}$ , by definition. Define $β : G \to S_{Y}$ such that $β (g) := π_{g} \in S_{Y}$ , where $π_{g} (y) = g \circ_{G} y$ , for any $y \in Y$ . Remember, $y \in Y$ means that $y$ is an element of $G$ , so $g \circ_{G} y$ is defined.

First we have to show that

$\begin{aligned} β (g_{1} \circ_{G} g_{2}) (y) & = \\ β (g_{1}) \circ_{S_{Y}} β (g_{2}) (y) & = \\ π_{g_{1}} \circ π_{g_{2}} (y) & = \\ π_{g_{1}} (π_{g_{2}} (y)) \end{aligned}$

for all $y \in Y$ . This follows from the fact that

$\begin{aligned} β (g_{1} \circ_{G} g_{1}) (y) & = \\ π_{g_{1} \circ_{G} g_{2}} (y) & = \\ (g_{1} \circ_{G} g_{2}) \circ_{G} y \end{aligned}$

and

$\begin{aligned} π_{g_{1}} (π_{g_{2}} (y)) & = \\ g_{1} \circ_{G} (g_{2} \circ_{G} y) \end{aligned}$

By associativity, the two must be equal.

Finally, we have to show that for any $g \in G$ , $β (g) \in S_{Y}$ , i.e. that $π_{g}$ is actually a permutation of $Y$ . To do that we must show that $π_{g} : Y \overset{1-1, onto}{\to} Y$ .

Let’s first show that $π_{g} (y)$ is 1-1. Suppose $π_{g} (y_{1}) = π_{g} (y_{2})$ , then $g \circ_{G} y_{1} = g \circ_{G} y_{2}$ . We’ve already shown that we can apply cancellation in $G$ , so $y_{1} = y_{2}$ , and $π$ is 1-1.

Now we show that $π_{g}$ is onto. Let $y$ be any element in $Y$ , and thus an element of $G$ . Consider that

$\begin{aligned} π_{g} (g^{- 1} \circ_{G} y) & = \\ g \circ_{G} (g^{- 1} \circ_{G} y) & = \\ y \end{aligned}$

so $y \in R a n g e (π_{g})$ , thus $π_{g}$ is onto. It is therefore a permutation, and our proof is finished.

QED

In the earlier entry (More Math of Permutations), we showed that for any permutation of a finite set, there is a function

$S i g n (π) = \pm 1$

and that

$\begin{aligned} S i g n (π_{1} \circ π_{2}) = \\ S i g n (π_{1}) \cdot S i g n (π_{2}) \end{aligned}$

We now know that $S i g n : S_{X} \to {1, - 1}$ is a homomorphism from the set of all permutations of a finite set $X$ into the set ${1, - 1}$ . What’s more, with the above Theorem of Cayley, there’s also such a homomorphism from each finite group into the set of ${1, - 1}$ . This can be very useful. As an example we can now prove a couple of lemmas:

Lemma (either all even or half even)

Let $G$ be a finite group. Then if there exists $g \in G$ , such that $S i g n (g) = - 1$ , there exists $N ◃ G$ , such that $(G : N) = 2$ . Otherwise for every $g \in G$ , $S i g n (g) = 1$ .

Proof

Suppose there is a $g \in G$ , such that $S i g n (g) = - 1$ , then let $N := {h \in G | S i g n (h) = 1}$ . Notice that if $n_{1}$ and $n_{2} \in N$ , that

$\begin{aligned} S i g n (n_{1} \cdot n_{2}^{- 1}) & = \\ S i g n (n_{1}) \cdot S i g n (n_{2})^{- 1} & = \\ 1 \cdot 1^{- 1} & = \\ 1 \end{aligned}$

so $n_{1} \cdot n_{2}^{- 1} \in N$ , and thus $N$ is a subgroup of $G$ . It is a normal subgroup, because for any $g \in G$ , and $n \in N$ ,

$\begin{aligned} S i g n (g^{- 1} \cdot n \cdot g) = \\ S i g n (g^{- 1}) \cdot S i g n (n) \cdot S i g n (g) \end{aligned}$

and that is equal to

$S i g n (g)^{- 1} \cdot S i g n (g) \cdot 1 = 1$

and so is in $N$ . Therefore $g^{- 1} N g = N$ , so $N$ is normal.

Now we show that $(G : N) = 2$ . Notice that for any $n \in N$ , $g \cdot n \notin N$ , and likewise, for any $h \notin N$ , $g \cdot h \in N$ . We previously showed that $π_{g} (x) = g \cdot x$ is 1-1, so $| N | \leq | G ∖ N | \leq | N |$ , therefore $| N | = \frac{1}{2} | G |$ , and thus $(G : N) = 2$ .

QED

Lemma ( 2*odd has a normal subgroup of order odd)

Let $G$ be a group of order $2 \cdot (2 \cdot k + 1)$ , then $G$ has a subgroup $N$ of order $2 \cdot (2 \cdot k + 1)$ , which is normal in $G$ .

We’re going to prove this in the next entry. It takes a bit more work than the above lemma.