# Generators and Relations

When you are in a deep hole, stop digging!

Recall: Let G and H be groups, and let φ: G → H be a homomorphism. Then:

1. The kernel of φ is a normal subgroup of G, H ◁ G.
2. The image of φ is a subgroup of H, im(φ) ≤ G.
3. The image of φ is isomorphic to the quotient group G/ker(φ), G/Ker(φ) ≋ Im(φ). In particular, if φ is surjective then H is isomorphic to G/ker(φ).

A presentation is one method of specifying a group. It comprises a set of generators S (every element of the group can be expressed as a combination of these generators and their inverses) and a set of relations or equations R among those generators, we then say that a group G has a presentation ⟨S | R⟩, e.g., D4 = ⟨a, b | a4 = b2 = e, ab = ba-1⟩, ℤ x ℤ = ⟨a, b | ab = ba⟩, ℤ4⊕ ℤ2 = ⟨a, b | a4 = b2 = 2 and ab = ba⟩

Let be a set S = {a, b, c, …}, S-1 = {a-1, b-1, c-1, …}. W(S) = {x1x2···xk, where each xi∈ S ∪ S-1}, the collection of all formal finite strings x1x2···xk or words, including the empty word (e) with no elements.

A binary operation on the set W(S) could be defined by juxtaposition, ∀ x1x2···xk and y1y2···yt ∈ W(S), then so does x1x2···xky1y2···yt. This binary operation is well-defined, associative, and has the empty word as the identity, but we have no inverses.

It seems obvious that the inverse of ab, should be b-1a-1, but abb-1a-1 is not the empty word.

Equivalence classes of words. ∀u, v ∈ W(S), we say that u is related to v (u ~ v) if v can be obtained from u by a finite sequence of insertions or deletions of words of the form xx-1 or x-1x, where x ∈ S. This relation is an equivalence relation on W(S). The proof is left to the reader as an easy exercise, I know that I am awesome - you are welcome!😄

Examples: Let S = {a, b, c} Then acc-1b is equivalent to ab, ab-1bcc-1b is equivalent to ab, ab-1bb-1bcc-1b is equivalent to ab-1bcc-1b, acc-1b, and ab, and so on and so forth ad nauseum.

Let S be a set of distinct symbols. ∀u ∈ W(S), let $\bar u$ denote the equivalence class containing u (that is, the set of all words equivalent to u). Then, the set of all equivalence classes of elements of W(S) is a group, called the free group, under the group operation $\bar u·\bar v=\overline {uv}$.

Theorem. The universal mapping property. Every group is a homomorphic image of a free group.

Proof.

Let G be a group and let S be a set of generator for G. Please notice that such a set does exist because we could take S to be G itself. Let F be the free group on S.

Let’s use some notations for the sake of clarity:

1. x1x2···xn ∈ W(S) will be written as $(x_1x_2···x_n)_F$
2. The product of elements in G x1x2···xn by (x1x2···xn)G
3. $\overline {(x_1x_2···x_n)}$ denotes the equivalence class in F containing the set of all words in W(S) equivalent to $(x_1x_2···x_n)_F$

Let’s consider the mapping Φ: F → G defined by Φ$\overline {(x_1x_2···x_n)}$ = (x1x2···xn)G

1. Φ is well-defined because inserting or deleting a sequence of expressions of the form xx-1 or x-1x corresponds to inserting or deleting the identity in G.
2. Φ is homomorphism, that is, operation-preserving: $Φ\overline {(x_1x_2···x_n)}\overline {(y_1y_2···y_m)}~=~Φ\overline {(x_1x_2···x_ny_1y_2···y_m)}~=$ (x1x2···xny1y2···ym)G = (x1x2···xn)G(y1y2···ym)G = $Φ\overline {(x_1x_2···x_n)}Φ\overline {(y_1y_2···y_m)}$
3. Φ is onto because F is the free group, that is, the group of all equivalence classes of elements of W(S) and S is a set of generators for G.

Corollary. Every group is isomorphic to a factor group of a free group.

Proof.

