Homomorphisms and isomorphisms

So far we have studied groups one at a time. The real power of group theory comes from maps between groups that respect the operation. Such maps, homomorphisms, let us transport information from one group to another, recognize when two groups that look different are really the same, and break a complicated group into simpler pieces. This lesson defines homomorphisms and isomorphisms, works out their basic properties, and proves Cayley's theorem of 1854: every group is, up to renaming, a group of permutations.

Definition and examples

Let \(G\) and \(H\) be groups. A homomorphism is a function \(\varphi : G \to H\) such that

\[ \varphi(ab) = \varphi(a)\varphi(b) \quad \text{for all } a, b \in G. \]

The product on the left is taken in \(G\) and the one on the right in \(H\). In words: it makes no difference whether you combine first and then map, or map first and then combine. Many familiar rules are statements that some map is a homomorphism.

• The determinant \(\det : GL_n(\mathbb{R}) \to \mathbb{R}^\times\), since \(\det(AB) = \det A \det B\).

• The exponential \(\exp : (\mathbb{R}, +) \to (\mathbb{R}_{>0}, \times)\), since \(e^{x+y} = e^x e^y\). Its inverse, the logarithm, is also a homomorphism, which is why logarithm tables turned multiplication into addition for three centuries of navigators and astronomers.

• Reduction modulo \(n\), \(\mathbb{Z} \to \mathbb{Z}_n\), \(k \mapsto k \bmod n\), since the remainder of a sum is the sum of the remainders, reduced.

• The sign \(\operatorname{sgn} : S_n \to \{1, -1\}\), since \(\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}\sigma \operatorname{sgn}\tau\) (lesson 4).

• The map \(D_n \to \{1, -1\}\) sending rotations to 1 and reflections to \(-1\), which records whether a symmetry turns the polygon over.

• For fixed \(g \in G\), conjugation \(c_g : G \to G\), \(c_g(x) = gxg^{-1}\), since \(gxyg^{-1} = (gxg^{-1})(gyg^{-1})\).

• The trivial homomorphism \(G \to H\) sending everything to \(e_H\).

A non-example: \(x \mapsto x + 1\) on \(\mathbb{Z}\) is not a homomorphism, since \((a + b) + 1 \ne (a + 1) + (b + 1)\). Nor is \(x \mapsto x^2\) on \(S_3\): \(((1\,2)(1\,3))^2 = (1\,3\,2)^2 = (1\,2\,3)\), while \((1\,2)^2(1\,3)^2 = e\).

Basic properties

Theorem. Let \(\varphi : G \to H\) be a homomorphism. Then: (i) \(\varphi(e_G) = e_H\); (ii) \(\varphi(a^{-1}) = \varphi(a)^{-1}\), and \(\varphi(a^k) = \varphi(a)^k\) for all integers \(k\); (iii) if \(a\) has finite order \(n\), then the order of \(\varphi(a)\) divides \(n\); (iv) the image of a subgroup of \(G\) is a subgroup of \(H\), and the preimage of a subgroup of \(H\) is a subgroup of \(G\).

Proof: (i) \(\varphi(e) = \varphi(ee) = \varphi(e)\varphi(e)\), and canceling in \(H\) gives \(\varphi(e) = e_H\). (ii) \(\varphi(a)\varphi(a^{-1}) = \varphi(aa^{-1}) = \varphi(e) = e_H\), so \(\varphi(a^{-1})\) is the inverse of \(\varphi(a)\); the power rule follows by induction. (iii) \(\varphi(a)^n = \varphi(a^n) = \varphi(e) = e_H\), and an element whose \(n\)th power is the identity has order dividing \(n\) (lesson 3). (iv) For \(K \le G\), the set \(\varphi(K)\) contains \(e_H\), and \(\varphi(a)\varphi(b)^{-1} = \varphi(ab^{-1}) \in \varphi(K)\), so the one-step test applies. The preimage argument is similar.

Property (iii) is a quick way to rule out homomorphisms. There is no nontrivial homomorphism from \(\mathbb{Z}_3\) to \(\mathbb{Z}_4\): the image of a generator must have order dividing both 3 and 4, so order 1. In general a homomorphism from a cyclic group \(\langle a \rangle\) is determined by where it sends \(a\), and \(\mathbb{Z}_m \to \mathbb{Z}_n\), \(1 \mapsto k\), is a well-defined homomorphism exactly when the order of \(k\) divides \(m\), which gives \(\gcd(m, n)\) homomorphisms in all.

