Group Homomorphisms and Isomorphisms: Structure-Preserving Maps

Terminology

Term	Definition
Homomorphism	A function $\phi: G \to H$ between groups that preserves the operation: $\phi(a \star b) = \phi(a) \cdot \phi(b)$
Isomorphism	A bijective homomorphism. Two groups are isomorphic ($G \cong H$) if such a map exists.
Kernel	$\ker(\phi) = \{g \in G : \phi(g) = e_H\}$, the set of elements mapped to the identity of $H$
Image	$\text{im}(\phi) = \{\phi(g) : g \in G\}$, the set of all outputs of $\phi$
First Isomorphism Theorem	$G / \ker(\phi) \cong \text{im}(\phi)$: the quotient of $G$ by the kernel is isomorphic to the image
Quotient group	$G / N$: the group formed by cosets of a normal subgroup $N$
Normal subgroup	A subgroup $N$ where $gNg^{-1} = N$ for all $g \in G$, enabling quotient group construction
Injective / Surjective	Injective (one-to-one): distinct inputs give distinct outputs. Surjective (onto): every element in the codomain is hit.

What & Why

A homomorphism is a function between two groups that respects their structure. If you operate in the source group and then map, you get the same result as mapping first and then operating in the target group. This "structure preservation" is the mathematical formalization of a concept programmers use constantly: interfaces, adapters, and type conversions that preserve behavior.

Formally, $\phi: (G, \star) \to (H, \cdot)$ is a homomorphism if for all $a, b \in G$ :

$\phi(a \star b) = \phi(a) \cdot \phi(b)$

When $\phi$ is also a bijection, it is an isomorphism, and we say $G \cong H$ : the two groups are "the same" in terms of algebraic structure, even if their elements look different.

Why does this matter for CS?

Type system morphisms: a function that converts between two data types while preserving operations (e.g., serialization that preserves concatenation) is a homomorphism. Type-safe conversions are structure-preserving maps.
Database schema mappings: migrating data between schemas while preserving relational constraints is a homomorphism between algebraic structures.
Code reuse through abstraction: when two modules have isomorphic interfaces, code written for one works for the other. This is the algebraic reason generic programming works.
Cryptographic hash functions: a hash $h$ where $h(a \cdot b) = h(a) \cdot h(b)$ is a homomorphism, enabling homomorphic signatures and commitments.

How It Works

The Homomorphism Property

Kernel and Image

The kernel of $\phi$ measures how much information the homomorphism "loses":

$\ker(\phi) = \{g \in G : \phi(g) = e_H\}$

Key facts:

$\ker(\phi)$ is always a normal subgroup of $G$
$\phi$ is injective (one-to-one) if and only if $\ker(\phi) = \{e_G\}$
The image $\text{im}(\phi)$ is always a subgroup of $H$

Example: Parity Homomorphism

Define $\text{sgn}: S_n \to \{+1, -1\}$ mapping each permutation to its sign. This is a homomorphism because the sign of a composition equals the product of signs:

$\text{sgn}(\sigma \circ \tau) = \text{sgn}(\sigma) \cdot \text{sgn}(\tau)$

The kernel is the alternating group $A_n$ (all even permutations), and the image is $\{+1, -1\}$. By the First Isomorphism Theorem: $S_n / A_n \cong \{+1, -1\}$.

The First Isomorphism Theorem

This is one of the most powerful results in algebra:

$G / \ker(\phi) \cong \text{im}(\phi)$

In programming terms: if you have a lossy transformation $\phi$, the "equivalence classes" of inputs that map to the same output form a group that is structurally identical to the set of outputs. This is exactly what happens when you define equality by hash value: objects with the same hash form equivalence classes, and the set of hash values inherits algebraic structure from the original objects.

Complexity Analysis

Operation	Time	Notes
Verify homomorphism (finite groups)	$O(\|G\|^2)$	Check $\phi(ab) = \phi(a)\phi(b)$ for all pairs
Compute kernel	$O(\|G\|)$	Evaluate $\phi(g)$ for each $g$ and check against $e_H$
Compute image	$O(\|G\|)$	Collect $\{\phi(g) : g \in G\}$ in a set
Check isomorphism (brute force)	$O(\|G\|! \cdot \|G\|^2)$	Try all bijections, verify homomorphism property
Check isomorphism (practical)	Polynomial for many cases	Compare order profiles, use canonical forms