Φ: F → G defined by Φ$\overline {(x_1x_2···x_n)}$ = (x1x2···xn)G is a group homomorphism by the previous theorem ⇒ [By the First Isomorphism Theorem] G =[Φ is onto] Im(Φ) ≋ F/Ker(Φ)∎

# Example

Let F be the free group on {a, b}, let N be the smallest normal subgroup of F containing the set {a4, b2, (ab)2}. Claim: F/N ≋ D4.

Let’s define Φ: F → D4, Φ(a) = R90 (clockwise rotation by 90°), Φ(b) = H (the horizontal reflection) is a well-defined homomorphism, and N ⊆ Ker(Φ) (a4 = b2 = (ab)2 = e) and [By the First Isomorphism Theorem, Φ is onto] D4 ≋ F/Ker(Φ)

D4 = ⟨a, b | a4 = b2 = (ab)2 = e⟩

Let K = {N, aN, a2N, a3N, bN, abN, a2bN, a3bN} be the set of left cosets of N. Claim: K is F/N itself (and D4). Notice that every member of F/N can be generated by starting with N and successively multiplying on the left by combinations of a’s and b’s, so we need to show that K is closed under left multiplication by a and b.

• It is trivial that K is closed under left multiplication by a.
• Let’s see that K is closed under left multiplication by b.
1. b(aN) = baN = [By assumption, N is the smallest normal subgroup of F containing {a4, b2, (ab)2}, so b2 ∈ N and Nb2 = N] baNb2 =[N is normal ⇒ bN = Nb ⇒ Nb2 = bNb] babNb = (a-1a)babNb = (a-1)(abab)Nb [e = (ab)2 = abab ∈ N, so by absorption] a-1Nb = [a4 ∈ N] a-1a4Nb = a3Nb = [Nb = bN] a3bN.
2. b(a2N) =[ba2N=baaN=N is normalbaNa] baNa = [b(aN) = a3bN, the previous result] a3bNa = a3baN = [b(aN) = a3bN, the previous result] a3a3bN = a6bN =[N is normal] a6Nb = a2Nb = a2bN.
3. b(a3N) = b(a2aN) = b(a2N)a = [By 2]a2bNa = a2baN = [By 1] a2a3bN = a2a3Nb = a5Nb = aNb = abN.
4. b(bN) = b2N = N.
5. b(abN) = baNb = [By 1] a3bNb = a3bbN = a3b2N = a3N
6. b(a2bN) = b(a2N)b = [By 2] a2bNb = a2bbN = a2b2N = a2N
7. b(a3bN) = b(a3N)b = [By 3] abNb = abbN = ab2N = aN

Therefore, F/N has at most eight elements. F/Ker(Φ) ≋ D4 ⇒ |F/Ker(Φ)| = 8, F/Ker(Φ) is a factor group of F/N (The factor group F/Ker(Φ) is the set of all left cosets of N in F) ⇒[|F/N| ≤ 8 and |F/Ker(Φ)| = 8 ⇒ |F/N| = |F/Ker(Φ)| = 8] F/N = F/Ker(Φ) ≋ D4.

F/Ker(Φ) is a factor group of F/N because N is the smallest normal subgroup of F containing {a4, b2, (ab)2}, N ⊆ Ker(Φ), and F/Ker(Φ) ≋ (F/N)/(ker(Φ)/N)

Definition. Let G be a group generated by some subset A = {a1, a2,…, an}, F be the free group on A, W = {w1, w2,…, wt} ⊆ F, and N be the smallest normal subgroup of F containing W. We say that G has the presentation ⟨a1, a2,..., an | w1 = w2 = ... = wt = e⟩ or is given by the generators a1, a2,..., an and the relations w1 = w2 = ... = wt = e if there is an isomorphism Φ from F/N onto G such that Φ(aiN) = ai.

Example. The group of integers is the free group on one letter, i.e., ℤ ≋ ⟨a⟩

Dick’s theorem. Let G = ⟨a1, a2,..., an | w1 = w2 = ... = wt = e⟩ and let create a new group by imposing additional relations, that is, $\bar G$ = ⟨a1, a2,..., an | w1 = w2 = ... = wt = wt+1 = ··· = wt+k = e⟩. Then, $\bar G$ is a homomorphic image of G.

Proof.

