    # Generators and Relations

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.
2. The image of φ is a subgroup of H.
3. The image of φ is isomorphic to the quotient group G/ker(φ). 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 G has presentation ⟨S | R⟩, e.g., D4 = ⟨r, f | r4 = f2 = (rf)2 = id⟩, ℤ 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.

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

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 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$

659353521

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] 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. 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 = [b2 ∈ N] baNb2 =[N is normal ⇒ bN = Nb ⇒ Nb2 = bNb] babNb = (a-1a)babNb = (a-1)(abab)Nb [e = (ab)2 = abab ∈ N] 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 = a6Nb = a2Nb = a2bN.
3. b(a3N) = 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 ⇒ 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 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 really have an isomorphism, K ≋ G.

# The Quaternion Group, Q4

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, and we also have 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 ⇒ b = aba. Futhermore, a2 = b2 = (aba)(aba) = aba2ba = abb2ba = ab4a ⇒ a2 = ab4a ⇒ a = ab4 ⇒ e = b4.

Hence, there are at most four elements in H (e, b, b2, b3) and therefore, at most eight in Q4, 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. 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⟩, G = H ∪ aH ∪ a2H. Therefore, G = {aibj | 0 ≤ i ≤ 2, 0 ≤ j ≤ 8} ⇒ |G| ≤ 27.

a-1ba = b-1 ⇒ b = (a-1ba)-1 = a-1b-1a

b = ebe = [a3 = e ⇒ a-3 = e] a-3ba3 = a-2(a-1ba)a2 = a-2b-1a2 = a-1(a-1b-1a)a = a-1ba = b-1 ⇒ [b = b-1] b2 = e = b9 ⇒ b = e ⇒ G has at most three elements (a, a2, and e), and ℤ3 satisfy the defining relations with a = 1 and 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 ⇒ a = a -1 ⇒ ∀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: ℤ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 is isomorphic to ℤ8, ℤ4⊕ℤ2, ℤ2⊕ℤ2⊕ℤ2.

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., satisfy 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| = 2, 4 or 8. By the previous lemma, 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 goes |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) ⇒ [By Lagrange’s Theorem, H = ⟨a⟩, |G|=8 = [G:H]·|H| = [G:H]·4] Therefore there are two cosets, G = ⟨a⟩ ∪ ⟨a⟩b = {e, a, a2, a3, b, ab, a2b, a3b}.

{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 beca use b2 commute with b (b2b = bb2), but a does not (ab ≠ ba because since {a, b} generates G, this makes G an Abelian group).
• 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 (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. Used 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 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.

Let G be a group generated by a pair of elements of order 2, a and b. If |ab| = ∞ ⇒ G is infinite and satisfies the relations of D. We claim that G is indeed isomorphic to D.

By Dick’s Theorem, G is isomorphic to some factor group of D, say D/H. Let’s take an element h ∈ H, h ≠ e. Every element of D has one of the following forms: (ab)i, (ba)i, (ab)ia or (ba)i. By symmetry, we could assume that h = (ab)i or h = (ab)ia

• If h = (ab)i, D/H satisfies the defining relations for Di defined as ⟨x, y| x2 = yi=e, xyx = y-1⟩.

Since (ab)i ∈ H by assumption ⇒ H = (ab)iH = (abH)i (ii) ⇒ (abH)-1 = (abH)i-1.

(ab)-1H = [Sock and shoes Theorem] b-1a-1H = [By assumption a and b have order 2] baH.

We need to show that it satisfies the relation xyx = y-1, x = aH, y = abH ↭ [Lemma ⟨a, b⟩ = ⟨a, ab⟩] aHabHaH = (abH)-1.

aHabHaH = a2HbHaH = eHbaH = baH = (ab)-1H = (abH)-1 (iii)

Thus, G ≈ D/H = ⟨aH, bH⟩ = ⟨aH, abH⟩ satisfies the defining relation for Di: (aH)2 = H (i), (abH)i=H (ii), aHabHaH = (abH)-1 (iii) In particular, G is finite ⊥

• If h = (ab)ia ⇒ H = (ab)iaH = (ab)iHaH ⇒ [(ab)iH = (aH)-1] (abH)i = (ab)iH = (aH)-1 = a-1H = [|a| = 2] aH, so aH = (abH)i

Therefore, ⟨aH, bH⟩ = ⟨aH, abH⟩ ⊆ ⟨abH⟩

(abH)2i = [aH = (abH)i] (aH)2 = a2H = H, so again G ≈ D/H is again finite ⊥ ⇒ H = {e}, G ≈ D.

• |ab| = n, G = ⟨a, b⟩ = ⟨a, ab⟩ ⇒ G ≈ Dn = ⟨a, ab| a2 = (ab)n = e, a(ab)a = (ab)-1⟩.

xyx = y-1 ↭ b(ab)b = (ab)-1

(ab)-1 = [Sock and Shoes Theorem] b-1a-1 = [a, b of order 2] ba.

b(ab)b = ba(bb) = [|b|=2, b2=e] ba.

Corollary. G = ⟨x, y| x2 = yn = e, xyx = y-1⟩ ≈ Dn.

⟨x, y⟩ = [Previous Lemma] ⟨x, xy⟩

(xy)2 = (xy)(xy) = (xyx)y = [xyx = y-1] y-1y = e, x2 = e ⇒ [Characterization of Dihedral Groups. Any group generated by a pair of elements of order 2 is dihedral.] G is isomorphic to a dihedral group. Futhermore, |x(xy)| = |y| = n ⇒ [Last case of Characterization of Dihedral Group, |ab|=n] G ≈ Dn

Bitcoin donation 