Kernel and image

The kernel of \(\varphi : G \to H\) is \(\ker\varphi = \{g \in G : \varphi(g) = e_H\}\), and the image is \(\varphi(G) = \{\varphi(g) : g \in G\}\). Both are subgroups, by property (iv). For the determinant the kernel is \(SL_n(\mathbb{R})\); for the sign it is \(A_n\); for reduction modulo \(n\) it is \(n\mathbb{Z}\); for the exponential it is \(\{0\}\).

Theorem. A homomorphism is one-to-one if and only if its kernel is \(\{e\}\). More precisely, \(\varphi(a) = \varphi(b)\) if and only if \(a^{-1}b \in \ker\varphi\).

Proof: \(\varphi(a) = \varphi(b) \iff \varphi(a)^{-1}\varphi(b) = e_H \iff \varphi(a^{-1}b) = e_H \iff a^{-1}b \in \ker\varphi\). If the kernel is trivial this forces \(a = b\). Conversely, if \(\varphi\) is one-to-one, only \(e\) can map to \(e_H = \varphi(e)\).

The second statement says, by the coset lemma of lesson 7, that \(\varphi(a) = \varphi(b)\) exactly when \(a\) and \(b\) lie in the same left coset of the kernel. So a homomorphism collapses each coset of its kernel to a single point, and different cosets go to different points. For finite groups this gives \(|G| = |\ker\varphi| \cdot |\varphi(G)|\), the seed of the first isomorphism theorem in lesson 10.

Isomorphisms

An isomorphism is a homomorphism that is a bijection. If one exists, \(G\) and \(H\) are isomorphic, written \(G \cong H\). The inverse of an isomorphism is again a homomorphism: if \(\varphi(a) = x\) and \(\varphi(b) = y\) then \(\varphi(ab) = xy\), so \(\varphi^{-1}(xy) = ab = \varphi^{-1}(x)\varphi^{-1}(y)\). Isomorphic groups have identical Cayley tables after renaming the elements, so for algebraic purposes they are the same group.

Examples: \((\mathbb{R}, +) \cong (\mathbb{R}_{>0}, \times)\) via \(\exp\). The rotation group of a regular \(n\)-gon is isomorphic to \(\mathbb{Z}_n\) via \(r^k \mapsto k\). The group of complex \(n\)th roots of unity is isomorphic to \(\mathbb{Z}_n\) via \(e^{2\pi i k/n} \mapsto k\). \(D_3 \cong S_3\) (lesson 5). \(U(8) \cong \mathbb{Z}_2 \times \mathbb{Z}_2\) and \(U(10) \cong \mathbb{Z}_4\) (lesson 7). Indeed every cyclic group of order \(n\) is isomorphic to \(\mathbb{Z}_n\), and every infinite cyclic group to \(\mathbb{Z}\), via \(a^k \mapsto k\).

To prove that two groups are not isomorphic, find a property that isomorphisms preserve and that one group has and the other lacks. Isomorphisms preserve the order of the group, the order of each element (by (iii) applied to \(\varphi\) and \(\varphi^{-1}\)), the number of elements of each order, being abelian, being cyclic, the size of the center, and the number of subgroups of each order. So \(\mathbb{Z}_4 \not\cong \mathbb{Z}_2 \times \mathbb{Z}_2\) (one has an element of order 4, the other does not), \(\mathbb{Z}_6 \not\cong S_3\) (abelian versus not), and \(D_4 \not\cong Q_8\) (five elements of order 2 versus one). Matching invariants do not by themselves prove isomorphism; for that one must exhibit the map.

Theorem. \(\mathbb{Z}_m \times \mathbb{Z}_n \cong \mathbb{Z}_{mn}\) if and only if \(\gcd(m, n) = 1\).

Proof: by lesson 3 the element \((1, 1)\) has order \(\operatorname{lcm}(m, n)\), and every element \((a, b)\) has order dividing \(\operatorname{lcm}(m, n)\). If \(\gcd(m, n) = 1\) then \(\operatorname{lcm}(m, n) = mn\), so \((1, 1)\) generates and the group is cyclic of order \(mn\). If \(\gcd(m, n) > 1\), every element has order at most \(\operatorname{lcm}(m, n) < mn\), so the group is not cyclic. In number theory this is the Chinese remainder theorem.

Cayley's theorem

Arthur Cayley's paper of 1854 was the first to define a group abstractly, as a set with a multiplication table satisfying the axioms, rather than as a collection of permutations. He immediately showed that nothing was lost.

