Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 68 ยท Algebraic Structures and Boolean Algebra

Homomorphisms, Isomorphisms and Automorphisms

Learn structure-preserving maps between groups: homomorphisms, kernels, isomorphisms, automorphisms, plus semigroups and monoids, all checked by Python.

Two algebraic systems can look different and still behave identically. Clock arithmetic mod 6 and the pairs (a mod 2, b mod 3) are made of different objects, yet adding in one mirrors adding in the other. To make that idea precise, mathematicians study maps that respect the operation: translate first and combine, or combine first and translate, and you get the same answer.

This lesson builds on groups. You will meet homomorphisms (structure-preserving maps), their kernels, isomorphisms (perfect translations), automorphisms (a group translated onto itself), and two weaker structures, semigroups and monoids, that appear all over programming. Every claim is checked by brute force.

Homomorphisms

Let (G, โˆ˜) and (H, โˆ—) be groups. A function f: G โ†’ H is a homomorphism if

TEXT
f(a โˆ˜ b) = f(a) โˆ— f(b)    for all a, b in G

The left side combines inside G and then maps; the right side maps and then combines inside H. Two facts follow at once and are worth memorizing:

  • f sends the identity to the identity: f(e_G) = e_H.
  • f sends inverses to inverses: f(aโปยน) = f(a)โปยน.

Examples you already know: reducing mod n is a homomorphism from (Z, +) to (Z_n, +); the exponential x โ†ฆ e^x is a homomorphism from (R, +) to (Rโบ, ร—) because e^(x+y) = e^x ยท e^y; the length of a string is a homomorphism from strings under concatenation to (N, +).

Because the group is finite, we can test the defining equation on every pair. The code below checks four candidate maps between small groups.

Python Testing the homomorphism condition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The shift x + 1 fails because it does not send 0 to 0: a homomorphism must preserve the identity. The squaring map fails too. Multiplying by 3 passes, which tells us homomorphisms need not be one-to-one or onto, and leads to the next idea.

The kernel and the image

Two sets describe what a homomorphism does:

  • The image f(G) is everything in H that is hit. It is always a subgroup of H.
  • The kernel ker f is everything in G that is sent to the identity of H. It is always a subgroup of G.

The kernel measures how much information f throws away. In fact, f is one-to-one exactly when its kernel is just . When the kernel is larger, f glues together the elements that differ by a kernel element, and the first isomorphism theorem says that the group you get by gluing has the same size as the image:

TEXT
|G| = |ker f| ยท |image f|

That formula is Lagrange's theorem in disguise, and it works as a quick sanity check on any computed homomorphism.

Python Kernel, image and the size formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Map 5x mod 6 has a trivial kernel [0], so it loses nothing: it is a perfect relabeling. Map 3x mod 6 collapses three pairs of elements and has a kernel of size 2.

Isomorphisms

A homomorphism that is also bijective (one-to-one and onto) is an isomorphism. Two groups with an isomorphism between them are isomorphic, written G โ‰… H. As far as group theory goes, they are the same group in different clothes: any statement about the operation true in one is true in the other.

To show two groups are not isomorphic you look for a property an isomorphism must preserve and that differs: the number of elements, being abelian, the number of elements of each order, or the existence of a generator. These invariants are quick to compute.

Consider the four-element groups. Z_4 and the Klein four-group Z_2 ร— Z_2 (pairs added componentwise mod 2) both have order 4 and are abelian, but are they the same? Count element orders.

Python Are two groups isomorphic? Compare invariants and search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Z_4 has an element of order 4, while every non-identity element of the Klein group has order 2, so they are different groups. Z_6 and Z_2 ร— Z_3 match, and the translation x โ†ฆ (x mod 2, x mod 3) is the Chinese Remainder Theorem from modular arithmetic viewed as an isomorphism. In general Z_m ร— Z_n โ‰… Z_{mn} exactly when gcd(m, n) = 1.

Brute-force search over all bijections is fine for tiny groups (it tries up to n! maps), but real proofs use invariants.

Automorphisms

An automorphism is an isomorphism from a group onto itself. It is a symmetry of the structure: a relabeling of the elements that preserves every product. The identity map is always an automorphism, and the automorphisms of a group form a group under composition, called Aut(G).

For the cyclic group Z_n, the automorphisms are exactly the maps x โ†ฆ kx where k is coprime to n, so Aut(Z_n) has ฯ†(n) elements (Euler's totient). For the Klein four-group, any permutation of the three non-identity elements works, giving a group with 6 elements.

Python Counting automorphisms

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Semigroups and monoids

Sometimes only some of the group axioms hold. Dropping them one at a time gives a ladder of structures:

Structure Closure Associative Identity Inverses
Magma yes
Semigroup yes yes
Monoid yes yes yes
Group yes yes yes yes

Programmers use monoids constantly: strings under concatenation (identity ""), lists under + (identity []), numbers under + (identity 0) or max (identity negative infinity), and functions under composition (identity: the identity function). Associativity is exactly what lets you split a big fold into chunks, reduce each chunk in parallel, and combine the results, the idea behind MapReduce.

A monoid homomorphism is a map with f(a โˆ˜ b) = f(a) โˆ— f(b) and f(e) = e'. Note that for monoids the identity condition must be demanded separately, since there are no inverses to force it. len is a monoid homomorphism from strings to (N, +).

Python Semigroups, monoids and chunked reduction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 6 questions

of 6 answered You scored / 6 ยท perfect!

  1. 1. What must a homomorphism f from (G, โˆ˜) to (H, โˆ—) satisfy?

    A homomorphism respects the operation: mapping a product gives the product of the images. It need not be one-to-one or onto.
  2. 2. The map f(x) = x + 1 from (Z6, +) to itself is not a homomorphism. Why?

    Every homomorphism between groups must send identity to identity. f(0) = 1, so the condition fails.
  3. 3. A homomorphism has kernel {e}. What does that tell you?

    If only the identity maps to the identity, no two different elements can have the same image, so f is injective.
  4. 4. Z4 and Z2 ร— Z2 both have four elements and are abelian. Why are they not isomorphic?

    Isomorphisms preserve element orders. 1 has order 4 in Z4, but every non-identity pair in Z2 ร— Z2 has order 2.
  5. 5. How many automorphisms does the group (Z8, +) have?

    Automorphisms are x -> kx with k coprime to 8, so k in {1, 3, 5, 7}. That is phi(8) = 4 maps.
  6. 6. Which structure has closure, associativity and an identity but not necessarily inverses?

    A monoid is a semigroup with an identity. Strings under concatenation are a standard example.

Summary

  • A homomorphism satisfies f(a โˆ˜ b) = f(a) โˆ— f(b); it automatically preserves the identity and inverses.
  • The kernel (elements sent to the identity) is a subgroup; f is injective exactly when the kernel is trivial, and |G| = |ker f| ยท |image f|.
  • An isomorphism is a bijective homomorphism; isomorphic groups are the same structure. Non-isomorphism is shown with invariants such as element orders.
  • Automorphisms are isomorphisms from a group to itself; Aut(Z_n) has ฯ†(n) elements.
  • Dropping group axioms gives semigroups (associative) and monoids (associative with identity), which underlie folds and parallel reductions.

Next: Finite Automata and Regular Languages, where monoids reappear as the transitions of a machine.