MIT 18.701 — Lecture 2

Group Examples, Subgroups, Isomorphisms, Homomorphisms

§ Group Theory Definitions (cont.)

Theorem. (Uniqueness of Identity) Any group $G$ has an identity $1 \in G$ . That identity $1$ , in fact, is unique.

Proof: If $G$ had two identities $1$ and $1'$ , then $1 = 11' = 1'$ , so in fact $1 = 1'$ . $\blacksquare$

Definition (Cyclic Group). The cyclic group of order $n$ , denoted $C_n$ , is the set $\{0, 1, 2, \dots, n - 1\}$ together with operation “addition modulo $n$ ”.

Definition (Cyclic Group v2). Equivalently, $C_n$ is the group $\{1, g, g^2, \dots, g^{n - 1}\}$ together with operation “multiplication, given $g^n = 1$ ”. This representation of $C_n$ better shows how $C_n$ is generated by a single element $g$ .

Definition (Direct Product). Given groups $G$ and $H$ , the group $G \times H$ is the set $\{(g, h): g \in G, h \in H\}$ together with the operation $(g_1, h_1)(g_2, h_2) = (g_1g_2, h_1h_2)$ .

§ Group Examples by Order

We can now classify all groups of small order up to isomorphism.

Order 1. Only the trivial group.
Order 2. Only $C_2$ .
Order 3. Only $C_3$ .
Order 4. Only $C_4$ and $C_2 \times C_2$ .
- These groups are non-isomorphic! One way to see this is to note that the claim “ $g + g = 0$ for all $g \in G$ ” is true for $G = C_2 \times C_2$ but false for $G = C_4$ .
Order 5. Only $C_5$ .
Order 6. Either $C_6$ or $S_3$ .
- The groups $C_2 \times C_3$ and $C_6$ are the same group. One way to see this is to note that, just like $C_6$ , $C_2 \times C_3$ is also generated by a single element: $(1, 1)$ .
- The group $S_3$ is the lowest-order nonabelian group.
More generally, for primes $p$ , the only group of order $p$ is $C_p$ .

§ Subgroups

Definition (Subgroup). A group $H$ is a subgroup of another group $G$ if (i) $H \subseteq G$ , and (ii) the operation of $H$ is directly inherited from the operation of $G$ .

Example. The trivial group is a subgroup of any group.

Example. For any groups $G$ and $H$ , the group $G \times H$ has subgroups $G \times \{1_H\}$ and $\{1_G\} \times H$ .

Example. The group $(\mathbb{R}, +)$ has subgroups $(\mathbb{Z}, +)$ , $(\mathbb{Q}, +)$ , and $(\mathbb{Q}\pi + \mathbb{Q}e, +)$ (among many others).

Remark. If $H_1$ and $H_2$ are subgroups of $G$ , then $H_1 \cap H_2$ is also a subgroup! However, $H_1 \cup H_2$ is not usually a subgroup; closure is typically violated.

What if we consider subgroups in the context of matrix groups?

Example. The group $GL_n(\mathbb{R})$ has the following subgroups.

The group $GL_n(\mathbb{Q})$ is a subgroup. But $\{A \in \mathbb{Z}^{n \times n} : \det A \neq 0\}$ isn't: it doesn't have inverses!
The special linear group $SL_n(\mathbb{R}) := \{A \in \mathbb{R}^{n \times n}: \det A = 1\}$ is a subgroup.
The special orthogonal group $SO_2(\mathbb{R}) := \left\{ \begin{bmatrix} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{bmatrix} : \theta \in \mathbb{R}\right\}$ is a subgroup of $GL_2(\mathbb{R})$ .

§ Geometric Groups

Groups can capture geometric symmetries, turning geometric problems into algebraic problems!

Definition (Dihedral Groups). For any positive integer $n \geq 3$ , the group $D_n$ consists of all symmetries of a regular $n$ -gon. Note that $|D_n| = 2n$ ; there are $n$ rotational symmetries and $n$ reflectional symmetries.

More complicatedly, one can consider the group of all symmetries of an icosahedron.

Tip: Learn how to freehand an icosahedron; it's not as hard as it looks!

Get excited to learn more about icosahedra!

§ Isomorphisms

We hand-waved the definition of isomorphism earlier. Let's fix that.

Definition (Isomorphism). Consider groups $(G, \cdot)$ and $(H, \star)$ . Then an isomorphism is a bijection $f: G \to H$ such that for any $g_1, g_2 \in G$ , we have $f(g_1 \cdot g_2) = f(g_1) \star f(g_2)$ . In other words, you can pair the elements of $G$ and $H$ so that the products correspond under this pairing.

Definition (Isomorphic). Groups $(G, \cdot)$ and $(H, \star)$ are isomorphic if there exists an isomorphism $f: G \to H$ . We use the notation $G \cong H$ to indicate that $G$ and $H$ are isomorphic.

Theorem. (Image of the Identity) Given an isomorphism $f: G \to H$ , we have $f(1_G) = 1_H$ .

Proof: By definition of isomorphism, observe:

f(1_G) \star f(1_G) = f(1_G \cdot 1_G) ~ \implies ~ f(1_G) \star f(1_G) = f(1_G) ~ \stackrel{\star f(1_G)^{-1}}{\implies} ~ f(1_G) = 1_H. ~~~ \blacksquare

Example. The group of $n \times n$ permutation matrices is isomorphic to $S_n$ .

Example. Recall the coincidence $2n = n!$ when $n = 3$ ; therefore, $|D_3| = |S_3|$ . It turns out, in fact, that $D_3$ and $S_3$ are isomorphic! The isomorphism can be found by interpreting any symmetry of the equilateral triangle as a permutation of its vertices; the nontrivial rotations yield $3$ -cycles, and reflections yield $2$ -cycles.