Theorem (Cayley). Every group \(G\) is isomorphic to a group of permutations. If \(|G| = n\), then \(G\) is isomorphic to a subgroup of \(S_n\).

Proof: for \(g \in G\) define \(\lambda_g : G \to G\) by \(\lambda_g(x) = gx\). It is a bijection of the set \(G\), with inverse \(\lambda_{g^{-1}}\), so \(\lambda_g\) is a permutation of \(G\). The map \(\lambda : G \to \operatorname{Sym}(G)\), \(g \mapsto \lambda_g\), is a homomorphism because \(\lambda_{gh}(x) = ghx = \lambda_g(\lambda_h(x))\), so \(\lambda_{gh} = \lambda_g \circ \lambda_h\). Its kernel is trivial, since \(\lambda_g = \text{id}\) gives \(g = ge = e\). So \(\lambda\) is an isomorphism onto its image, a subgroup of the permutations of \(G\). Numbering the elements of \(G\) as \(1, \dots, n\) identifies this with a subgroup of \(S_n\).

In table language, \(\lambda_g\) is the permutation read off from row \(g\) of the Cayley table, which by the Latin square property of lesson 2 is indeed a permutation. Cayley's theorem justifies the study of permutation groups: every finite group appears inside some \(S_n\). It is not an efficient representation, though. \(D_n\) appears inside \(S_n\) via its action on vertices, while Cayley's construction embeds it in the far larger \(S_{2n}\).

The code below carries out Cayley's construction for \(D_3\), writing each element as the permutation of \(\{0, \dots, 5\}\) given by its row of the table, and checks that \(g \mapsto \lambda_g\) is an injective homomorphism. It also counts the homomorphisms \(\mathbb{Z}_m \to \mathbb{Z}_n\) for a few pairs and compares the count with \(\gcd(m, n)\).

from math import gcd

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

G = [(a, b) for b in (0, 1) for a in range(3)]
idx = {g: i for i, g in enumerate(G)}
lam = {g: tuple(idx[mul(g, x)] for x in G) for g in G}

def compose(p, q):                   # p after q
    return tuple(p[q[i]] for i in range(len(q)))

hom = all(lam[mul(g, h)] == compose(lam[g], lam[h]) for g in G for h in G)
injective = len(set(lam.values())) == len(G)
print("lambda is a homomorphism:", hom, " injective:", injective)
print("lambda_r  =", lam[(1, 0)])
print("lambda_s  =", lam[(0, 1)])

def count_homs(m, n):
    total = 0
    for k in range(n):               # candidate image of 1
        phi = [(k * x) % n for x in range(m)]
        if all(phi[(x + y) % m] == (phi[x] + phi[y]) % n for x in range(m) for y in range(m)):
            total += 1
    return total

for m, n in [(3, 4), (6, 4), (12, 18), (8, 12), (5, 5)]:
    print(f"homs Z{m} -> Z{n}: {count_homs(m, n)}   gcd = {gcd(m, n)}")

lambda is a homomorphism: True  injective: True
lambda_r  = (1, 2, 0, 4, 5, 3)
lambda_s  = (3, 5, 4, 0, 2, 1)
homs Z3 -> Z4: 1   gcd = 1
homs Z6 -> Z4: 2   gcd = 2
homs Z12 -> Z18: 6   gcd = 6
homs Z8 -> Z12: 4   gcd = 4
homs Z5 -> Z5: 5   gcd = 5

In the output, \(\lambda_r\) is a product of two 3-cycles and \(\lambda_s\) a product of three transpositions, matching the figure, and each homomorphism count equals the gcd.

Automorphisms

An isomorphism from a group to itself is an automorphism, and the automorphisms of \(G\) form a group \(\operatorname{Aut}(G)\) under composition. The conjugations \(c_g\) are automorphisms, called inner automorphisms; they are trivial exactly when \(g\) is in the center. For cyclic groups the automorphisms are easy to describe: an automorphism of \(\mathbb{Z}_n\) must send the generator 1 to another generator \(k\), with \(\gcd(k, n) = 1\) by lesson 3, and \(x \mapsto kx\) is then an automorphism. Composition multiplies the values of \(k\), so \(\operatorname{Aut}(\mathbb{Z}_n) \cong U(n)\). For example \(\operatorname{Aut}(\mathbb{Z}_8) \cong U(8)\) is a Klein four-group. The automorphism group of the Klein four-group itself permutes its three nonidentity elements in every possible way and is isomorphic to \(S_3\).