Let F be the free group on {a1, a2,…, an}, N be the smallest normal subgroup of F containing {w1, w2,… , wt}, M be the smallest normal subgroup of F containing {w1, w2,… , wt, wt+1,…, wt+k}.

Then, by the definition of generators and relations, F/N ≋ G and F/M ≋ $\bar G$.

Consider the mapping Φ: F/N → F/M defined by Φ(aN) = aM ∀a ∈ F.

1. Φ is homomorphism. Φ((a1N)(a2N)) = Φ(a1a2N) = a1a2M = (a1M)(a2M) = Φ(a1N)Φ(a2N)
2. Φ is onto.

F/N ≋ G and F/M ≋ $\bar G$, the surjective homomorphism from F/N to F/M induces a surjective homomorphism between G and $\bar G$. Hence, $\bar G$ is a homomorphic image of G.

Corollary. If K is a group satisfying the defining relations of a finite group G = ⟨a1, a2,..., an | w1 = w2 = ... = wt = e⟩ and |K| ≥ |G|, then K ≋ G.

Proof. By Dyck’s Theorem, K is a homomorphic image of G ⇒ |K| ≤ |G| and by assumption |K| ≥ |G| ⇒ |K| = |G|. Given that K is a homomorphic image of G, then we indeed have an isomorphism, K ≋ G.

# The Quaternion Group, Q4

Q4={1, −1, i, −i, j,− j, k, −k} where 1⋅a=a⋅1=a ∀a∈Q4, (−1)⋅a=a⋅(−1)=−a, i⋅i=j⋅j=k⋅k=−1, i⋅j=k, j⋅i=−k, j⋅k=i, k⋅j=−i, k⋅i=j, and i⋅k=−j. It is defined by the presentation Q4 = ⟨a, b | a2 = b2 = (ab)2

By definition, Q4 ≋ F/N where F is the free group on the set {a, b} and N is the smallest normal subgroup of F containing b-2a2 and (ab)-2a2.

Next, let us consider H = ⟨b⟩ and S = ⟨H, aH⟩, then just as we did before, S is closed under left multiplication by combinations of a’s and b’s (e.g., bH =[bH = H ↭ b ∈ H = ⟨b⟩] H, a2H =[a2 = b2] b2H = bbH = bH = H, abH = aH, etc.) ⇒ Q4 = H ∪ aH.

From there, we can understand the structure of Q4, once we really know how many elements there are in H.

Observe that b2 = (ab)2 = abab ⇒[Cancellation law] b = aba. Futhermore, a2 = b2 =[b = aba] (aba)(aba) = aba2ba =[a2 = b2] abb2ba = ab4a ⇒ a2 = ab4a ⇒ a = ab4e = b4.

Hence, there are at most four elements in H, so H = ⟨b⟩ = {e, b, b2, b3}, and therefore, at most eight in Q4 = H ∪ aH, namely, {e, b, b2, b3, a, ab, ab2, ab3}. However, there is a larger uncertainty, as it is reasonable to consider that not all of these eight elements are distinct.

By the Corollary to Dyck’s Theorem, it suffices to find one specific group that satisfies the defining generators and relations of Q8 and ord($\bar G$) = 8 ≥ |Q4| ⇒ Q4 ≋ $\bar G$, and therefore ord(Q4) = 8.

It turns out that there exists such an example $\bar G$ generated by the matrices A = $(\begin{smallmatrix}0 & 1\\ -1 & 0\end{smallmatrix})$ and B = $(\begin{smallmatrix}0 & i\\ i & 0\end{smallmatrix})$ where i = $\sqrt{-1}$.

Calculating all the elements in $\bar G$ directly can prove that its eight elements {e, B, B2, B3, A, AB, AB2, AB3} are all distinct indeed and $\bar G$ satisfies the relation A2 = B2 = (AB)2, e.g., $A^2 = (\begin{smallmatrix}0 & 1\\ -1 & 0\end{smallmatrix})(\begin{smallmatrix}0 & 1\\ -1 & 0\end{smallmatrix}) = (\begin{smallmatrix}-1 & 0\\ 0 & -1\end{smallmatrix}) = (\begin{smallmatrix}0 & i\\ i & 0\end{smallmatrix})(\begin{smallmatrix}0 & i\\ i & 0\end{smallmatrix}) = B^2$ Hence, the quaternion group Q4 = ⟨a,b ∣ a2 = b2 = (ab)2⟩ is of order 8, and its elements are {e, b, b2, b3, a, ab, ab2, ab3}. Besides, Q4 is not isomorphic to D4.

