Subgroups and generators

A subgroup is a group living inside another group, using the same operation. We have met many already: the rotations inside \(D_n\), the even permutations \(A_n\) inside \(S_n\), the multiples of 3 inside \(\mathbb{Z}\). This lesson makes the idea precise, gives quick tests for recognizing subgroups, introduces the subgroup generated by a set of elements, and draws the complete picture of subgroups for a few small groups. Subgroups are the raw material for the rest of the course: cosets, normal subgroups, kernels and stabilizers are all special subgroups.

Definition and the subgroup tests

Let \(G\) be a group. A subset \(H \subseteq G\) is a subgroup, written \(H \le G\), if \(H\) is itself a group under the operation of \(G\). Associativity is inherited automatically, so the content of the definition is three conditions: \(H\) contains the identity of \(G\), \(H\) is closed under the operation (\(a, b \in H\) implies \(ab \in H\)), and \(H\) is closed under inverses (\(a \in H\) implies \(a^{-1} \in H\)).

Every group has the trivial subgroup \(\{e\}\) and the whole group \(G\) as subgroups; any other subgroup is called proper and nontrivial. Note that the identity of a subgroup must be the identity of \(G\): if \(f \in H\) satisfies \(ff = f\) then canceling in \(G\) gives \(f = e\).

Theorem (one-step subgroup test). A nonempty subset \(H\) of \(G\) is a subgroup if and only if \(ab^{-1} \in H\) whenever \(a, b \in H\).

Proof: a subgroup certainly has this property. Conversely, suppose \(H\) is nonempty and closed under \((a, b) \mapsto ab^{-1}\). Pick any \(a \in H\); then \(e = aa^{-1} \in H\). For \(b \in H\), \(b^{-1} = eb^{-1} \in H\). For \(a, b \in H\), we now know \(b^{-1} \in H\), so \(ab = a(b^{-1})^{-1} \in H\). All three conditions hold.

Theorem (finite subgroup test). A nonempty finite subset \(H\) of \(G\) that is closed under the operation is a subgroup.

Proof: let \(a \in H\). The powers \(a, a^2, a^3, \dots\) all lie in \(H\) by closure, and \(H\) is finite, so two of them coincide, say \(a^i = a^j\) with \(i < j\). Then \(a^{j-i} = e\), so \(e \in H\), and \(a^{-1} = a^{j-i-1}\), which lies in \(H\) (it is \(e\) if \(j - i = 1\)). So \(H\) contains inverses too.

The finite test is very convenient: to show that a finite set of permutations or matrices is a group, closure is the only thing to check. It fails for infinite sets: the positive integers are closed under addition but are not a subgroup of \(\mathbb{Z}\).

Intersections, unions and centralizers

If \(H\) and \(K\) are subgroups of \(G\), then \(H \cap K\) is a subgroup: it contains \(e\), and if \(a, b\) lie in both then so does \(ab^{-1}\). The same argument works for the intersection of any collection of subgroups, finite or infinite.

The union is usually not a subgroup. In \(\mathbb{Z}\), \(2\mathbb{Z} \cup 3\mathbb{Z}\) contains 2 and 3 but not \(2 + 3 = 5\). In fact \(H \cup K\) is a subgroup only when one of \(H, K\) contains the other: if \(h \in H \setminus K\) and \(k \in K \setminus H\), then \(hk\) cannot lie in \(H\) (else \(k = h^{-1}(hk) \in H\)) nor in \(K\) (else \(h \in K\)).

Two families of subgroups attached to elements are worth naming. The centralizer of an element \(a\) is \(C(a) = \{g \in G : ga = ag\}\), the elements that commute with \(a\). It is a subgroup: if \(ga = ag\) then multiplying by \(g^{-1}\) on both sides gives \(ag^{-1} = g^{-1}a\), and products of elements commuting with \(a\) commute with \(a\). The center \(Z(G)\) from lesson 5 is the intersection of all the centralizers, so it is a subgroup as well, and it is abelian. A group is abelian exactly when \(Z(G) = G\).

The subgroup generated by a set

