Structural Group Theory

Linear Algebra to Algebraic Foundations

← Back to Section I Overview
Part 1: Linear Equations Part 2: Linear Transformation Part 3: Matrix Algebra Part 4: Determinants Part 5: Vector Spaces Part 6: Eigenvalues & Eigenvectors Part 7: Orthogonality Part 8: Least-Squares Problems Part 9: Symmetry Part 10: Trace and Norms Part 11: Kronecker Product & Tensor Part 12: Woodbury Matrix Identity Part 13: Stochastic Matrix Part 14: Graph Laplacians and Spectral Methods Part 15: Intro to Abstract Algebra Part 16: More Finite Groups Part 17: Structural Group Theory Part 18: Classification of Finite Abelian Groups
Cosets Lagrange's Theorem Normal Subgroups Factor Groups Group Homomorphisms Group Isomorphisms

Cosets: Partitioning the Group

Up to this point, we have treated groups as individual, isolated objects. We have explored the "internal clockwork" of cyclic groups and the "shuffling" mechanics of symmetric groups. However, the true power of group theory lies in structural analysis - understanding how groups relate to one another.

In this page, we shift our focus from "What is a group?" to "How do groups map to each other?" We will develop the tools to partition groups into meaningful blocks (cosets), simplify complex groups into smaller "quotient" structures, and prove that seemingly different groups are actually identical in structure (isomorphism).

In computer science, we often use equivalence relations to categorize data into buckets. In group theory, cosets serve a similar purpose. Given a subgroup \( H \), we can use it to "slice" the parent group \( G \) into disjoint pieces of equal size.

Definition: Cosets Let \(H\) be a nonempty subset of a group \(G\). For any \(a \in G\), we define: \[ \begin{align*} aH &= \{ah \mid h \in H\} (\text{ The left coset of } H \text{ in } G \text{ containing } a. ), \\\\ Ha &= \{ha \mid h \in H\} (\text{ The right coset of } H \text{ in } G \text{ containing } a. ), \\\\ aHa^{-1} &= \{aha^{-1} \mid h \in H\}. \end{align*} \] The element \(a\) is called the coset representative of \(aH\) (or \(Ha\)).
We denote \(|aH|\) (or \(Ha\)) as the number of elements in the set \(aH\) (or \(Ha\)).
Example: The "Clock" Partition (\( 3\mathbb{Z} \) in \( \mathbb{Z} \))

Consider the additive group of integers \( \mathbb{Z} \) and its subgroup \[ H = 3\mathbb{Z} = \{ \dots, -6, -3, 0, 3, 6, \dots \}. \] To find the cosets, we pick an element \( a \in \mathbb{Z} \) and add it to every element in \( H \):

  • 0 + 3\(\mathbb{Z}\) = { \(\cdots\), -6, -3, 0, 3, 6, \(\cdots\) }
  • 1 + 3\(\mathbb{Z}\) = { \(\cdots\), -5, -2, 1, 4, 7, \(\cdots\) }
  • 2 + 3\(\mathbb{Z}\) = { \(\cdots\), -4, -1, 2, 5, 8, \(\cdots\) }
  • 3 + 3\(\mathbb{Z}\) = { \(\cdots\), -3, 0, 3, 6, 9, \(\cdots\) } = 0 + 3\(\mathbb{Z}\)

This illustrates that the cosets are exactly the equivalence classes of the "modulo" relation. In CS terms, this is the mathematical foundation of a hash map where the keys are remainders.

The following properties define how cosets behave as the "building blocks" of a group. These properties establish that cosets aren't just random subsets, but a highly structured partition.

Properties of Cosets

Let \(H\) be a subgroup of \(G\), and \(a, b \in G\). Then:

  1. \(a \in aH\).
  2. \(aH = H\) if and only if \(a \in H\).
  3. \(aH = bH\) if and only if \(a \in bH\).
  4. \(aH = bH\) or \(aH \cap bH = \emptyset\).
  5. \(aH = bH\) if and only if \(a^{-1}b \in H\).
  6. \(|aH| = |bH|\).
  7. \(aH = Ha\) if and only if \(H = aHa^{-1}\).
  8. \(aH\) is a subgroup of \(G\) if and only if \(a \in H\).

Note: Corresponding properties hold for right cosets as well.

From a structural perspective, Property 3 implies that a coset is uniquely determined by any one of its elements (any element can act as a "representative"). Property 4 ensures that these cosets never partially overlap. Combining these with Property 6, we arrive at a powerful conclusion: the left (or right) cosets of \(H\) partition \(G\) into disjoint blocks of equal size. In Computer Science, this is the exact behavior of an equivalence relation used in partitioning algorithms.

