15 Groups, Homomorphism, Isomorphism, Preservation of Identity and Inverses

Lecture from: 06.11.2024 | Video: Videos ETHZ

Algebra

In abstract algebra, we study algebraic structures, which consist of a set $S$ and one or more operations defined on that set. Focusing on binary operations, we denote a structure as $⟨S;\ast ⟩$, where $\ast :S\times S\to S$. This means the operation $\ast$ takes two elements from $S$ as input and produces another element in $S$ as output. If $S$ is a finite set with $|S|=n$, then there are $n^{(n^2)}$ possible binary operations on $S$.

Groups

Groups are a specific type of algebraic structure where the binary operation satisfies certain constraints. A group is denoted by $⟨G;\ast {,}^{-1},e⟩$, where $G$ is a set, $\ast$ is the binary operation, ${}^{-1}$ denotes the inverse operation, and $e$ is the identity element. A minimal set of defining properties (axioms) of a group are:

• G1 (Associativity): For all $a,b,c\in G$, $(a\ast b)\ast c=a\ast (b\ast c)$. This means the grouping of operations doesn’t affect the result.

• G2’ (Right Identity): There exists an element $e\in G$ such that for all $a\in G$, $a\ast e=a$.

• G3’ (Right Inverse): For every element $a\in G$, there exists an element $\hat{a}\in G$ (we use $\hat{a}$ to distinguish from $a^{-1}$ in the full axiom set) such that $a\ast \hat{a}=e$.

From G1, G2’, and G3’, we can prove the existence and uniqueness of a two-sided identity ($e\ast a=a\ast e=a$), and a two-sided inverse ($\hat{a}\ast a=a\ast \hat{a}=e$, implying $\hat{a}=a^{-1}$), as demonstrated in the previous lecture notes. Therefore, these minimal axioms fully characterize a group.

Groups with 1 Element ($n=1$)

If $n=1$, the set $G$ contains only one element, which must be the identity element $e$. The operation table is trivial:

This single-element group is often denoted as the trivial group.

Groups with 2 Elements ($n=2$)

If $n=2$, let $G=\{e,a\}$, where $e$ is the identity element. The row and column corresponding to $e$ are determined by the identity property ($e\ast e=e$ and $e\ast a=a$). This leaves one entry to be determined: $a\ast a$.

For $G$ to be a group, every element must have an inverse. Since $e$ is its own inverse ($e\ast e=e$), the only possible inverse for $a$ is itself. Therefore, $a\ast a=e$. This leads to a unique group structure:

This group is isomorphic to ${\mathbb{Z}}_2$, the integers modulo 2 under addition. It can also be interpreted as the bitwise XOR operation on a single bit. We denote this group as ${\mathbb{Z}}_2$.

Groups with 3 Elements ($n=3$)

Let $G=\{e,a,b\}$, where $e$ is the identity element. As before, the row and column corresponding to $e$ are determined by the identity property.

We can deduce the remaining entries by considering the requirements for inverses and the Latin square property (each element appears exactly once in each row and column).

This group is isomorphic to ${\mathbb{Z}}_3$, the integers modulo 3 under addition. Each element can be mapped to a corresponding element in ${\mathbb{Z}}_3$: $e\to 0$, $a\to 1$, $b\to 2$. The operation table then corresponds to addition modulo 3.

Groups with 4 Elements ($n=4$)

With four elements, the situation becomes more complex. Unlike groups with one, two, or three elements, there are two distinct group structures (up to isomorphism) for a group of order 4.

Let $G=\{e,a,b,c\}$, where $e$ is the identity element. The first row and column are determined by the identity property. However, there’s no longer a unique way to complete the table to satisfy the group axioms.

1. The Klein Four-Group (${\mathbb{Z}}_2\times {\mathbb{Z}}_2$)

One possibility is the Klein four-group, also denoted as ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$. This group is isomorphic to the direct product of two copies of ${\mathbb{Z}}_2$. Its operation table is:

