Chapter 3: Groups

Question 1

Define the terms group and abelian group

Answer 1

Group criteria:

1. It is closed under the operation
2. The operation is associative on the group
3. The operation has an identity element
4. Every element of the group has an inverse under the operation

Abelian group criteria:

5. The operation is commutative on the group

Question 2

Give examples of groups:

1. The trivial group (abelian!)
2. Groups from fields
3. The general and special linear groups
4. The symmetry groups of geometrical figures
5. Groups abstractly defined from presentations

Answer 2

1. Let G = {𝒆}, with the operation defined so that 𝒆𝒆 = 𝒆
   
   1. The defined operation means this set is closed
   2. (𝒆𝒆)𝒆 = 𝒆𝒆 = 𝒆 = 𝒆𝒆 = 𝒆(𝒆𝒆)
   3. This set contains one identity element
   4. The identity element is self-inverse, i.e. 𝒆 = 𝒆^-1, so this set contains every element’s inverse
   5. 𝒆₁𝒆₂ = 𝒆 = 𝒆₂𝒆₁ (not sure if valid to write this way but you see what I mean)
2. Under addition: ℂ, ℝ, ℚ, ℤ, ℚ(√2)
   Under modular addition: ℤ_p;
   Under multiplication: ℂ^*, ℝ^*, ℚ^*, ℚ(√2)
   Under modular multiplication: ℤ_p^*
3. The set of invertible n × n matrices GL_n(𝔽) (the general linear group) and SL_n(𝔽) (the special linear group, where each has det 1)
4. The set of symmetries of a geometrical figure Φ, Sym(Φ) is a group, where Sym(P_𝒏) is the dihedral group Dih(2𝒏)/D_𝒏, which is finite and contains 2𝒏 elements, with 𝒏 rotations through the centre and 𝒏 reflections
5. A presentation of G, e.g. <𝒙|𝒙^𝒏>, is a group (this one specifically is a cyclic group, called C_𝒏; x¹ to x^𝒏-1 are in this set, and x^𝒏 is the identity element)

Question 3

Let α = (1 3)(2 4), β = (1 2 3 4) and γ = (1 3)

Compose the following permutations:

1. αβ (α∘β)
2. βγ (β∘γ)
3. γα (γ∘α)
4. αβγ (α∘β∘γ)

Answer 3

1. (1 4 3 2)
2. (1 4)(2 3)
3. (1 3)(2 4)
4. (1 2)(3 4)

Question 4

Prove that permutations can always be expressed as products of disjoint cycles

Answer 4

1. Let α be a permutation of {1, …, 𝒏} and 𝒌 ∈ {1, …, 𝒏}
2. By applying α repeatedly, we obtain the points 𝒌, α(𝒌), α²(𝒌) = α(α(𝒌)), …
3. As two of these must coincide [because we are permuting a finite set of integers; there is a finite set of “target” options to choose from], we see that there are integers 𝒑 and 𝒒 with 𝒑 < 𝒒 such that α^𝒑(𝒌) = α^𝒒(𝒌) and importantly, one of these will be equal to 𝒌 - which might not be the case using other algorithms e.g. in cryptography
4. Since α^-1 exists [because α ∈ S_𝒏, which is a group and thus contains every element’s inverse], α^𝒑-𝒒(𝒌) = 𝒌 [e.g. …]
5. Now let 𝒖 be the smallest positive integer with the property that α^𝒖(𝒌) = 𝒌; then

Question 5

Prove that every permutation is either even or odd (3 steps incl. 1 lemma)

Answer 5

1. Suppose 𝒕₁…𝒕_𝒑 = 𝒓₁…𝒓_𝒒, where each 𝒕_𝒋 and 𝒓_𝒋 is a transposition
2. Then 𝒕₁…𝒕_𝒑𝒓₁…𝒓_𝒒 = 𝒆, so by Lemma 202 (below) 𝒑+𝒒 is even
3. It follows that either 𝒑 and 𝒒 are both even, or they are both odd

Lemma 202:

An expression of the identity permutation 𝒆 on {1, 2, …, 𝒏} can only use 𝒎 transpositions if 𝒎 is even.

Question 6

Determine if the following permutations are odd or even:

1. (1 3)(2 4)
2. (1 3 5)(2 4)(6 7 8)

(There are two ways: think of 𝒒 vs 𝒎.)

Answer 6

If α is a cycle of length 𝒒, then sign(α) = (-1)^𝒒+1.