Lagrange's Theorem

The properties of cosets we have just explored lead to one of the most fundamental results in finite group theory. If cosets partition a group into disjoint blocks of equal size, then the total number of elements in the group must be a simple multiple of the size of any of its subgroups.

Named after Joseph-Louis Lagrange, this theorem imposes a rigid "divisibility constraint" on the structure of finite groups: a subgroup cannot just be any size; its order must be a divisor of the parent group's order.

Theorem: Lagrange's Theorem

If \(H\) is a subgroup of a finite group \(G\), then \(|H|\) divides \(|G|\). Moreover, the number of distinct left (or right) cosets of \(H\) in \(G\) is \(|G| / |H|\).

Proof:

Let \(a_1 H, \, a_2 H, \, \ldots, \, a_r H\) denote the distinct left cosets of \(H\) in \(G\). For any \(a \in G\), Property 1 guarantees that \(a \in aH\). Since the cosets \(a_1 H, \ldots, a_r H\) exhaust all distinct cosets, we have \(aH = a_i H\) for some \(i\), which means \(a \in a_i H\). Therefore, every element of \(G\) belongs to one of these cosets: \[ G = a_1 H \cup \cdots \cup a_r H. \] By Property 4, this union is disjoint, so: \[ |G| = |a_1 H| + |a_2 H| + \cdots + |a_r H|. \] Since \(\forall i, \, |a_i H| = |H|\) by Property 6, we have \(|G| = r |H|\). Therefore, \[ r = \frac{|G|}{|H|}. \]

Corollaries of Lagrange's Theorem:
  1. The Index Formula:
    If \(G\) is a finite group and \(H\) is a subgroup of \(G\), then the number of distinct cosets (the index) is exactly \[ |G:H| = |G| / |H| \].
  2. Divisibility of Element Orders:
    In a finite group, the order of each element of the group divides the order of the group.

  3. The Identity Constraint:
    Let \(G\) be a finite group and let \(a \in G\). Then, raising any element to the power of the group's order always yields the identity: \[ a^{|G|} = e \]
  4. Fermat's Little Theorem:
    For every integer \(a\) and every prime \(p\): \[ a^p = a \pmod{p} \]
Proof for Fermat's Little Theorem:

By the division algorithm: \[ a = pm + r, \, 0 \leq r < p. \] Thus, \(a \bmod p = r\) and it suffices to prove that \(r^p \bmod p = r\). If \(r =0\), the result is trivial, we assume that \(r \in U(p)\). (Note that \(U(p) = \{1, 2, \ldots, p-1\}\) under multiplication modulo \(p\).)
Then, by the Corollary 3, \(r^{p-1} \bmod p = 1 \) and therefore, \(r^p \bmod p = r\),

In computer science, these corollaries are computational shortcuts. Corollary 3 allows us to reduce massive exponents in modular arithmetic (essential for RSA), and Corollary 4 provides a fast probabilistic test for primality.

Example: Subgroup Attacks and the Pohlig-Hellman Algorithm

In the Diffie-Hellman key exchange, two parties agree on a shared secret by exchanging values in a cyclic group \(G = \langle g \rangle\) of order \(n\). The security relies on the discrete logarithm problem (DLP): given \(g\) and \(h = g^x\), find the exponent \(x\).

Lagrange's Theorem reveals a critical vulnerability when \(n\) is composite. The Pohlig-Hellman algorithm exploits the subgroup structure guaranteed by Lagrange's Theorem to reduce the DLP in \(G\) to smaller DLPs in subgroups of prime-power order.

The Key Insight:

Suppose \(n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\). For each prime power \(p_i^{e_i}\) dividing \(n\), consider the element \[ g_i = g^{n / p_i^{e_i}}. \] By Lagrange's Theorem, \(g_i\) has order exactly \(p_i^{e_i}\) since \[ (g_i)^{p_i^{e_i}} = g^n = e \quad \text{and} \quad (g_i)^{p_i^{e_i - 1}} = g^{n/p_i} \neq e. \] Similarly, define \(h_i = h^{n / p_i^{e_i}}\). Then \[ h_i = (g^x)^{n / p_i^{e_i}} = (g_i)^x, \] so solving \(h_i = (g_i)^{x_i}\) for \(x_i\) is a DLP in a subgroup of order \(p_i^{e_i}\), which yields \(x_i \equiv x \bmod{p_i^{e_i}}\).

Reconstructing the Solution:

Once we have all \(k\) congruences \[ x \equiv x_1 \bmod{p_1^{e_1}}, \quad x \equiv x_2 \bmod{p_2^{e_2}}, \quad \ldots, \quad x \equiv x_k \bmod{p_k^{e_k}}, \] the Chinese Remainder Theorem guarantees a unique solution modulo \(n\).

Complexity Implication:

The complexity of the Pohlig-Hellman algorithm is \[ O\left(\sum_{i=1}^{k} e_i \left(\log n + \sqrt{p_i}\right)\right) \] group operations. When all prime factors \(p_i\) are small (i.e., \(n\) is smooth), this is dramatically faster than the \(O(\sqrt{n})\) complexity of generic algorithms like baby-step giant-step. For example, if \(n = 2^{20}\), the DLP can be solved in roughly \(O(20 \cdot (\log n + \sqrt{2})) \approx O(20 \cdot 21.4)\) operations instead of \(O(\sqrt{2^{20}}) = O(1024)\) operations.

The Defense:

This is precisely why cryptographic protocols choose groups of prime order \(p\). By Lagrange's theorem, such groups have no nontrivial proper subgroups, rendering Pohlig-Hellman inapplicable and forcing attackers to confront the full difficulty of the DLP. We hope you can see the fundamental connection between abstract algebra and computer science.

Reference

A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997, pp. 107-109.

Normal Subgroups: The Requirement for Consistency

We have seen that any subgroup \(H\) partitions \(G\) into cosets. However, the left coset \(aH\) and right coset \(Ha\) are not always identical. This 'mismatch' implies that a product of cosets would depend on our choice of representatives, rendering the group operation ill-defined. To ensure the operation remains well-defined - and thus independent of the representative - we require a subgroup that is invariant under conjugation. This special structure is known as a normal subgroup.

Definition: Normal Subgroups A subgroup \(H\) of a group \(G\) is called a normal subgroup of \(G\) if \[ \forall a \in G, \, aH = Ha. \] we denote this by \(H \trianglelefteq G\).
Examples:
  • Abelian Groups:
    If \(G\) is Abelian, every subgroup is normal. Since \(ah = ha\) for all elements, clearly \(aH = Ha\).
  • The Center \(Z(G)\):
    The center is always normal in \(G\) because its elements commute with everything by definition.
  • The Alternating Group \(A_n\):
    In the previous chapter, we saw that \(|S_n| = 2|A_n|\). This implies that \(A_n\) has index 2 in \(S_n\).
    Theorem: Any subgroup of index 2 is always normal.
    (Why? One coset is \(H\) itself. The other coset must be \(G \setminus H\). Since this partition is unique, left and right cosets must match.)

Checking \(aH = Ha\) for every \(a\) is tedious. In practice, we use the following test.