In this group, every element is its own inverse ($x\ast x=e$ for all $x\in G$). This group is abelian (commutative). As discussed previously, this can be interpreted as bitwise XOR on two-bit strings.

2. The Cyclic Group of Order 4 (${\mathbb{Z}}_4$)

The other possible group structure is the cyclic group of order 4, denoted as ${\mathbb{Z}}_4$. This group is isomorphic to the integers modulo 4 under addition. Its operation table is:

In this group, $a$ has order 4 (meaning $a\ast a\ast a\ast a=e$), $b$ has order 2 ($b\ast b=e$), and $c$ has order 4. This group is also abelian. It can be interpreted as rotations by multiples of 90 degrees (0°, 90°, 180°, 270°).

These two groups, ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$ and ${\mathbb{Z}}_4$, are not isomorphic to each other. One key difference is that ${\mathbb{Z}}_4$ has an element of order 4, while all non-identity elements in ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$ have order 2. This demonstrates that even with a small number of elements, different group structures can arise.

The Multiplicative Group of Integers Modulo 5 (${\mathbb{Z}}_5^{\ast }$)

We previously examined groups of the form $⟨{\mathbb{Z}}_m^{\ast };{\odot }_m⟩$, where ${\mathbb{Z}}_m^{\ast }$ is the set of integers modulo $m$ that are coprime to $m$, and ${\odot }_m$ represents multiplication modulo $m$. Let’s consider the case where $m=5$.

Since 5 is a prime number, all non-zero elements modulo 5 are coprime to 5. Therefore, ${\mathbb{Z}}_5^{\ast }=\{1,2,3,4\}$. The operation table for $⟨{\mathbb{Z}}_5^{\ast };{\odot }_5⟩$ is:

This group is isomorphic to ${\mathbb{Z}}_4$, the cyclic group of order 4. The isomorphism can be seen by mapping the elements as follows:

• $1\in {\mathbb{Z}}_5^{\ast }\to 0\in {\mathbb{Z}}_4$ (identity elements)
• $2\in {\mathbb{Z}}_5^{\ast }\to 1\in {\mathbb{Z}}_4$
• $4\in {\mathbb{Z}}_5^{\ast }\to 2\in {\mathbb{Z}}_4$
• $3\in {\mathbb{Z}}_5^{\ast }\to 3\in {\mathbb{Z}}_4$

The Multiplicative Group of Integers Modulo 8 (${\mathbb{Z}}_8^{\ast }$)

Let’s examine the multiplicative group of integers modulo 8, denoted as ${\mathbb{Z}}_8^{\ast }$. This group consists of the elements in ${\mathbb{Z}}_8$ that are coprime to 8, under the operation of multiplication modulo 8.

The elements coprime to 8 are 1, 3, 5, and 7. Therefore, ${\mathbb{Z}}_8^{\ast }=\{1,3,5,7\}$. The operation table for $⟨{\mathbb{Z}}_8^{\ast };{\odot }_8⟩$ is:

Notice that every element is its own inverse ($x{\odot }_{8}x=1$ for all $x\in {\mathbb{Z}}_8^{\ast }$). This group is isomorphic to the Klein four-group, ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$. One possible isomorphism is given by the following mapping:

• $1\in {\mathbb{Z}}_8^{\ast }\to (0,0)\in {\mathbb{Z}}_2\times {\mathbb{Z}}_2$
• $3\in {\mathbb{Z}}_8^{\ast }\to (0,1)\in {\mathbb{Z}}_2\times {\mathbb{Z}}_2$
• $5\in {\mathbb{Z}}_8^{\ast }\to (1,0)\in {\mathbb{Z}}_2\times {\mathbb{Z}}_2$
• $7\in {\mathbb{Z}}_8^{\ast }\to (1,1)\in {\mathbb{Z}}_2\times {\mathbb{Z}}_2$

Under this mapping, multiplication modulo 8 corresponds to component-wise addition modulo 2. For example, $3{\odot }_{8}5=7$ corresponds to $(0,1)+(1,0)=(1,1)$.