1. Even (we have cycles of length 2 and 2 here, and (-1)³(-1)³ = 1)
2. Odd (we have cycles of length 3, 2 and 3 here, and (-1)⁴(-1)³(-1)⁴ = -1)

Alternatively, we can use sign(α) = (-1)^𝒎, where α is a product of 𝒎 transpositions. Then:

1. 𝒎 = 2 so this permutation is even
2. (1 3 5)(2 4)(6 7 8) = (1 5)(1 3)(2 4)(6 8)(6 7) so 𝒎 = 5 and this permutation is odd

Question 7

Define the terms symmetric group and alternating group

Answer 7

The symmetric group S_𝒏 is the group defined over the set of 𝒏 elements. Each element in the group is a permutation of the set of 𝒏 elements. The group operation is function composition.

The alternating group A_𝒏 is the set of even permutations of S_𝒏.

Question 8

Let G be a group and let 𝒂, 𝒃 ∈ G.

Prove that:

1. the identity element in G is unique
2. inverses in a group are also unique
3. if 𝒂𝒙 = 𝒃𝒙 then 𝒂 = 𝒃, and similarly if 𝒙𝒂 = 𝒙𝒃 then 𝒂 = 𝒃
4. the equation 𝒂𝒙 = 𝒃 has a unique solution in G, namely 𝒙 = 𝒂^-1𝒃, and similarly 𝒙𝒂 = 𝒃 has a unique solution which is 𝒃𝒂^-1
5. 𝒆 is the unique solution of 𝒙𝒙 = 𝒙
6. (𝒂𝒃)^-1 = 𝒃^-1𝒂^-1

Answer 8

1. G has at least one identity element, by definition of a group. Suppose 𝒆 and 𝒇 are identity elements of G. Then, since 𝒆 is an identity element, we have that 𝒆𝒇 = 𝒇𝒆 = 𝒇. But as 𝒇 is also an identity element, we also have 𝒇𝒆 = 𝒆𝒇 = 𝒆. Hence 𝒆 = 𝒇 and we have exactly one identity element.
2. Let 𝒉, 𝒉’ ∈ G be two inverses of 𝒂, so they have the properties that 𝒉𝒂 = 𝒂𝒉 = 𝒆 and 𝒉’𝒂 = 𝒂𝒉’ = 𝒆. We see that 𝒉 = 𝒉𝒆 = 𝒉(𝒂𝒉’) = (𝒉𝒂)𝒉’ = 𝒆𝒉’ = 𝒉’, i.e. 𝒉 = 𝒉’. As 𝒂𝒂^-1 = 𝒂^-1𝒂 = 𝒆, it’s clear that (𝒂^-1)^-1 = 𝒂.
3. if 𝒂𝒙 = 𝒃𝒙 then (𝒂𝒙)𝒙^-1 = (𝒃𝒙)𝒙^-1. Now (𝒂𝒙)𝒙^-1 = 𝒂(𝒙𝒙^-1) = 𝒂𝒆 = 𝒂, and similarly when 𝒂 is replaced by 𝒃 (so LHS becomes 𝒂 and RHS becomes 𝒃). The 𝒙𝒂 = 𝒙𝒃 statement follows in a similar way.
4. As 𝒂(𝒂^-1𝒃) = (𝒂𝒂^-1)𝒃 = 𝒆𝒃 = 𝒃, we see that 𝒂^-1𝒃 is a solution of 𝒂𝒙 = 𝒃. For uniqueness, suppose 𝒚₁ and 𝒚₂ are solutions. Then 𝒂𝒚₁ = 𝒃 = 𝒂𝒚₂, so by Lemma 210 (point 3 in this list) 𝒚₁ = 𝒚₂. The proof of the second statement is similar.
5. As 𝒚𝒆 = 𝒚 for every 𝒚 ∈ G, we see that if 𝒚 = 𝒆 then 𝒆𝒆 = 𝒆. It follows that 𝒆 is a solution of 𝒙𝒙 = 𝒙. For uniqueness, if 𝒙𝒙 = 𝒙 then 𝒙𝒙 = 𝒙𝒆. By Lemma 210 (point 3 above), we must therefore have that 𝒙 = 𝒆.
6. Observe that (𝒃^-1𝒂^-1)(𝒂𝒃) = 𝒃^-1(𝒂^-1𝒂)𝒃 = 𝒃^-1𝒆𝒃 = 𝒃^-1𝒃 = 𝒆, and (𝒂𝒃)(𝒃^-1𝒂^-1) = 𝒂(𝒃𝒃^-1)𝒂^-1 = 𝒂𝒆𝒂^-1 = 𝒂𝒂^-1 = 𝒆. We have shown that 𝒃^-1𝒂^-1 is the inverse of 𝒂𝒃, i.e. like 𝒂’𝒂 = 𝒆 = 𝒂𝒂’.