Example. Let G = ⟨a, b | a3 = b9 = e, a-1ba = b-1⟩. Let H = ⟨b⟩, then it can easily be demonstrated that G = H ∪ aH ∪ a2H. Therefore, G = {aibj | 0 ≤ i ≤ 2, 0 ≤ j ≤ 8} ⇒ |G| ≤ 27.

a-1ba = b-1b = (a-1ba)-1 =[Shoe-socks property] a-1b-1a.

b = ebe = [a3 = e ⇒ a-3 = e] a-3ba3 = a-2(a-1ba)a2 =[a-1ba = b-1] a-2b-1a2 = a-1(a-1b-1a)a =[b = a-1b-1a] a-1ba = b-1 ⇒ [b = b-1] b2 = e = b9 ⇒ e = b9 = b2b2b2b2b =[b2 = e] eeeeb = b ⇒ b = e ⇒ G has at most three elements, namely a, a2, and e, and we know a group ℤ3 that satisfies the defining relations (additive notation) with a = 1 and b = 0 (e.g., a3 = 1 + 1 + 1 = 0, b = 0), so G did not have 27 distinct elements, but just 3.

Lemma. If every element of a group except its identity has order 2, then the group is Abelian.

Proof.

Let a ∈ G be an arbitrary element, a ≠ e. By assumption, a2 = e ⇒[Uniqueness of inverses] a = a -1 ⇒ In particular, ∀a, b ∈ G, (ab)-1 = ab

By Sock and Shoes’ Theorem, (ab)-1 = b-1a-1 = ba. Therefore, ab = ba∎

Groups of Order 8: Up to isomorphism, there are only five groups of order 8, namely ℤ8, ℤ4⊕ℤ2, ℤ2⊕ℤ2⊕ℤ2, D4, and the quaternion group Q4.

Proof: By the Fundamental Theorem of Finite Abelian Groups (Every finite Abelian group is an internal group direct product of cyclic groups whose orders are prime powers), we know that any Abelian group of order 8 = 23 is isomorphic to ℤ8 (-3-, 1 element in the partition), ℤ4⊕ℤ2 (-2+1-, 2 elements in the partition), ℤ2⊕ℤ2⊕ℤ2 (-1+1+1-, 3 elements in the partition).

Let G be a non Abelian group, |G| = 8. Let G1 = ⟨a, b | a4 = b2 = (ab)2 = e⟩ and G2 = ⟨a, b | a2 = b2 = (ab)2 = e⟩. From previous discussions, we know that G1 ≋ D4 and G2 ≋ Q4. Therefore, we are left with showing that G must be isomorphic, i.e., satisfying the defining relations of either G1 or G2.

By Lagrange’s Theorem, the order of some arbitrary element a ∈ G, a ≠ e, |a| | |G|=8 ⇒[a ≠ e] |a| = 2, 4 or 8. By the previous lemma (by assumption, G is not Abelian), we know that not all elements of G have order 2 ⇒ ∃a ∈ G: |a| = 4 or 8. If |a| = 8 ⇒ |a2| = 4 ⇒ ∃a ∈ G (we are abusing some notation here 🙂): |a| = 4

Another argument could go like this |a| = 8 ⇒ G is cyclic, generated by this element, and all cyclic groups are Abelian ⊥