This example illustrates that ${\mathbb{Z}}_m^{\ast }$ can have different structures depending on the value of $m$. Even though $|{\mathbb{Z}}_8^{\ast }|=4$, like ${\mathbb{Z}}_5^{\ast }$, its structure is different.

Square to Square Transformations (Dihedral Group $D_4$)

Let’s analyze the transformations of a square that map the square back onto itself. These transformations form the dihedral group $D_4$. There are eight such transformations: four rotations and four reflections.

We can represent the rotations as $R_0$ (0°), $R_{90}$ (90° clockwise), $R_{180}$ (180°), and $R_{270}$ (270° clockwise). The reflections can be represented by their axes of reflection:

• $V$: Vertical reflection
• $H$: Horizontal reflection
• $D_1$: Reflection across the main diagonal (top-left to bottom-right)
• $D_2$: Reflection across the other diagonal (top-right to bottom-left)

The complete operation table for $D_4$ is:

The rotations form a subgroup isomorphic to ${\mathbb{Z}}_4$, demonstrating the cyclic nature of rotations. The reflections do not form a subgroup by themselves because the composition of two reflections can produce a rotation.

Note that $D_4$ can be viewed as a subgroup of $S_4$, the symmetric group on four elements. This is because each transformation in $D_4$ corresponds to a permutation of the four vertices of the square. However, $D_4$ is a proper subgroup, as $S_4$ contains $4!=24$ elements, while $D_4$ has only 8. So, we write $D_4\subset S_4$. Using the notation $S_{\square }$ to represent the symmetry group of the square, we have $S_{\square }=D_4\subset S_4$.

Subgroups

Given a group $⟨G;\ast {,}^{-1},e⟩$, a subgroup is a subset $H\subseteq G$ that also forms a group under the same operation $\ast$ restricted to $H$. This is denoted as $H\le G$.

For $H$ to be a subgroup of $G$, it must satisfy the following conditions:

1. Closure: For all $a,b\in H$, $a\ast b\in H$. The operation applied to any two elements in $H$ must produce a result that is also in $H$.
2. Identity: The identity element $e$ of $G$ must also be in $H$.
3. Inverses: For every element $a\in H$, its inverse $a^{-1}$ (with respect to the operation $\ast$ in $G$) must also be in $H$.

If $G$ is a finite group and $H$ is a subgroup of $G$, then the order (number of elements) of $H$ must divide the order of $G$. This is known as Lagrange’s theorem. We write $|H|\mid |G|$. So if $G$ is a group $|G|=20$, subgroups of $G$ can only be $\{e\}$ ($|H|=1$), $|H|=2,4,5,10,20$.

Example from next lecture:

General Concepts

Cartesian Product of Groups

Given two groups $G=⟨G;{\ast }_G{,}_G^{-1},e_G⟩$ and $H=⟨H;{\ast }_H{,}_H^{-1},e_H⟩$, their Cartesian product, denoted $G\times H$, is a new group formed by taking the Cartesian product of their underlying sets and defining the operation component-wise.

More formally:

• Set: The underlying set of $G\times H$ is the set of all ordered pairs $(g,h)$, where $g\in G$ and $h\in H$. That is, $G\times H=\{(g,h)\mid g\in G,h\in H\}$.
• Operation: The binary operation $\ast (G\times H)$ on $G\times H$ is defined as: $(g_1,h_1)\ast (G\times H)(g_2,h_2)=(g_1{\ast }_G{g}_2,h_1{\ast }_H{h}_2)$.
• Identity Element: The identity element of $G\times H$ is $(e_G,e_H)$.
• Inverse Element: The inverse of an element $(g,h)\in G\times H$ is $(g_G^{-1},h_H^{-1})$.

Example: ${\mathbb{Z}}_5\times {\mathbb{Z}}_7$