§ Group Generation

Definition (Subgroup Generated by Subset). Let $S$ be a subset of a group $G$ . Then the subgroup generated by $\mathbf{S}$ is the intersection of all subgroups of $G$ that contain $S$ .

Equivalently, we can think of the subgroup generated by $S = \{x_1, x_2, \dots, x_n\}$ as the set of all possible results of multiplying terms of the form $x_i$ or $x_i^{-1}$ in some order. (Analogies: span, convex hull, fruit in a blender, …)

Example. If $S$ is not just a subset of $G$ , but more strongly a subgroup, then the subgroup generated by $S$ is just $S$ .

This lets us more formally define group generation.

Definition (Generation). A group $G$ is said to be generated by $S \subseteq G$ if the subgroup generated by $S$ is $G$ .

Theorem. (Generation by a Single Element) If $G$ is a group generated by a single element $g$ , then $G$ is either a cyclic group $C_n = \{1, g^1, g^2, \dots, g^{n - 1}\}$ , or $G$ is $(\mathbb{Z}, +)$ .

Proof: By definition of subgroup generation, $G$ must contain every element in the set $\{\dots, g^{-2}, g^{-1}, 1, g^1, g^2, \dots\}$ . If all of these elements are distinct, then $G$ is just $(\mathbb{Z}, +)$ .

Suppose some two elements are not distinct, then. This lets us choose distinct integers $a$ and $b$ such that $g^a = g^b$ , which implies $g^{a - b} = 1$ . If we choose $(a, b)$ so that $n = |a - b|$ is as small as possible, then $G \cong C_n$ . $\blacksquare$

Unfortunately, the set of groups generated by two elements is much less tractable.

Theorem. (Subgroups of $\mathbf{(\mathbb{Z}, +)}$ ) The only subgroups $H$ of $(\mathbb{Z}, +)$ are of the form $(d\mathbb{Z}, +)$ for some integer $d$ .

Proof: One case is $H = \{0\}$ , corresponding to $d = 0$ . So let's assume $H \neq \{0\}$ , which lets us take $d$ to be the smallest positive integer in $H$ .

Claim. For any $n \in H$ , $n$ must be a multiple of $d$ .

Proof: Suppose the contrary. Divide $n$ by $d$ to yield $q$ as a quotient and $r$ as a remainder. It must follow that $n = dq + r$ , where $0 < r < d$ .

By closure of $H$ , however, observe that $n \underbrace{- d - d \dots - d}_{q \text{ times}} = r$ must also be in $H$ . But $0 < r < d$ , contradicting the assumption that $d$ was the smallest positive integer in $H$ . $\square$

The above claim immediately implies $H = d\mathbb{Z}$ , as desired. $\blacksquare$

§ Homomorphisms

What if isomorphisms didn't have to be bijective?

Definition (Homomorphism). A homomorphism between groups $(G,\cdot)$ and $(H, \star)$ is a function $f: G \to H$ such that for any $g_1, g_2 \in G$ , we have $f(g_1 \cdot g_2) = f(g_1) \star f(g_2)$ .

Example. All isomorphisms are homomorphisms.

Example. Let $(G, \cdot)$ and $(H, \star)$ be literally any groups. Then $f: G \to H$ defined by $f(g) = 1_H$ for all $g \in G$ is a homomorphism: the trivial homomorphism.

Example. If $H$ is a subgroup of $G$ , then the inclusion (“do-nothing”) function $f: H \to G$ is a homomorphism.

Example. There is a homomorphism $f: (\mathbb{C}, +) \to (\mathbb{C}^{\times}, \cdot)$ (where $\mathbb{C}^{\times} := \{z \in \mathbb{C}: z \neq 0 \}$ ) defined by $f(z) = e^z$ . The condition $f(z_1 + z_2) = f(z_1) \cdot f(z_2)$ is equivalent to the identity $e^{z_1 + z_2} = e^{z_1} \cdot e^{z_2}$ .

Example. Take $G = (\mathbb{Z}, +)$ and $H = C_n$ . Then $f: G \to H$ defined by $f(k) = \text{``the remainder of } k \text{ modulo } n\text{''}$ is a homomorphism. This is a preview of a quotient homomorphism.

Example. Take $G = GL_n(\mathbb{R})$ and $H = (\mathbb{R}^{\times}, \cdot)$ (where $\mathbb{R}^{\times} := \{r \in \mathbb{R}: r \neq 0 \}$ ). Then $f: G \to H$ defined by $f(M) = \det M$ is a homomorphism.

That last example lets us prove a very funny theorem.

Theorem. (Determinant of Permutation Matrices) Let $M$ be an $n \times n$ permutation matrix. Then $\det M = \pm 1$ .

Proof: Let $f$ denote the aforementioned homomorphism $f: GL_n(\mathbb{R}) \to (\mathbb{R}^{\times}, \cdot)$ . Then:

f(M) \cdot f(M^{-1}) = f(MM^{-1}) = f(I_n) = 1

Recall $f(M) = \det M$ and $f(M^{-1}) = \det M^{-1}$ must be integers since $M$ and $M^{-1}$ are both permutation matrices. Yet the product of these integers is $1$ , so the only possibility is that both $f(M)$ and $f(M^{-1})$ are $\pm 1$ , as desired. $\blacksquare$

Taking into account the fact that $S_n$ is isomorphic to the group of $n \times n$ permutation matrices, we may define:

Definition (Permutation Sign). Consider the natural isomorphism $f: S_n \to \text{group of permutation matrices}$ . Then we say that the sign of a permutation $\pi \in S_n$ is $\det f(\pi)$ . (Note that the sign is always $\pm 1$ .)