Applying Permutations to Group Theory

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 \( \phi \) is a homomorphism from a group \(A\) to a group \(B\), then \( Ker(\phi) \) is a normal subgroup of \(A\). Now we’re going to show

Theorem (image is a subgroup)

Proof

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

$$ \begin{align} &\phi(a \cdot b^{-1}) = \\ &\phi(a) \cdot \phi(b)^{-1} \in Im(\phi) \\ \end{align} $$

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

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)

Definition (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)

Proof

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

QED

Mini-Lemma (aN = Na)

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)

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_1s_1\), for example.

$$ \begin{align} &r_1s_1 N &&= \\ &r_1 ( s_1 N) &&= \\ &r_1 (s_2 N) \end{align} $$

then by the mini lemma above, since \(N\) is a normal subgroup, we have

$$ \begin{align} &r_1 (s_2 N) &&= \\ &r_1 (N s_2) &&= \\ &(r_1 N) s_2 &&= \\ &(r_2 N) s_2 \\ \end{align} $$

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{align} &[r] \circ_{\equiv} ( [s] \circ_{\equiv} [t] ) &&= \\ &[r] \circ_{\equiv} [s \circ_{G} t] \\ \end{align} $$

and that is equal to

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

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 \( \alpha\), it is a homomorphism. Let’s determine its kernel.

Suppose \(g \in G\) is such that \( \alpha(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 \( \alpha(g) = [g] = [e] \). Therefore \( Ker(\alpha) = N \).

The only thing left to check is that it is onto \(G /N\), which is easy. Let \(gN\) be a left coset of \(N \in G / N\), then \( [g] \) is an equivalence class in the range of \( \alpha \). 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)

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)

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 \( \beta : G \rightarrow S_{Y} \) such that \( \beta(g) := \pi_{g} \in S_{Y} \), where \( \pi_{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{align} &\beta(g_1 \circ_{G} g_2)(y) &&= \\ &\beta(g_1) \circ_{S_{Y}} \beta(g_2)(y) &&= \\ &\pi_{g_1} \circ \pi_{g_2}(y) &&= \\ &\pi_{g_1}(\pi_{g_2}(y)) \\ \end{align} $$

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

$$ \begin{align} &\beta( g_1 \circ_{G} g_1)(y) &&= \\ &\pi_{g_1 \circ_{G} g_2}(y) &&= \\ &(g_1 \circ_{G} g_2) \circ_{G} y \\ \end{align} $$

and

$$ \begin{align} &\pi_{g_1} (\pi_{g_2}(y)) &&= \\ &g_1 \circ_{G} ( g_2 \circ_{G} y ) \\ \end{align} $$

By associativity, the two must be equal.

Finally, we have to show that for any \(g \in G\), \( \beta(g) \in S_{Y} \), i.e. that \( \pi_{g} \) is actually a permutation of \( Y \). To do that we must show that \( \pi_{g} : Y \xrightarrow{\text{1-1, onto}} Y \).

Let’s first show that \( \pi_{g}(y) \) is 1-1. Suppose \( \pi_{g}(y_1) = \pi_{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 \( \pi \) is 1-1.

Now we show that \( \pi_{g} \) is onto. Let \( y \) be any element in \(Y\), and thus an element of \(G\). Consider that

$$ \begin{align} &\pi_{g}(g^{-1} \circ_{G} y) &&= \\ &g \circ_{G} (g^{-1} \circ_{G} y) &&= \\ &y \\ \end{align} $$

so \( y \in Range(\pi_{g}) \), thus \( \pi_{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

\[Sign(\pi) = \pm 1 \]

and that

$$ \begin{align} &Sign(\pi_1 \circ \pi_2) = \\ &Sign(\pi_1) \cdot Sign(\pi_2) \\ \end{align} $$

We now know that \(Sign : S_{X} \rightarrow \{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)

Proof

Suppose there is a \(g \in G\), such that \( Sign(g) = -1\), then let \( N := \{ h \in G | Sign(h) = 1 \} \). Notice that if \(n_1\) and \(n_2 \in N \), that

$$ \begin{align} &Sign(n_1 \cdot n_2^{-1}) &&= \\ &Sign(n_1) \cdot Sign(n_2)^{-1} &&= \\ &1 \cdot 1^{-1} &&= \\ &1 \\ \end{align} $$

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{align} &Sign(g^{-1} \cdot n \cdot g) = \\ &Sign(g^{-1}) \cdot Sign(n) \cdot Sign(g) \\ \end{align} $$

and that is equal to

\[ Sign(g)^{-1} \cdot Sign(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 \not\in N \), and likewise, for any \( h \not\in N\), \( g \cdot h \in N \). We previously showed that \( \pi_{g}(x) = g \cdot x \) is 1-1, so \( | N | \leq | G \setminus 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)

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