The graph isomorphism problem (closely related to group isomorphism) was shown by Babai (2015) to be solvable in quasi-polynomial time $2^{O((\log n)^c)}$, one of the major results in computational complexity.

Implementation

ALGORITHM VerifyHomomorphism(G_elements, H_elements, G_op, H_op, phi)
INPUT:  G_elements: array of elements of group G
        H_elements: array of elements of group H
        G_op: operation table for G
        H_op: operation table for H
        phi: function mapping G elements to H elements
OUTPUT: TRUE if phi is a homomorphism, FALSE otherwise

BEGIN
  // Check that phi maps into H
  FOR EACH g IN G_elements DO
    IF phi(g) NOT IN H_elements THEN
      RETURN FALSE
    END IF
  END FOR

  // Check the homomorphism property for all pairs
  FOR EACH a IN G_elements DO
    FOR EACH b IN G_elements DO
      left  := phi(G_op(a, b))       // map the product
      right := H_op(phi(a), phi(b))  // product of the maps
      IF left != right THEN
        RETURN FALSE
      END IF
    END FOR
  END FOR

  RETURN TRUE
END

ALGORITHM ComputeKernel(G_elements, phi, identity_H)
INPUT:  G_elements: array of elements of group G
        phi: homomorphism from G to H
        identity_H: identity element of H
OUTPUT: list of elements in the kernel of phi

BEGIN
  kernel := empty list

  FOR EACH g IN G_elements DO
    IF phi(g) = identity_H THEN
      APPEND g TO kernel
    END IF
  END FOR

  RETURN kernel
END

ALGORITHM CheckIsomorphism(G_elements, H_elements, G_op, H_op)
INPUT:  two finite groups (G, G_op) and (H, H_op)
OUTPUT: TRUE if G is isomorphic to H, FALSE otherwise

BEGIN
  // Quick rejection: groups of different sizes cannot be isomorphic
  IF LENGTH(G_elements) != LENGTH(H_elements) THEN
    RETURN FALSE
  END IF

  // Quick rejection: compare order profiles
  G_orders := SORT([order_of(g, G_op) FOR g IN G_elements])
  H_orders := SORT([order_of(h, H_op) FOR h IN H_elements])
  IF G_orders != H_orders THEN
    RETURN FALSE
  END IF

  // Try to construct a bijection that preserves the operation
  // (simplified: try mapping generators and extending)
  FOR EACH candidate_map IN generator_based_bijections(G, H) DO
    IF VerifyHomomorphism(G_elements, H_elements, G_op, H_op, candidate_map) THEN
      RETURN TRUE
    END IF
  END FOR

  RETURN FALSE
END

Real-World Applications

Type system design: a type conversion function that preserves operations (e.g., converting between numeric types while preserving arithmetic) is a homomorphism. Type safety guarantees are algebraic structure preservation.
Database schema migration: mapping data from one schema to another while preserving referential integrity and constraints is a structure-preserving map between relational algebras.
Homomorphic encryption: encryption schemes where $E(a) \cdot E(b) = E(a + b)$ allow computation on encrypted data. The encryption function is literally a homomorphism.
Compiler optimizations: abstract interpretation maps concrete program states to abstract domains via homomorphisms, enabling sound static analysis.
API adapters and wrappers: the Adapter design pattern creates an isomorphism between two interfaces, allowing code written for one to work with the other.
Hashing: a hash function $h$ where $h(a \| b) = h(a) \oplus h(b)$ (like XOR-based checksums) is a homomorphism from the monoid of strings to a finite group.

Key Takeaways

A homomorphism preserves group structure: $\phi(a \star b) = \phi(a) \cdot \phi(b)$. An isomorphism is a bijective homomorphism.
The kernel measures information loss: $\ker(\phi) = \{e\}$ means the map is injective (lossless)
The First Isomorphism Theorem ($G/\ker(\phi) \cong \text{im}(\phi)$) is the algebraic version of "equivalence classes of inputs correspond to distinct outputs"
Isomorphic groups are structurally identical, which is why generic programming works: code depends on structure, not on specific element representations
Homomorphisms appear in type conversions, schema migrations, homomorphic encryption, and abstract interpretation