Question 9

Define the term subgroup

Answer 9

Let (G, *) be a group with identity 𝒆.

A non-empty subset H of G is a subgroup of G if (H, *) is a group.

We write H ≤ G.

We call H a proper subgroup if H ≠ G and a non-trivial subgroup if H ≠ {𝒆}.

(Note that the operation in the subgroup must be the same.)

Question 10

State and prove the subgroup criterion

Answer 10

Let G be a group and let H be a non-empty subset of G.

Then H is a subgroup of G iff H satisfies:

1. for all 𝒉, 𝒌 in H, 𝒉𝒌 ∈ H
2. for all 𝒉 in H, 𝒉^-1 ∈ H

Proof:

If H is a subgroup, then by definition it satisfies both of the conditions above.

Now to show that H is a group (and thus a subgroup of G…?):

1. H is closed under the operation because of condition 1 above
2. Since the operation in G is associative, H inherits this property
3. As H is non-empty there exists 𝒉 ∈ H. By condition 2 above, 𝒉^-1 ∈ H and by condition 1 above, 𝒉𝒉^-1 ∈ H, and (by definition of an inverse?) 𝒉𝒉^-1 = 𝒆, so H contains an identity element
4. By condition 2 above, H contains the inverse of each of its elements

Question 11

State and prove the finite subgroup criterion

Answer 11

TBC

Question 12

Define the order of a group and of its elements

Answer 12

TBC

Question 13

Calculate the orders of the following elements in their given group:

1.
2.
3.
4.

Answer 13

TBC

Question 14

State and prove Lagrange’s Theorem

Answer 14

TBC

Question 15

State and prove n corollaries of Lagrange’s Theorem

Answer 15

TBC

Question 16

Define the terms homomorphism and isomorphism

Answer 16

TBC

Question 17

Prove the following simple properties of homomorphisms:

1.
2.
3.

Answer 17

TBC

Question 18

Define the terms kernel and image

Answer 18

TBC

Question 19

Prove that kernel and image are subgroups

Answer 19

TBC

Question 20

Determine if the following pairs of groups are isomorphic or not.

1.
2.
3.

Answer 20

TBC

Question 21

How many elements exist in GL_n(Z_p)?

Answer 21

|GL_n(Z_p)| = (pⁿ - 1)(pⁿ - p)(pⁿ - p²) … (pⁿ - p^n-1)

Question 22

What are the three criteria for a relation, 𝐑, on a set, 𝐗, to be considered an equivalence relation?

What is the notation for an equivalence relation?

What is an equivalence class?

Answer 22

1. Reflexive, i.e. for 𝒙 ∈ 𝐗, we have that 𝒙𝐑𝒙
2. Symmetric, i.e. for 𝒙, 𝒚 ∈ 𝐗, we have that 𝒙𝐑𝒚 whenever 𝒚𝐑𝒙
3. Transitive, i.e. for 𝒙, 𝒚, 𝒛 ∈ 𝐗, we have that 𝒙𝐑𝒛 whenever 𝒙𝐑𝒚 and 𝒚𝐑𝒛

If 𝐑 is an equivalence relation, we use ~ instead of 𝐑.

An equivalence class is a set containing all the elements from the other set that are equivalent to 𝒙:
[𝒙] = { 𝒚 ∈ 𝐗 : 𝒚 ~ 𝒙 }

Question 23

What is ℚ(√2)?

Answer 23

ℚ(√2) is usually defined as the smallest field containing all rational numbers and √2.

ℚ(√2) = {𝒂 + 𝒃√2: 𝒂, 𝒃 ∈ ℚ}

(A field is a set on which addition, subtraction, multiplication and division are defined, and behave as the corresponding operations on ℚ and ℝ do.)

Question 24

Where are the lines of reflection for a two-dimensional n-sided polygon when:

1. n is odd?
2. n is even?

Answer 24

1. if n is odd, all reflections are about lines that pass through a corner and the mid-point of the opposite side
2. if n is even, then half the reflections are about lines that pass through the mid-points of an opposite pair of sides while the other half are about lines that pass through the opposite pair of corners