Theorem: Normal Subgroup Test A subgroup \(H\) of \(G\) is normal in \(G\) if and only if \[ \forall x \in G, \, x H x^{-1} \subseteq H. \]
Proof: If \(H\) is normal in \(G\), then for any \(x \in G\) and \(h \in H\), there is an \(h' \in H\) such that \(xh = h'x\). Multiplying by \(x^{-1}\) on the right gives \[ xhx^{-1} = h' \in H. \] Thus, \(xHx^{-1} \subseteq H\).

Conversely, suppose \(\forall x, \, xHx^{-1} \subseteq H\). Let \(x = a \in G\). Then we have \[ aHa^{-1} \subseteq H \text{ or } aH \subseteq Ha. \] On the other hand, consider \(x = a^{-1}\). Then we have \[ a^{-1}H(a^{-1})^{-1} = a^{-1}Ha \subseteq H. \] Thus, \(Ha \subseteq aH\).
Since \(aH \subseteq Ha\) and \(Ha \subseteq aH\), we conclude \(aH = Ha\).

Factor Groups (Quotient Groups)

We have seen that a normal subgroup \(H\) satisfies \(aH = Ha\) for all \(a \in G\), ensuring that left and right cosets coincide. This property is not merely a curiosity — it is precisely the condition required to define a consistent group operation on the set of cosets. With normality in hand, we can now "collapse" a group into a simpler structure by treating entire cosets as single elements.

Theorem: Factor Groups Let \(G\) be a group and let \(H\) be a normal subgroup of \(G\). The set of cosets: \[ G / H = \{aH \mid a \in G\} \] forms a group under the operation: \[ (aH)(bH) = (ab)H. \] This group is called the factor group (or quotient group) of \(G\) by \(H\). The size of this group is \(|G/H| = |G|/|H|\).
Proof: First, to show that the operation is well-defined, we check if the following function is valid or not: \[ (G / H) \times (G / H) \to G / H. \] Suppose \(aH = a'H\) and \(bH = b'H\) for some elements \(a, a', b, b' \in G\). We must show that \(abH = a'b'H\).
From the assumption: \(aH = a'H \text{ and } bH = b'H \), we have \(a' = ah_1\) and \(b' = bh_2\) for some \(h_1, h_2 \in H\). Here, by Property 2 of Properties of Cosets and \(H \trianglelefteq G\), we have: \[ \begin{align*} a'b'H &= (ah_1)(bh_2) H \\\\ &= ah_1 b H \\\\ &= ah_1 H b \\\\ &= aHb \\\\ &= abH. \end{align*} \] Therefore, the operation is well-defined.

Now, we check group axioms for \(G / H\):
  • Identity: \(eH = H\) serves as the identity because \((aH)(eH) = (ae)H = aH\).
  • Inverse: The inverse of \(aH\) is \(a^{-1}H\) because \((aH)(a^{-1}H) = (aa^{-1})H = eH = H\).
  • Associativity: Inherited directly from \(G\):\((aHbH)cH = (ab)HcH = (ab)cH = a(bc)H = aH(bc)H = aH(bHcH)\).
Example: The Integers Modulo \(n\) (\(\mathbb{Z}/n\mathbb{Z}\))

Let \(G = \mathbb{Z}\) (integers) and \(H = n\mathbb{Z}\) (multiples of \(n\)). Since \(\mathbb{Z}\) is Abelian, \(H\) is normal.
The cosets are: \[ 0+H, \quad 1+H, \quad 2+H, \quad \dots, \quad (n-1)+H. \] The factor group operation tells us how to add these cosets: \[ (a+H) + (b+H) = (a+b) + H. \] Does this look familiar? It is exactly modular arithmetic. The factor group \(\mathbb{Z}/n\mathbb{Z}\) is structurally identical (isomorphic) to the group \(\mathbb{Z}_n\).

In software engineering, we hide implementation details behind an interface. Factor groups do the exact same thing for mathematics. When we form \(G/N\), we are saying, "The internal details of \(N\) don't matter to the macro-behavior of the system." We encapsulate \(N\) into a single identity element and observe how the remaining parts of \(G\) interact. This is the ultimate form of data abstraction.

Group Homomorphisms

While cosets and factor groups allow us to analyze groups as isolated algebraic systems, we often need to investigate the structural relationships between different groups. This section introduces group homomorphisms — mappings that preserve algebraic operations. These functions act as a structural bridge, allowing us to see how the properties of one group are faithfully mirrored in another

Definition: Group Homomorphism A homomorphism \(\phi\) from a group \(G\) to a group \(\overline{G}\) is a mapping from \(G\) into \(\overline{G}\) that preserves the group operation: \[ \forall a, b \in G \, \phi(ab) = \phi(a)\phi(b). \]
Example: The Parity Map

Consider the group of integers \(\mathbb{Z}\) under addition and the group \(G_2 = \{1, -1\}\) under multiplication. Define a map \(\phi: \mathbb{Z} \to G_2\) based on whether a number is even or odd: \[ \phi(n) = \begin{cases} 1 & \text{if } n \text{ is even} \\ -1 & \text{if } n \text{ is odd} \end{cases} \] Is this a homomorphism? We check if \(\phi(a + b) = \phi(a)\phi(b)\).

  • Even + Even = Even: \(\phi(E + E) = 1\) and \(\phi(E)\phi(E) = 1 \cdot 1 = 1\). (Match)
  • Odd + Odd = Even: \(\phi(O + O) = 1\) and \(\phi(O)\phi(O) = (-1) \cdot (-1) = 1\). (Match)
  • Even + Odd = Odd: \(\phi(E + O) = -1\) and \(\phi(E)\phi(O) = 1 \cdot (-1) = -1\). (Match)

Since the equation holds for all cases, \(\phi\) is a homomorphism. It "translates" the logic of addition into multiplication without breaking the truth of the statements.

Definition: Kernel of a Homomorphism The kernel of a homomorphism \(\phi\) from a group \(G\) to a group with identity \(e\) is the set: \[ \text{Ker }\phi = \{x \in G \mid \phi(x) = e\}. \]
Example: The Determinant Mapping

Let \(GL(n, \mathbb{R})\) be the General Linear Group (invertible \(n \times n\) matrices) and \(\mathbb{R}^*\) be the group of nonzero real numbers under multiplication.

Recall the property of determinants: \[ \det(AB) = \det(A)\det(B). \] This equation is exactly the homomorphism property. It tells us that the determinant mapping \(\det: GL(n, \mathbb{R}) \to \mathbb{R}^*\) defined by \(A \mapsto \det(A)\) is a homomorphism.

The kernel of this homomorphism is \[ \text{Ker } \det = \{A \in GL(n, \mathbb{R}) \mid \det(A) = 1\} \] This is the Special Linear Group, denoted \(SL(n, \mathbb{R})\). (Note that \(SL(n, \mathbb{R})\) is a normal subgroup of \(GL(n, \mathbb{R})\).)

Example: The Natural Projection \(\mathbb{Z} \to \mathbb{Z}_n\)

Let \(n\) be a fixed positive integer greater than 1. If \(a \bmod n = a'\) and \(b \bmod n = b'\), then \[ (a + b) \bmod n = (a' + b') \bmod n. \] This shows that the mapping \(\phi: \mathbb{Z} \to \mathbb{Z}_n\) defined by \(\phi(m) = m \bmod n\) is a homomorphism.

The kernel consists of all integers that map to \(0\): \[ \text{Ker }\phi = \{m \in \mathbb{Z} \mid m \bmod n = 0\} = n\mathbb{Z} = \langle n \rangle. \]

Properties of Elements under Homomorphism: Let \(\phi\) be a homomorphism from a group \(G\) to a group \(\overline{G}\) and let \(g\) be an element of \(G\). Then
  1. \(\phi\) carries the identity of \(G\) to the identity of \(\overline{G}\).
  2. \(\phi(g^n) = (\phi(g))^n\) for all \(n \in \mathbb{Z}\).
  3. If \(|g|\) is finite, then \(|\phi(g)|\) divides \(|g|\), and if \(|G|\) is finite then \(|\phi(g)|\) divides \(|g|\) and \(|\phi(G)|\)
  4. \(\text{Ker } \phi\) is a subgroup of \(G\).
  5. \(\phi(a) = \phi(b)\) if and only if \(a\text{Ker }\phi = b\text{Ker }\phi\).
    6. Properties of Elements under Homomorphism:
  6. If \(\phi(g) = \overline{g}\), then \(\phi^{-1}(\overline{g}) = \{x \in G \mid \phi(x) = \overline{g}\} = g \text{Ker } \phi\).

Note:
For property 1, let \(e\) be the identity in \(G\) and \(\bar{e}\) be the identity in \(\overline{G}\). Since \(\phi(e) \in \overline{G}\) and \(e = ee\), we have: \[ \bar{e}\phi(e) = \phi(e) = \phi(ee) = \phi(e)\phi(e). \] Thus, by right cancellation, \(\bar{e} = \phi(e)\).

Properties of Subgroups under Homomorphism: Let \(\phi\) be a homomorphism from a group \(G\) to a group \(\overline{G}\) and let \(H\) be a subgroup of \(G\). Then
  1. \(\phi(H) = \{\phi(h) \mid h \in H\}\) is a subgroup of \(\overline{G}\)
  2. If \(H\) is cyclic, then \(\phi(H)\) is cyclic.
  3. If \(H\) is Abelian, then \(\phi(H)\) is Abelian.
  4. If \(H\) is normal in \(G\), then \(\phi(H)\) is normal in \(\phi(G)\).
  5. If \(|\text{Ker }\phi| = n\), then \(\phi\) is an \(n\)-to-\(1\) mapping from \(G\) onto \(\phi(G)\).
  6. If \(H\) is finite, then \(|\phi(H)|\) divides \(|H|\).
  7. \(\phi(Z(G))\) is a subgroup of \(Z(\phi(G))\).
  8. If \(\overline{K}\) is a subgroup of \(\overline{G}\) then \(\phi^{-1}(\overline{K}) = \{k \in G \mid \phi(k) \in \overline{K}\}\) is a subgroup of \(G\).
  9. If \(\overline{K}\) is a normal subgroup of \(\overline{G}\), then \(\phi^{-1}(\overline{K}) = \{k \in G \mid \phi(k) \in \overline{K}\}\) is a normal subgroup of \(G\).
  10. If \(\phi\) is onto and \(\text{Ker }\phi = \{e\}\), then \(\phi\) is an isomorphism from \(G\) to \(\overline{G}\).

Property 5 (The \(n\)-to-1 Mapping) states that when \(|\text{Ker }\phi| = n\), exactly \(n\) elements of \(G\) map to each element in the image \(\phi(G)\).

To see why, recall Property 6 of Elements under Homomorphism: if \(\phi(g) = \overline{g}\), then \[ \phi^{-1}(\overline{g}) = \{x \in G \mid \phi(x) = \overline{g}\} = g \text{Ker } \phi. \] This tells us that the set of all elements mapping to \(\overline{g}\) is precisely the coset \(g \text{Ker } \phi\).

By Property 6 of Cosets, all cosets have the same number of elements. Since \(e \text{Ker } \phi = \text{Ker } \phi\) is itself a coset, we have: \[ |\phi^{-1}(\overline{g})| = |g \text{Ker } \phi| = |\text{Ker } \phi| = n. \] Therefore, for every element \(\overline{g} \in \phi(G)\), there are exactly \(n\) elements in \(G\) that map to \(\overline{g}\) (aka preimages).

If \(H\) is finite, then \(\phi\) restricted to \(H\) is an \(m\)-to-1 mapping where \(m = |H \cap \text{Ker }\phi|\). By counting: \[ |H| = m \cdot |\phi(H)| \implies |\phi(H)| = \frac{|H|}{m}, \] which shows that \(|\phi(H)|\) divides \(|H|\).



Recall from Example: The Determinant Mapping that \[ \text{Ker } \det = SL(n, \mathbb{R}). \] We claim that \(SL(n, \mathbb{R})\) is a normal subgroup of \(GL(n, \mathbb{R})\). This is actually a special case of Property 9, where \(\overline{K} = \{e\}\). In general, we have the following theorem:

Theorem: Kernels are Normal Let \(\phi\) be a group homomorphism from \(G\) to \(\overline{G}\). Then \(\text{Ker } \phi\) is a normal subgroup of \(G\).

Thus, \(SL(n, \mathbb{R}) \trianglelefteq GL(n, \mathbb{R})\).

Note: The converse of this theorem is also true: every normal subgroup of a group \(G\) is the kernel of some homomorphism of \(G\).

Group Isomorphisms

When a homomorphism is so perfect that it creates a one-to-one correspondence between every element and every operation, we call it an isomorphism. If an isomorphism exists, the two groups are "structurally identical", which means that though their elements may look different (like integers vs. rotations), their underlying "DNA" is exactly the same.

Definition: Group Isomorphism An isomorphism \(\phi\) from a group \(G\) to a group \(\overline{G}\) is a one-to-one and onto mapping (or function) from \(G\) to \(\overline{G}\) that preserves the group operation. That is, \[ \forall a, b \in G, \, \phi(ab) = \phi(a)\phi(b). \] If there is an isomorphism from \(G\) onto \(\overline{G}\), we say that \(G\) and \(\overline{G}\) are isomorphic and denoted by \(G \cong \overline{G}\).
Example: Logarithms (The Slide Rule Principle)

Consider the additive group of real numbers \((\mathbb{R}, +)\) and the multiplicative group of positive real numbers \((\mathbb{R}^+, \times)\).
The function \(\phi(x) = e^x\) is an isomorphism between them: \[ \phi(a + b) = e^{a+b} = e^a \cdot e^b = \phi(a) \cdot \phi(b) \] This isomorphism tells us that addition in the world of exponents is identical to multiplication in the world of bases. This is the mathematical principle behind the Slide Rule: by transforming numbers into lengths (logs), we can multiply them simply by adding the lengths.

Properties of Isomorphisms Acting on Elements: Suppose that \(\phi\) is an isomorphism from a group \(G\) onto a group \(\overline{G}\). Then
  1. \(\phi\) carries the identity of \(G\) to the identity of \(\overline{G}\).
  2. For every integer \(n\) and for every group element \(a \in G\), \(\phi(a^n) = (\phi(a))^n\).
  3. For any elements \(a, b \in G\), \(a\) and \(b\) commute if and only if \(\phi(a)\) and \(\phi(b)\) commute.
  4. \(G = \langle a \rangle\) if and only if \(\overline{G} = \langle \phi(a) \rangle\).
  5. \(\forall a \in G, \, |a| = |\phi(a)|\).
  6. For a fixed integer \(k\) and a fixed group element \(b \in G\), the equation \(x^k = b\) has the same number of solutions in \(G\) as does the equation \(x^k = \phi(b) \in \overline{G}\).
  7. If \(G\) is finite, then \(G\) and \(\overline{G}\) have exactly the same number of elements of every order.

Property 4 (Generators Map to Generators) states that an isomorphism between cyclic groups takes a generator to a generator. That is, \(a\) is a generator of \(G\) if and only if \(\phi(a)\) is a generator of \(\overline{G}\). Moreover, we can say that if \(G\) or \(\overline{G}\) is cyclic and the other is not, then immediately we conclude that the groups \(G\) or \(\overline{G}\) are not isomorphic.

Properties of Isomorphisms Acting on Groups: Suppose that \(\phi\) is an isomorphism from a group \(G\) onto a group \(\overline{G}\). Then
  1. \(\phi^{-1}\) is an isomorphism from \(\overline{G}\) onto \(G\).
  2. \(G\) is Abelian if and only if \(\overline{G}\) is Abelian.
  3. \(G\) is cyclic if and only if \(\overline{G}\) is cyclic.
  4. If \(K\) is a subgroup of \(G\), then \(\phi(K) = \{\phi(k) \mid k \in K\}\) is a subgroup of \(\overline{G}\).
  5. If \(\overline{K}\) is a subgroup of \(\overline{G}\), then \(\phi^{-1}(\overline{K}) = \{g \in G \mid \phi(g) \in \overline{K}\}\) is a subgroup of \(G\).
  6. \(\phi(Z(G)) = Z(\overline{G})\).

Again, if two groups are isomorphic, then the two groups are structurally equivalent. In other words, isomorphism preserves all group theoritic properties.

Also, certain kinds of isomorphism have been given special names:

Definition: Automorphism An isomorphism from a group \(G\) onto itself is called an automorphism of \(G\). The set of all automorphisms of \(G\) forms a group under function composition, denoted \(\text{Aut}(G)\).

One of the simplest examples of an automorphism appears in \(\mathbb{R}^2 = \{(a, b) \mid a, b \in \mathbb{R}\}\) under componentwise addition. The map \(\phi(a, b) = (b, a)\) is an automorphism of \(\mathbb{R}^2\). Geometrically, this is the reflection of each point in the plane across the line \(y = x\). Indeed, any reflection across a line through the origin and any rotation about the origin are automorphisms of \(\mathbb{R}^2\). In general, every invertible linear transformation of a vector space \(V\) to itself is an automorphism of \(V\). This is one reason why linear transformations appear everywhere in mathematics.

Definition: Inner Automorphism Induced by \(a\) Let \(G\) be a group, and let \(a \in G\). The function \(\phi_a\) defined by: \[ \forall x \in G, \, \phi_a (x) = axa^{-1} \] is called the inner automorphism of \(G\) induced by \(a\). The set of all inner automorphisms of \(G\) forms a group under composition, denoted \(\text{Inn}(G)\).
Example: Inner Automorphism in \(S_3\)

Consider the symmetric group \(S_3\) and let \(a = (1\, 2)\). The inner automorphism \(\phi_a\) induced by \(a\) is defined by: \[ \phi_a(x) = (1\, 2) \, x \, (1\, 2)^{-1} = (1\, 2) \, x \, (1\, 2). \] Let us compute \(\phi_a\) for each element of \(S_3\):

  • \(\phi_a(\epsilon) = (1\, 2)\, \epsilon \,(1\, 2) = \epsilon\)
  • \(\phi_a((1\, 2)) = (1\, 2)(1\, 2)(1\, 2) = (1\, 2)\)
  • \(\phi_a((1\, 3)) = (1\, 2)(1\, 3)(1\, 2) = (2\, 3)\)
  • \(\phi_a((2\, 3)) = (1\, 2)(2\, 3)(1\, 2) = (1\, 3)\)
  • \(\phi_a((1\, 2\, 3)) = (1\, 2)(1\, 2\, 3)(1\, 2) = (1\, 3\, 2)\)
  • \(\phi_a((1\, 3\, 2)) = (1\, 2)(1\, 3\, 2)(1\, 2) = (1\, 2\, 3)\)

Notice that \(\phi_a\) swaps \((1\, 3) \leftrightarrow (2\, 3)\) and \((1\, 2\, 3) \leftrightarrow (1\, 3\, 2)\), while fixing \(\epsilon\) and \((1\, 2)\). This is a nontrivial automorphism of \(S_3\).

Note:
\(\text{Aut(G)}\) and \(\text{Inn(G)}\) are both groups under the operation of function composition.

Theorem: Cayley's Theorem Every group is isomorphic to a group of permutations.
Proof:

From any group \(G\), we construct a group \(\overline{G}\) of permutations that is isomorphic to \(G\). For any \(g \in G\), define a mapping \(T_g: G \to G\) by \(T_g (x) = gx\) for any \(x \in G\).

Let \(y \in G\). Since \(T_g(x) = T_g(y)\) implies \(gx = gy\), by left cancellation we have \(x =y\). Thus \(T_g\) is one-to-one. Also, \(T_g ( g^{-1} y) = y\), so \(T_g\) is onto. Thus, \(T_g\) is a permutation on the set of elements of \(G\).

Now, let \(\overline{G} = \{T_g \mid g \in G \}\). Then we claim that \(\overline{G}\) is a group under the operation of function composition. To verify this, we first observe that \(\forall g, h \in G\), \[ T_g T_h (x) = T_g (T_h(x)) = T_g(hx) = g(hx) = (gh)x = T_{gh}(x). \] Note that \(T_e\) is the identity since \[T_e (x) = ex =x \] and \((T_g)^{-1} = T_{g^{-1}}\) since \[ T_g \circ (T_g)^{-1} = T_e = T_{gg^{-1}} = T_g \circ T_{g^{-1}}. \] Since function composition is associative, we conclude that \(\overline{G}\) satisfies all the conditions to be a group.

For any \(g \in G\), define \(\phi (g) = T_g\). If \(T_g = T_h\), then \(T_g(e) = T_h (e)\), or \(ge = he\). Thus, \(g = h\) and \(\phi\) is one-to-one. Also, \(\phi\) is onto by the way \(\overline{G}\) was constructed.

Finally, let \(a, b \in G\). Then \[ \phi(ab) = T_{ab} = T_a T_b = \phi(a)\phi(b). \] Thus, \(\phi\) preserves operations.

Therefore, \(\phi\) is an isomorphism between \(G\) and \(\overline{G}\).

Theorem: First Isomorphism Theorem (TFIT) Let \(\phi\) be a group homomorphism from \(G\) to \(\overline{G}\). Then the mapping from \(G / \text{Ker }\phi\) to \(\phi(G)\), given by \(g \text{Ker } \phi \to \phi(g)\), is an isomorphism. In symbols, \[ G / \text{Ker } \phi \cong \phi(G). \]
Proof:

Let \(\psi\) be the correspondence \(g \text{Ker } \phi \to \phi(g)\).
That \(\psi\) is well-defined and one-to-one follows directly from Property 5 of Elements under Homomorphism: \[ \phi(a) = \phi(b) \iff a\text{Ker }\phi = b\text{Ker }\phi. \] This ensures that the image depends only on the coset, not the representative, and that distinct cosets map to distinct values.

To show that \(\psi\) is operation-preserving, observe that: \[ \begin{align*} &\psi(x \text{Ker } \phi \, y \text{Ker } \phi) \\\\ &= \psi(xy \text{Ker }\phi) \\\\ &= \phi(xy) \\\\ &= \phi(x)\phi(y) \\\\ &= \psi(x \text{Ker }\phi)\psi(y \text{Ker }\phi). \end{align*} \] Finally, \(\psi\) is onto \(\phi(G)\) by the definition of the mapping.
Since \(\psi\) is well-defined, one-to-one, onto, and operation-preserving, it is an isomorphism.

In short, the First Isomorphism Theorem says that every homomorphism is essentially a factor group construction. When we map \(G \to \overline{G}\) via \(\phi\), we are implicitly doing three things:

  1. Collapsing: identifying all elements of \(\text{Ker }\phi\) as the identity.
  2. Partitioning: grouping the elements of \(G\) into cosets of \(\text{Ker }\phi\).
  3. Relabeling: matching each coset to its corresponding element in \(\phi(G)\).

We immediately obtain following corollaries from TFIT.

Corollaries: If \(\phi\) is a homomorphism from a finite group \(G\) to \(\overline{G}\), then
  • \(|G| / |\text{Ker } \phi | = | \phi(G) |\).
  • \(|\phi(G)|\) divides \(|G|\) and \(|\overline{G}|\).
Example: \(\mathbb{Z}/\langle n \rangle \cong \mathbb{Z}_n\)

Recall the natural projection \(\phi: \mathbb{Z} \to \mathbb{Z}_n\) defined by \(\phi(m) = m \bmod n\), whose kernel is \(\text{Ker }\phi = \langle n \rangle\).

By the First Isomorphism Theorem: \[ \mathbb{Z} / \langle n \rangle \cong \phi(\mathbb{Z}) = \mathbb{Z}_n. \] This confirms that the factor group \(\mathbb{Z}/\langle n \rangle = \mathbb{Z}/n\mathbb{Z}\) and the cyclic group \(\mathbb{Z}_n\) are structurally identical.