For an element \(a\), the cyclic subgroup \(\langle a \rangle = \{a^k : k \in \mathbb{Z}\}\) is the smallest subgroup containing \(a\). More generally, for any subset \(S \subseteq G\) the subgroup generated by \(S\), written \(\langle S \rangle\), is the intersection of all subgroups of \(G\) that contain \(S\). It is the smallest subgroup containing \(S\), and concretely it consists of all finite products \(s_1^{\pm 1} s_2^{\pm 1} \cdots s_k^{\pm 1}\) of elements of \(S\) and their inverses, together with \(e\). (Those products form a subgroup containing \(S\), and any subgroup containing \(S\) must contain them all.) When \(\langle S \rangle = G\) we say \(S\) generates \(G\).

In a finite group the inverses are not needed, because \(s^{-1}\) is a positive power of \(s\). So \(\langle S \rangle\) can be computed by starting from \(e\) and repeatedly multiplying by elements of \(S\) until nothing new appears, which is exactly what the generate function in lesson 5 did.

Some important generating sets:

• \(\mathbb{Z}\) is generated by 1, and also by \(\{2, 3\}\), since \(1 = 3 - 2\). In general \(\langle a, b \rangle = \gcd(a, b)\mathbb{Z}\) in \(\mathbb{Z}\), a restatement of Bézout's identity.

• \(D_n\) is generated by \(r\) and \(s\), and also by two adjacent reflections \(s\) and \(rs\), since their product \(rs \cdot s = r\).

• \(S_n\) is generated by its transpositions (lesson 4), by the adjacent transpositions \((1\,2), (2\,3), \dots, (n{-}1\;n)\), and even by just the two elements \((1\,2)\) and \((1\,2\,\cdots\,n)\).

• \(A_n\) is generated by its 3-cycles, for \(n \ge 3\), since every product of two transpositions is a product of 3-cycles: \((a\,b)(a\,c) = (a\,c\,b)\) and \((a\,b)(c\,d) = (a\,c\,b)(a\,c\,d)\).

The last identity is worth checking by hand, following each of \(a, b, c, d\) from right to left; lesson 4 explained the convention. Generating sets matter in practice because a group with millions of elements can be described by two or three of them. The Rubik's cube group, discussed in lesson 12, has about \(4.3 \times 10^{19}\) elements and is generated by six face turns.

Products of subgroups

Given subgroups \(H\) and \(K\) of \(G\), the product set is \(HK = \{hk : h \in H, k \in K\}\). It always contains both \(H\) and \(K\), but it need not be a subgroup. In \(S_3\), take \(H = \langle (1\,2) \rangle\) and \(K = \langle (1\,3) \rangle\). Then \(HK = \{e, (1\,2), (1\,3), (1\,2)(1\,3)\}\) has four elements, and four does not divide six, so by Lagrange's theorem in lesson 7 it cannot be a subgroup; directly, \((1\,3)(1\,2)\) is missing from it.

Two facts about product sets are used repeatedly later in the course.

Theorem. If \(H\) and \(K\) are finite subgroups, then \(|HK| = |H|\,|K| / |H \cap K|\).

Proof: there are \(|H|\,|K|\) pairs \((h, k)\), and we count how many pairs give each product. Suppose \(hk = h'k'\). Then \(t = h'^{-1}h = k'k^{-1}\) lies in both \(H\) and \(K\), and \((h', k') = (ht^{-1}, tk)\). Conversely, for every \(t \in H \cap K\), the pair \((ht^{-1}, tk)\) has the same product as \((h, k)\), and different values of \(t\) give different pairs. So each element of \(HK\) arises from exactly \(|H \cap K|\) pairs, and dividing gives the formula. In the \(S_3\) example, \(2 \cdot 2 / 1 = 4\), as found.

Theorem. \(HK\) is a subgroup if and only if \(HK = KH\). In particular \(HK\) is a subgroup whenever \(G\) is abelian, or whenever one of the two subgroups commutes elementwise with the other, or more generally whenever \(gK = Kg\) for every \(g \in H\).

Proof: if \(HK\) is a subgroup, it is closed under inverses, so \(HK = (HK)^{-1} = K^{-1}H^{-1} = KH\). Conversely, if \(HK = KH\), take \(h_1k_1\) and \(h_2k_2\) in \(HK\). Then \(h_1k_1(h_2k_2)^{-1} = h_1 (k_1 k_2^{-1}) h_2^{-1}\), and the element \(k_1k_2^{-1}h_2^{-1}\) of \(KH\) can be rewritten as some \(h_3k_3\), giving \(h_1h_3k_3 \in HK\). The one-step test finishes the proof.

The last condition, \(gK = Kg\) for all \(g\), will turn out to be the definition of a normal subgroup in lesson 9, and the product \(HK\) with \(K\) normal is the starting point of the second isomorphism theorem in lesson 10.