Let b ∈ G, b ∉ ⟨a⟩ (such an element exists because |a| = 4 and |G| = 8) ⇒ [By Lagrange’s Theorem, H = ⟨a⟩, |G| = 8 = [G:H]·|H| = [G:H]·4 ⇒ [G:H] = 2, there are two cosets, G = ⟨a⟩ ∪ ⟨a⟩b = {e, a, a2, a3, b, ab, a2b, a3b}.

First, it is obvious that {a, b} is a generator of G.

Let us consider the element b2 ∈ G. Which of the eight elements of G can it be?

• b2 = bb = b ⇒ [Cancellation law] b = e ⊥
• b2 = bb = ab ⇒ [Cancellation law] b = a but b ∉ ⟨a⟩⊥
• b2 = bb = a2b ⇒ [Cancellation law] b = a2 but b ∉ ⟨a⟩ ⊥
• b2 = bb = a3b ⇒ [Cancellation law] b = a3 but b ∉ ⟨a⟩ ⊥
• b2 = a, that is also not possible because b2 obviously commute with b (b2b = bb2), but a does not (ab ≠ ba because since {a, b} generates G, this will make G an Abelian group). If b2 = a, then ab = b2b = bb2 = ba ⊥
• b2 = a3 ⇒ that is not possible because b2 commute with b and a3 does not. For the sake of contradiction, a3b = ba3 ⇒ [* a right] a3ba = ba3a = e, a3ba = b ⇒ [* a left] aa3ba = ab ⇒ ba = ab ⊥
• b2 = e, since [A subgroup of index 2 is always normal] ⟨a⟩ ◁ G ⇒ [By definition] b⟨a⟩b-1 = ⟨a⟩. In particular, bab-1 ∈ ⟨a⟩ and we know [Order of Conjugate Element equals Order of Element, |xax-1|=|a|] |bab-1| = |a| ⇒[bab-1 ∈ ⟨a⟩] bab-1 = a (ba = ab, G is Abelian ⊥) or bab-1 = a-1 ⇒ ab-1 = b-1a-1 = [Sock and Shoes Theorem] (ab)-1 ⇒ [b2=e ⇒ b = b-1] ab = (ab)-1. Therefore, it satisfies the defining relations for G1 = ⟨a, b | a4 = b2 = (ab)2 = e⟩
• b2 = a2, same reasoning as before bab-1 = a-1 ⇒ (ab)2 = abab = aba(b-1b)b ⇒ a(bab-1)bb = [ bab-1 = a-1] aa-1bb = b2. Therefore, it satisfies the defining relations for G2 = ⟨a, b | a2 = b2 = (ab)2 = e⟩.

This way of classifying groups of order 8 using generators and relations presentation is fundamental to understanding other group structures. If we use all of this in combination with other theorems that teach us about the order of elements in groups of orders p2, 2p, or pq where p and q are primes, it allows us to classify groups of orders up to 15.

# Characterization of Dihedral Groups

Let be the group of symmetries of a regular n-gon, Dn ≋ ⟨a, b | an = b2 = (ab)2 = e⟩. We define the infinite dihedral group D as ⟨a, b |a2 = b2 = e⟩ = {e, a, b, ab, ba, (ab)a, (ba)a, (ab)2, (ba)2, (ab)2a, (ba)2b, (ab)3, …}

Lemma. Let G be a group, ⟨a, b⟩ = ⟨a, ab⟩

Proof:

Obviously, a and ab ∈ ⟨a, b⟩, and therefore ⟨a, ab⟩ ⊆ ⟨a, b⟩.

We claim ⟨a, b⟩ ⊆ ⟨a, ab⟩, that is pretty obvious, too because a ∈ ⟨a, ab⟩, and b = a-1(ab) ∈ ⟨a, ab⟩∎

Characterization of Dihedral Groups. Any group generated by a pair of elements of order 2 is dihedral.

Proof. The reader could check it for himself or read it in the Contemporary Abstract Algebra, Joseph, A. Gallian.

# Bibliography

This content is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This post relies heavily on the following resources, specially on NPTEL-NOC IITM, Introduction to Galois Theory, Michael Penn, and Contemporary Abstract Algebra, Joseph, A. Gallian.
1. NPTEL-NOC IITM, Introduction to Galois Theory.
2. Algebra, Second Edition, by Michael Artin.
3. LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
4. Field and Galois Theory, by Patrick Morandi. Springer.
5. Michael Penn (Abstract Algebra), and MathMajor.
6. Contemporary Abstract Algebra, Joseph, A. Gallian.
7. Andrew Misseldine: College Algebra and Abstract Algebra.
Bitcoin donation