Consider the groups ${\mathbb{Z}}_5$ (integers modulo 5 under addition) and ${\mathbb{Z}}_7$ (integers modulo 7 under addition). Their Cartesian product, ${\mathbb{Z}}_5\times {\mathbb{Z}}_7$, is a group with $5\times 7=35$ elements. The elements are ordered pairs $(x,y)$, where $x\in \{0,1,2,3,4\}$ and $y\in \{0,1,2,3,4,5,6\}$.

The group operation is component-wise addition modulo 5 and modulo 7, respectively. For example:

$(2,3)+(4,5)=(2{+}_{5}4,3{+}_{7}5)=(1,1)$

The identity element is $(0,0)$, and the inverse of an element $(x,y)$ is $(-x(\mathrm{mod}5),-y(\mathrm{mod}7))$. For example, the inverse of $(2,3)$ is $(3,4)$, since $(2,3)+(3,4)=(0,0)$.

Group Homomorphisms and Isomorphisms

A group homomorphism is a structure-preserving map between two groups. Given two groups $G=⟨G;{\ast }_G{,}_G^{-1},e_G⟩$ and $H=⟨H;{\ast }_H{,}_H^{-1},e_H⟩$, a homomorphism $\varphi :G\to H$ is a function that satisfies the following property for all $a,b\in G$:

$\varphi (a{\ast }_{G}b)=\varphi (a){\ast }_H\varphi (b)$

In essence, a homomorphism preserves the group operation. Applying the operation in $G$ and then mapping the result to $H$ is the same as mapping the elements to $H$ first and then applying the operation in $H$.

A group isomorphism is a bijective (one-to-one and onto) group homomorphism. If an isomorphism exists between two groups $G$ and $H$, we say that $G$ and $H$ are isomorphic, denoted as $G\cong H$. Isomorphic groups have the same underlying structure, even if their elements and operations are represented differently.

Example: Logarithms

The invention of logarithms provides a classic example of a group isomorphism. Consider the following two groups:

• $⟨{\mathbb{R}}^{+};\cdot {,}^{-1},1⟩$: The group of positive real numbers under multiplication, with the multiplicative inverse and 1 as the identity element.
• $⟨\mathbb{R};+,-,0⟩$: The group of real numbers under addition, with additive inverse (negation) and 0 as the identity element.

The logarithm function (with any fixed base) establishes an isomorphism between these two groups. Let ${\log }_b:{\mathbb{R}}^{+}\to \mathbb{R}$ be the logarithm function with base $b>0$ and $b\ne 1$. Then:

${\log }_b(x\cdot y)={\log }_b(x)+{\log }_b(y)$

This is the homomorphism property. The logarithm of a product is the sum of the logarithms.

Furthermore, the logarithm function is bijective: every positive real number has a unique logarithm, and every real number is the logarithm of some positive real number. The inverse function is exponentiation: $b^x$.

Therefore, the logarithm function provides an isomorphism between the multiplicative group of positive real numbers and the additive group of real numbers. This isomorphism allows us to transform multiplication problems into addition problems, which is the fundamental principle behind the usefulness of logarithms for simplifying calculations.

Lemma about Homomorphisms $\psi :G\to H$

Let $\psi :G\to H$ be a group homomorphism between groups $G=⟨G;{\ast }_G{,}_G^{-1},e_G⟩$ and $H=⟨H;{\ast }_H{,}_H^{-1},e_H⟩$. The following properties hold:

1. Preservation of Identity: $\psi (e_G)=e_H$

Proof:

1. $\psi (e_G)=\psi (e_G{\ast }_G{e}_G)$ (Identity property in $G$)
2. $\psi (e_G)=\psi (e_G){\ast }_H\psi (e_G)$ (Homomorphism property)
3. $e_H{\ast }_H\psi (e_G)=\psi (e_G){\ast }_H\psi (e_G)$ (Identity property in $H$)
4. $e_H=\psi (e_G)$ (Left cancellation law in $H$)

Example: In the logarithm example, ${\log }_b(1)=0$. The logarithm of the multiplicative identity (1) is the additive identity (0).

2. Preservation of Inverses: $\psi (a_G^{-1})=(\psi (a){)}_H^{-1}$