Subgroup lattices

The subgroups of a finite group, ordered by inclusion, can be drawn as a diagram called the subgroup lattice: each subgroup is a node, and a line joins \(H\) below \(K\) when \(H \subset K\) with no subgroup strictly between. For a cyclic group the picture is simply the divisor diagram of its order, by lesson 3: \(\mathbb{Z}_{12}\) has exactly one subgroup of each order 1, 2, 3, 4, 6, 12, and \(\langle a \rangle \subseteq \langle b \rangle\) exactly when the order of the first divides the order of the second.

For \(D_4\) the lattice is more interesting. It has ten subgroups: the trivial group; five subgroups of order 2, namely \(\langle r^2 \rangle\) and the four generated by single reflections; three of order 4, namely the rotations \(\langle r \rangle\) and the two Klein four-groups \(\{e, r^2, s, r^2s\}\) and \(\{e, r^2, rs, r^3s\}\); and \(D_4\) itself. The subgroup \(\langle r^2 \rangle\) lies in all three subgroups of order 4, while each reflection subgroup lies in exactly one of them.

The orders in both pictures have something in common: every subgroup order divides the order of the group. That is Lagrange's theorem, the subject of lesson 7. The code below finds every subgroup of \(D_4\) by brute force, using the finite subgroup test: it tries every subset generated by at most two elements, which suffices here because every subgroup of \(D_4\) is generated by two elements.

from itertools import combinations

def mul(x, y):                       # (a, b) means r^a s^b in D4
    (a, b), (c, d) = x, y
    return ((a + (-1) ** b * c) % 4, (b + d) % 2)

def name(x):
    a, b = x
    rot = {0: 'e', 1: 'r', 2: 'r2', 3: 'r3'}[a]
    return (rot if a else '') + 's' if b else rot

G = [(a, b) for b in (0, 1) for a in range(4)]

def generated(gens):
    H, frontier = {(0, 0)}, [(0, 0)]
    while frontier:
        new = []
        for h in frontier:
            for g in gens:
                x = mul(h, g)
                if x not in H:
                    H.add(x); new.append(x)
        frontier = new
    return frozenset(H)

subs = {generated(c) for k in (1, 2) for c in combinations(G, k)} | {frozenset([(0, 0)])}
for H in sorted(subs, key=lambda H: (len(H), sorted(H))):
    print(len(H), sorted(name(x) for x in H))
print("number of subgroups:", len(subs))
print("every order divides 8:", all(8 % len(H) == 0 for H in subs))

1 ['e']
2 ['e', 's']
2 ['e', 'rs']
2 ['e', 'r2']
2 ['e', 'r2s']
2 ['e', 'r3s']
4 ['e', 'r2', 'r2s', 's']
4 ['e', 'r', 'r2', 'r3']
4 ['e', 'r2', 'r3s', 'rs']
8 ['e', 'r', 'r2', 'r2s', 'r3', 'r3s', 'rs', 's']
number of subgroups: 10
every order divides 8: True

The output lists the ten subgroups by order and confirms that every order divides 8. A quick check on the converse: \(D_4\) has subgroups of every order dividing 8, but that is special to this group. Lesson 7 shows that \(A_4\), of order 12, has no subgroup of order 6.

Subgroups of infinite groups

Infinite groups can have very different subgroup structures. Every subgroup of \(\mathbb{Z}\) is \(n\mathbb{Z}\) for some \(n \ge 0\) (lesson 3), so the subgroups of \(\mathbb{Z}\) correspond to nonnegative integers. By contrast \(\mathbb{Q}\) under addition has a rich variety of subgroups, such as the rationals whose denominators are powers of 2, and there is no simple list of them all. The circle group \(\mathbb{T} = \{z \in \mathbb{C} : |z| = 1\}\) under multiplication contains, for every \(n\), exactly one subgroup of order \(n\): the \(n\)th roots of unity \(\{e^{2\pi i k/n}\}\). In \(GL_n(\mathbb{R})\), the invertible matrices, important subgroups include \(SL_n(\mathbb{R})\) (determinant 1), the orthogonal group \(O(n)\) of distance-preserving linear maps, and the rotation group \(SO(n)\); the dihedral group \(D_m\) sits inside \(O(2)\) as a finite subgroup, exactly as Leonardo's theorem in lesson 5 describes.