Proof:

1. $e_H=\psi (e_G)$ (Preservation of identity)
2. $e_H=\psi (a{\ast }_G{a}_G^{-1})$ (Inverse property in $G$)
3. $e_H=\psi (a){\ast }_H\psi (a_G^{-1})$ (Homomorphism property)
4. $(\psi (a){)}_H^{-1}{\ast }_H{e}_H=(\psi (a){)}_H^{-1}{\ast }_H(\psi (a){\ast }_H\psi (a_G^{-1}))$ (Multiply both sides by $(\psi (a){)}_H^{-1}$ on the left)
5. $(\psi (a){)}_H^{-1}=((\psi (a){)}_H^{-1}{\ast }_H\psi (a)){\ast }_H\psi (a_G^{-1})$ (Associativity in $H$)
6. $(\psi (a){)}_H^{-1}=e_H{\ast }_H\psi (a_G^{-1})$ (Inverse property in $H$)
7. $(\psi (a){)}_H^{-1}=\psi (a_G^{-1})$ (Identity property in $H$)

Example: In the logarithm example, ${\log }_b(x^{-1})={\log }_b(\frac{1}{x})=-{\log }_b(x)$. The logarithm of the multiplicative inverse is the additive inverse of the logarithm.

Number of Groups

The number of distinct group structures (up to isomorphism) for a given order (number of elements) is a fundamental question in group theory. For small orders, this number can be determined, but it becomes complex as the order increases.

For prime orders ($n$), there is only one group up to isomorphism, the cyclic group ${\mathbb{Z}}_n$. This is a consequence of Lagrange’s theorem, which states that the order of any subgroup must divide the order of the group. In a group of prime order $p$, there are no non-trivial proper subgroups and must be cyclic.

As the order increases, the number of possible group structures becomes more complex to determine. While there are formulas and algorithms for specific cases, there’s no general formula for the number of groups of order $n$.

Example: ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$

The group ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$ has $2\times 4=8$ elements, which are ordered pairs $(x,y)$ with $x\in \{0,1\}$ and $y\in \{0,1,2,3\}$. The operation is component-wise addition modulo 2 and modulo 4, respectively.

For example: $(1,3)+(0,2)=(1{+}_{2}0,3{+}_{4}2)=(1,1)$. To construct the full operation table, you would list all 8 elements as row and column headers and compute the sum for each pair using this component-wise addition.

Example: ${\mathbb{Z}}_{15}^{\ast }$

${\mathbb{Z}}_{15}^{\ast }$ consists of the elements in ${\mathbb{Z}}_{15}$ that are coprime to 15. To find these elements, we look for integers $k$ such that $1\le k<15$ and $\text{gcd}(k,15)=1$.

The elements are: 1, 2, 4, 7, 8, 11, 13, and 14. Thus, $|{\mathbb{Z}}_{15}^{\ast }|=8$.

You correctly point out that ${\mathbb{Z}}_{15}^{\ast }$ is not isomorphic to ${\mathbb{Z}}_2\times {\mathbb{Z}}_2\times {\mathbb{Z}}_2$ because in the latter, every element is its own inverse, which is not the case in ${\mathbb{Z}}_{15}^{\ast }$. For example, in ${\mathbb{Z}}_{15}^{\ast }$, $2\cdot 8=16\equiv 1(\mathrm{mod}15)$, so 2 and 8 are inverses of each other.

Determining the precise structure of ${\mathbb{Z}}_{15}^{\ast }$ requires further analysis. It turns out that ${\mathbb{Z}}_{15}^{\ast }\cong {\mathbb{Z}}_4\times {\mathbb{Z}}_2$. This can be shown by finding elements of order 4 and 2 that generate the group. For example, the element 7 has order 4, and the element 11 has order 2. Once we find these generating elements, we can easily calculate the others and have an isomorphism.

Continue here: 16 Isomorphism, Powers, Order, Generators, Lagrange’s Theorem, Multiplicative Groups, Euler’s Totient Function, RSA