Chapter 2

Groups

Groups are the central objects of algebra. In later chapters we will define rings and modules and see that they are special cases of groups. Also ring homomorphisms and module homomorphisms are special cases of group homomorphisms. Even though the definition of group is simple, it leads to a rich and amazing theory. Everything presented here is standard, except that the product of groups is given in the additive notation. This is the notation used in later chapters for the products of rings and modules. This chapter and the next two chapters are restricted to the most basic topics. The approach is to do quickly the fundamentals of groups, rings, and matrices, and to push forward to the chapter on linear algebra. This chapter is, by far and above, the most difficult chapter in the book, because group operations may be written as addition or multiplication, and also the concept of coset is confusing at first.

Definition Suppose G is a non-void set and ϕ : G × G → G is a function. ϕ is called a binary operation, and we will write ϕ(a, b) = a·b or ϕ(a, b) = a+b. Consider the following properties.

1) If a, b, c ∈ G then a · (b · c) = (a · b) · c. If a, b, c ∈ G then a + (b + c) = (a + b) + c.

2) ∃ e = e_{G} ∈ G such that if a ∈ G ∃ ¯0=¯0_{G} ∈ G such that if a ∈ G

e · a = a · e = a.  ¯0+a = a+¯0= a.

3) If a ∈ G, ∃b ∈ G with a · b = b · a = e If a ∈ G, ∃b ∈ G with a + b = b + a = ¯0 (b is written as b = a^{−1}). (b is written as b = −a).

4) If a, b ∈ G, then a · b = b · a. If a, b ∈ G, then a + b = b + a.

Definition If properties 1), 2), and 3) hold, (G, ϕ) is said to be a group. If we write ϕ(a, b) = a · b, we say it is a multiplicative group. If we write ϕ(a, b) = a + b, we say it is an additive group. If in addition, property 4) holds, we say the group is abelian or commutative.

Theorem Let (G, ϕ) be a multiplicative group.

(i) Suppose a, c, c̄ ∈ G. Then a · c = a · c̄ ⇒ c = c̄.

Also c · a = c̄ · a ⇒ c = c̄. In other words, if f : G → G is defined by f(c) = a · c, then f is injective. Also f is bijective with f^{−1} given by f^{−1}(c) = a^{−1} · c.

(ii) e is unique, i.e., if ē ∈ G satisfies 2), then e = ē. In fact, if a, b ∈ G then (a · b = a) ⇒ (b = e) and (a · b = b) ⇒ (a = e). Recall that b is an identity in G provided it is a right and left identity for any a in G. However, group structure is so rigid that if ∃ a ∈ G such that b is a right identity for a, then b = e. Of course, this is just a special case of the cancellation law in (i).

(iii) Every right inverse is an inverse, i.e., if a · b = e then b = a^{−1}. Also if b · a = e then b = a^{−1}. Thus inverses are unique.

(iv) If a ∈ G, then (a^{−1})^{−1} = a.

(v) The multiplication a_{1} ·a_{2} ·a_{3} = a_{1} ·(a_{2} ·a_{3}) = (a_{1} ·a_{2})·a_{3} is well-defined. In general, a_{1} · a_{2} ⋯ a_{n} is well defined.

(vi) If a, b ∈ G, (a · b)^{−1} = b^{−1} · a^{−1}. Also (a_{1} · a_{2} ⋯ a_{n})^{−1} = a_{n}^{−1} · a_{n−1}^{−1} ⋯ a_{1}^{−1}.

(vii) Suppose a ∈ G. Let a^{0} = e and if n > 0, a^{n} = a ⋯ a (n times) and a^{−n} = a^{−1} ⋯ a^{−1} (n times). If n_{1}, n_{2}, ..., n_{t} ∈ Z then a^{n_{1}} · a^{n_{2}} ⋯ a^{n_{t}} = a^{n_{1}+···+n_{t}}. Also (a^{n})^{m} = a^{nm}. Finally, if G is abelian and a, b ∈ G, then (a · b)^{n} = a^{n} · b^{n}.

Exercise. Write out the above theorem where G is an additive group. Note that part (vii) states that G has a scalar multiplication over Z. This means that if a is in G and n is an integer, there is defined an element an in G. This is so basic, that we state it explicitly.

Theorem. Suppose G is an additive group. If a ∈ G, let a0 =¯0 and if n > 0, let an = (a + · · +a) where the sum is n times, and a(−n) = (−a) + (−a) · · + (−a), which we write as (−a − a · · − a). Then the following properties hold in general, except the first requires that G be abelian.

(a + b)n = an + bn a(n + m) = an + am a(nm) = (an)m a1 = a

Note that the plus sign is used ambiguously — sometimes for addition in G and sometimes for addition in Z. In the language used in Chapter 5, this theorem states that any additive abelian group is a Z-module. (See page 71.)

Exercise Suppose G is a non-void set with a binary operation ϕ(a, b) = a·b which satisfies 1), 2) and [ 3′) If a ∈ G, ∃b ∈ G with a · b = e]. Show (G, ϕ) is a group, i.e., show b · a = e. In other words, the group axioms are stronger than necessary. If every element has a right inverse, then every element has a two sided inverse.

Exercise Suppose G is the set of all functions from Z to Z with multiplication defined by composition, i.e., f · g = f ∘ g. Note that G satisfies 1) and 2) but not 3), and thus G is not a group. Show that f has a right inverse in G iff f is surjective, and f has a left inverse in G iff f is injective (see page 10). Also show that the set of all bijections from Z to Z is a group under composition.

Examples G = R, G = Q, or G = Z with ϕ(a, b) = a + b is an additive abelian group.

Examples G = R − 0 or G = Q − 0 with ϕ(a, b) = ab is a multiplicative abelian group. G = Z − 0 with ϕ(a, b) = ab is not a group. G = R^{+} = {r ∈ R : r > 0} with ϕ(a, b) = ab is a multiplicative abelian group.

Subgroups

Theorem Suppose G is a multiplicative group and H ⊂ G is a non-void subset satisfying

1) if a, b ∈ H then a · b ∈ H

and 2) if a ∈ H then a^{−1} ∈ H.

Then e ∈ H and H is a group under multiplication. H is called a subgroup of G.

Proof Since H is non-void, ∃a ∈ H. By 2), a^{−1} ∈ H and so by 1), e ∈ H. The associative law is immediate and so H is a group.

Example G is a subgroup of G and e is a subgroup of G. These are called the improper subgroups of G.

Example If G = Z under addition, and n ∈ Z, then H = nZ is a subgroup of Z. By a theorem in the section on the integers in Chapter 1, every subgroup of Z is of this form (see page 15). This is a key property of the integers.

Exercises Suppose G is a multiplicative group.

1) Let H be the center of G, i.e., H = {h ∈ G : g · h = h · g for all g ∈ G}. Show H is a subgroup of G.

2) Suppose H_{1} and H_{2} are subgroups of G. Show H_{1} ∩ H_{2} is a subgroup of G.

3) Suppose H_{1} and H_{2} are subgroups of G, with neither H_{1} nor H_{2} contained in the other. Show H_{1} ∪ H_{2} is not a subgroup of G.

4) Suppose T is an index set and for each t ∈ T, H_{t} is a subgroup of G. Show ⋂_{t∈T}H_{t} is a subgroup of G.

5) Furthermore, if {H_{t}} is a monotonic collection, then ⋃_{t∈T}H_{t} is a subgroup of G.

6) Suppose G= {all functions f : [0, 1] → R}. Define an addition on G by (f + g)(t) = f(t) + g(t) for all t ∈ [0, 1]. This makes G into an abelian group. Let K be the subset of G composed of all differentiable functions. Let H be the subset of G composed of all continuous functions. What theorems in calculus show that H and K are subgroups of G? What theorem shows that K is a subset (and thus subgroup) of H?

Order Suppose G is a multiplicative group. If G has an infinite number of elements, we say that o(G), the order of G, is infinite. If G has n elements, then o(G) = n. Suppose a ∈ G and H = {a^{i} : i ∈ Z}. H is an abelian subgroup of G called the subgroup generated by a. We define the order of the element a to be the order of H, i.e., the order of the subgroup generated by a. Let f : Z → H be the surjective function defined by f(m) = a^{m}. Note that f(k + l) = f(k) · f(l) where the addition is in Z and the multiplication is in the group H. We come now to the first real theorem in group theory. It says that the element a has finite order iff f is not injective, and in this case, the order of a is the smallest positive integer n with a^{n} = e.

Theorem Suppose a is an element of a multiplicative group G, and H = {a^{i} : i ∈ Z}. If ∃ distinct integers i and j with a^{i} = a^{j}, then a has some finite order n. In this case H has n distinct elements, H = {a^{0}, a^{1}, …, a^{n−1}}, and a^{m} = e iff n|m. In particular, the order of a is the smallest positive integer n with a^{n} = e, and f^{−1}(e) = nZ.

Proof Suppose j < i and a^{i} = a^{j}. Then a^{i−j} = e and thus ∃ a smallest positive integer n with a^{n} = e. This implies that the elements of {a^{0}, a^{1}, ..., a^{n−1}} are distinct, and we must show they are all of H. If m ∈ Z, the Euclidean algorithm states that ∃ integers q and r with 0 ≤ r < n and m = nq + r. Thus a^{m} = a^{nq} · a^{r} = a^{r}, and so H = {a^{0}, a^{1}, ..., a^{n−1}}, and a^{m} = e iff n|m. Later in this chapter we will see that f is a homomorphism from an additive group to a multiplicative group and that, in additive notation, H is isomorphic to Z or Z_{n}.

Exercise Write out this theorem for G an additive group. To begin, suppose a is an element of an additive group G, and H = {ai : i ∈ Z}.

Exercise Show that if G is a finite group of even order, then G has an odd number of elements of order 2. Note that e is the only element of order 1.

Definition A group G is cyclic if ∃ an element of G which generates G.

Theorem If G is cyclic and H is a subgroup of G, then H is cyclic.

Proof Suppose G = {a^{i} : i ∈ Z} is a cyclic group and H is a subgroup of G. If H = e, then H is cyclic, so suppose H ≠ e. Now there is a smallest positive integer m with a^{m} ∈ H. If t is an integer with a^{t} ∈ H, then by the Euclidean algorithm, m divides t, and thus a^{m} generates H. Note that in the case G has finite order n, i.e., G = {a^{0}, a^{1}, …, a^{n−1}}, then a^{n} = e ∈ H, and thus the positive integer m divides n. In either case, we have a clear picture of the subgroups of G. Also note that this theorem was proved on page 15 for the additive group Z.

Cosets Suppose H is a subgroup of a group G. It will be shown below that H partitions G into right cosets. It also partitions G into left cosets, and in general these partitions are distinct.

Theorem If H is a subgroup of a multiplicative group G, then a ∼ b defined by a ∼ b iff a · b^{−1} ∈ H is an equivalence relation. If a ∈ G, cl(a) = {b ∈ G : a ∼ b} = {h · a : h ∈ H} = Ha. Note that a · b^{−1} ∈ H iff b · a^{−1} ∈ H.

If H is a subgroup of an additive group G, then a ∼ b defined by a ∼ b iff (a − b) ∈ H is an equivalence relation. If a ∈ G, cl(a) = {b ∈ G : a ∼ b} = {h + a : h ∈ H} = H + a. Note that (a − b) ∈ H iff (b − a) ∈ H.

Definition These equivalence classes are called right cosets. If the relation is defined by a ∼ b iff b^{−1} · a ∈ H, then the equivalence classes are cl(a) = aH and they are called left cosets. H is a left and right coset. If G is abelian, there is no distinction between right and left cosets. Note that b^{−1} · a ∈ H iff a^{−1} · b ∈ H.

In the theorem above, H is used to define an equivalence relation on G, and thus a partition of G. We now do the same thing a different way. We define the right cosets directly and show they form a partition of G. You might find this easier.

Theorem Suppose H is a subgroup of a multiplicative group G. If a ∈ G, define the right coset containing a to be Ha = {h · a : h ∈ H}. Then the following hold.

1) Ha = H iff a ∈ H.

2) If b ∈ Ha, then Hb = Ha, i.e., if h ∈ H, then H(h · a) = (Hh)a = Ha.

3) If Hc ∩ Ha ≠ ∅, then Hc = Ha.

4) The right cosets form a partition of G, i.e., each a in G belongs to one and only one right coset.

5) Elements a and b belong to the same right coset iff a · b^{−1} ∈ H iff b · a^{−1} ∈ H.

Proof There is no better way to develop facility with cosets than to prove this theorem. Also write this theorem for G an additive group.

Theorem Suppose H is a subgroup of a multiplicative group G.

1) Any two right cosets have the same number of elements. That is, if a, b ∈ G, f : Ha → Hb defined by f(h · a) = h · b is a bijection. Also any two left cosets have the same number of elements. Since H is a right and left coset, any two cosets have the same number of elements.

2) G has the same number of right cosets as left cosets. The function F defined by F (Ha) = a^{−1}H is a bijection from the collection of right cosets to the left cosets. The number of right (or left) cosets is called the index of H in G.

3) If G is finite, o(H) (index of H) = o(G) and so o(H) | o(G). In other words, o(G)/o(H) = the number of right cosets = the number of left cosets.

4) If G is finite, and a ∈ G, then o(a) | o(G). (Proof: The order of a is the order of the subgroup generated by a, and by 3) this divides the order of G.)

5) If G has prime order, then G is cyclic, and any element (except e) is a generator. (Proof: Suppose o(G) = p and a ∈ G, a ≠ e. Then o(a) | p and thus o(a) = p.)

6) If o(G) = n and a ∈ G, then a^{n} = e. (Proof: a^{o(a)} = e and n = o(a) (o(G)/o(a)) .)

Exercises

i) Suppose G is a cyclic group of order 4, G = {e, a, a^{2}, a^{3}} with a^{4} = e. Find the order of each element of G. Find all the subgroups of G.

ii) Suppose G is the additive group Z and H = 3Z. Find the cosets of H.

iii) Think of a circle as the interval [0, 1] with end points identified. Suppose G = R under addition and H = Z. Show that the collection of all the cosets of H can be thought of as a circle.

iv) Let G = R^{2} under addition, and H be the subgroup defined by H = {(a, 2a) : a ∈ R}. Find the cosets of H. (See the last exercise on p 5.)

Normal Subgroups

We would like to make a group out of the collection of cosets of a subgroup H. In general, there is no natural way to do that. However, it is easy to do in case H is a normal subgroup, which is described below.

Theorem If H is a subgroup of a group G, then the following are equivalent.

1) If a ∈ G, then aHa^{−1} = H

2) If a ∈ G, then aHa^{−1} ⊂ H

3) If a ∈ G, then aH = Ha

4) Every right coset is a left coset, i.e., if a ∈ G, ∃ b ∈ G with Ha = bH.

Proof 1) ⇒ 2) is obvious. Suppose 2) is true and show 3). We have (aHa^{−1})a ⊂ Ha so aH ⊂ Ha. Also a(a^{−1}Ha) ⊂ aH so Ha ⊂ aH. Thus aH = Ha.

3) ⇒ 4) is obvious. Suppose 4) is true and show 3). Ha = bH contains a, so bH = aH because a coset is an equivalence class. Thus aH = Ha. Finally, suppose 3) is true and show 1). Multiply aH = Ha on the right by a^{−1}.

Definition If H satisfies any of the four conditions above, then H is said to be a normal subgroup of G. (This concept goes back to Evariste Galois in 1831.)

Note For any group G, G and e are normal subgroups. If G is an abelian group, then every subgroup of G is normal.

Exercise Show that if H is a subgroup of G with index 2, then H is normal.

Exercise Show the intersection of a collection of normal subgroups of G is a normal subgroup of G. Show the union of a monotonic collection of normal subgroups of G is a normal subgroup of G.

Exercise Let A ⊂ R^{2} be the square with vertices (−1, 1), (1, 1), (1, −1), and (−1, −1), and G be the collection of all “isometries” of A onto itself. These are bijections of A onto itself which preserve distance and angles, i.e., which preserve dot product. Show that with multiplication defined as composition, G is a multiplicative group. Show that G has four rotations, two reflections about the axes, and two reflections about the diagonals, for a total of eight elements. Show the collection of rotations is a cyclic subgroup of order four which is a normal subgroup of G. Show that the reflection about the x-axis together with the identity form a cyclic subgroup of order two which is not a normal subgroup of G. Find the four right cosets of this subgroup. Finally, find the four left cosets of this subgroup.

Quotient Groups Suppose N is a normal subgroup of G, and C and D are cosets. We wish to define a coset E which is the product of C and D. If c ∈ C and d ∈ D, define E to be the coset containing c · d, i.e., E = N(c · d). The coset E does not depend upon the choice of c and d. This is made precise in the next theorem, which is quite easy.

Theorem Suppose G is a multiplicative group, N is a normal subgroup, and G/N is the collection of all cosets. Then (Na) · (Nb) = N(a · b) is a well defined multiplication (binary operation) on G/N, and with this multiplication, G/N is a group. Its identity is N and (Na)^{−1} = (Na^{−1}). Furthermore, if G is finite, o(G/N) = o(G)/o(N).

Proof Multiplication of elements in G/N is multiplication of subsets in G. (Na) · (Nb) = N(aN)b = N(Na)b = N(a · b). Once multiplication is well defined, the group axioms are immediate.

Exercise Write out the above theorem for G an additive group. In the additive abelian group R/Z, determine those elements of finite order.

Example Suppose G = Z under +, n > 1, and N = nZ. Z_{n}, the group of integers mod n is defined by Z_{n} = Z/nZ. If a is an integer, the coset a + nZ is denoted by [a]. Note that [a] + [b] = [a + b], −[a] = [−a], and [a] = [a + nl] for any integer l. Any additive abelian group has a scalar multiplication over Z, and in this case it is just [a]m = [am]. Note that [a] = [r] where r is the remainder of a divided by n, and thus the distinct elements of Z_{n} are [0], [1], ..., [n − 1]. Also Z_{n} is cyclic because each of [1] and [−1] = [n − 1] is a generator. We already know that if p is a prime, any non-zero element of Z_{p} is a generator, because Z_{p} has p elements.

Theorem If n > 1 and a is any integer, then [a] is a generator of Z_{n} iff (a, n) = 1.

Proof The element [a] is a generator iff the subgroup generated by [a] contains [1] iff ∃ an integer k such that [a]k = [1] iff ∃ integers k and l such that ak + nl = 1.

Exercise Show that a positive integer is divisible by 3 iff the sum of its digits is divisible by 3. Note that [10] = [1] in Z_{3}. (See the fifth exercise on page 18.)

Homomorphisms

Homomorphisms are functions between groups that commute with the group operations. It follows that they honor identities and inverses. In this section we list the basic properties. Properties 11), 12), and 13) show the connections between coset groups and homomorphisms, and should be considered as the cornerstones of abstract algebra. As always, the student should rewrite the material in additive notation.

Definition If G and Ḡ are multiplicative groups, a function f : G → Ḡ is a homomorphism if, for all a, b ∈ G, f(a · b) = f(a) · f(b). On the left side, the group operation is in G, while on the right side it is in Ḡ. The kernel of f is defined by ker(f) = f^{−1}(ē) = {a ∈ G : f(a) = ē}. In other words, the kernel is the set of solutions to the equation f(x) = ē. (If Ḡ is an additive group, ker(f) = f^{−1}(¯0).)

Examples The constant map f : G → Ḡ defined by f(a) = ē is a homomorphism. If H is a subgroup of G, the inclusion i : H → G is a homomorphism. The function f : Z → Z defined by f(t) = 2t is a homomorphism of additive groups, while the function defined by f(t) = t + 2 is not a homomorphism. The function h : Z → R − 0 defined by h(t) = 2^{t} is a homomorphism from an additive group to a multiplicative group.

We now catalog the basic properties of homomorphisms. These will be helpful later on in the study of ring homomorphisms and module homomorphisms.

Theorem Suppose G and Ḡ are groups and f : G → Ḡ is a homomorphism.

1) f(e) = ē.

2) f(a^{−1}) = f(a)^{−1}. The first inverse is in G, and the second is in Ḡ.

3) f is injective ⇔ ker(f) = e.

4) If H is a subgroup of G, f(H) is a subgroup of Ḡ. In particular, image(f) is a subgroup of Ḡ.

5) If H̄ is a subgroup of Ḡ, f^{−1}(H̄) is a subgroup of G. Furthermore, if H̄ is normal in Ḡ, then f^{−1}(H̄) is normal in G.

6) The kernel of f is a normal subgroup of G.

7) If ḡ ∈ Ḡ, f^{−1}(ḡ) is void or is a coset of ker(f), i.e., if f(g) = ḡ then f^{−1}(ḡ) = Ng where N= ker(f). In other words, if the equation f(x) = ḡ has a solution, then the set of all solutions is a coset of N= ker(f). This is a key fact which is used routinely in topics such as systems of equations and linear differential equations.

8) The composition of homomorphisms is a homomorphism, i.e., if h : Ḡ →G^{=} is a homomorphism, then h ∘ f : G →G^{=} is a homomorphism.

9) If f : G → Ḡ is a bijection, then the function f^{−1} : Ḡ → G is a homomorphism. In this case, f is called an isomorphism, and we write G ≈ Ḡ. In the case G = Ḡ, f is also called an automorphism.

10) Isomorphisms preserve all algebraic properties. For example, if f is an isomorphism and H ⊂ G is a subset, then H is a subgroup of G iff f(H) is a subgroup of Ḡ, H is normal in G iff f(H) is normal in Ḡ, G is cyclic iff Ḡ is cyclic, etc. Of course, this is somewhat of a cop-out, because an algebraic property is one that, by definition, is preserved under isomorphisms.

11) Suppose H is a normal subgroup of G. Then π : G → G/H defined by π(a) = Ha is a surjective homomorphism with kernel H. Furthermore, if f : G → Ḡ is a surjective homomorphism with kernel H, then G/H ≈ Ḡ (see below).

12) Suppose H is a normal subgroup of G. If H ⊂ ker(f), then f̄: G/H → Ḡ defined by f̄(Ha) = f(a) is a well-defined homomorphism making the following diagram commute.

[figure: G; Ḡ; G/H; f; π; f̄]

Thus defining a homomorphism on a quotient group is the same as defining a homomorphism on the numerator which sends the denominator to ē. The image of f̄ is the image of f and the kernel of f̄ is ker(f)/H. Thus if H = ker(f), f̄ is injective, and thus G/H ≈ image(f).

13) Given any group homomorphism f, domain(f)/ker(f) ≈ image(f). This is the fundamental connection between quotient groups and homomorphisms.

14) Suppose K is a group. Then K is an infinite cycle group iff K is isomorphic to the integers under addition, i.e., K ≈ Z. K is a cyclic group of order n iff K ≈ Z_{n}.

Proof of 14) Suppose Ḡ = K is generated by some element a. Then f : Z → K defined by f(m) = a^{m} is a homomorphism from an additive group to a multiplicative group. If o(a) is infinite, f is an isomorphism. If o(a) = n, ker(f) = nZ and f̄: Z_{n} → K is an isomorphism.

Exercise If a is an element of a group G, there is always a homomorphism from Z to G which sends 1 to a. When is there a homomorphism from Z_{n} to G which sends [1] to a? What are the homomorphisms from Z_{2} to Z_{6}? What are the homomorphisms from Z_{4} to Z_{8}?

Exercise Suppose G is a group and g is an element of G, g ≠ e.

1) Under what conditions on g is there a homomorphism f : Z_{7} → G with f([1]) = g ?

2) Under what conditions on g is there a homomorphism f: Z_{15} → G with f([1]) = g ?

3) Under what conditions on G is there an injective homomorphism f : Z_{15} → G ?

4) Under what conditions on G is there a surjective homomorphism f : Z_{15} → G ?

Exercise We know every finite group of prime order is cyclic and thus abelian. Show that every group of order four is abelian.

Exercise Let G = {h : [0, 1] → R : h has an infinite number of derivatives}. Then G is a group under addition. Define f : G → G by f(h) = \frac{dh}{dt} = h′. Show f is a homomorphism and find its kernel and image. Let g : [0, 1] → R be defined by g(t) = t^{3} − 3t + 4. Find f^{−1}(g) and show it is a coset of ker(f).

Exercise Let G be as above and g ∈ G. Define f : G → G by f(h) = h′′ + 5h′ + 6t^{2}h. Then f is a group homomorphism and the differential equation h′′+5h′+6t^{2}h = g has a solution iff g lies in the image of f. Now suppose this equation has a solution and S ⊂ G is the set of all solutions. For which subgroup H of G is S an H-coset?

Exercise Suppose G is a multiplicative group and a ∈ G. Define f : G → G to be conjugation by a, i.e., f(g) = a^{−1} · g · a. Show that f is a homomorphism. Also show f is an automorphism and find its inverse.

Permutations

Suppose X is a (non-void) set. A bijection f : X → X is called a permutation on X, and the collection of all these permutations is denoted by S = S(X). In this setting, variables are written on the left, i.e., f = (x)f. Therefore the composition f ∘g means “f followed by g”. S(X) forms a multiplicative group under composition.

Exercise Show that if there is a bijection between X and Y, there is an isomorphism between S(X) and S(Y). Thus if each of X and Y has n elements, S(X) ≈ S(Y), and these groups are called the symmetric groups on n elements. They are all denoted by the one symbol S_{n}.

Exercise Show that o(S_{n}) = n!. Let X = {1, 2, ..., n}, S_{n} = S(X), and H = {f ∈ S_{n} : (n)f = n}. Show H is a subgroup of S_{n} which is isomorphic to S_{n−1}. Let g be any permutation on X with (n)g = 1. Find g^{−1}Hg.

The next theorem shows that the symmetric groups are incredibly rich and complex.

Theorem (Cayley’s Theorem) Suppose G is a multiplicative group with n elements and S_{n} is the group of all permutations on the set G. Then G is isomorphic to a subgroup of S_{n}.

Proof Let h : G → S_{n} be the function which sends a to the bijection h_{a} : G → G defined by (g)h_{a} = g · a. The proof follows from the following observations.

1) For each given a, h_{a} is a bijection from G to G.

2) h is a homomorphism, i.e., h_{a·b} = h_{a} ∘ h_{b}.

3) h is injective and thus G is isomorphic to image(h) ⊂ S_{n}.

The Symmetric Groups Now let n ≥ 2 and let S_{n} be the group of all permutations on {1, 2, ..., n}. The following definition shows that each element of S_{n} may be represented by a matrix.

Definition Suppose 1 < k ≤ n, {a_{1}, a_{2}, ..., a_{k}} is a collection of distinct integers with 1 ≤ a_{i} ≤ n, and {b_{1}, b_{2}, ..., b_{k}} is the same collection in some different order.

Then the matrix ( \begin{matrix}a_{1} a_{2} ... a_{k} \\ b_{1} b_{2} ... b_{k} \end{matrix} ) represents f ∈ S_{n} defined by (a_{i})f = b_{i} for 1 ≤ i ≤ k,

and (a)f = a for all other a. The composition of two permutations is computed by applying the matrix on the left first and the matrix on the right second.

There is a special type of permutation called a cycle. For these we have a special notation.

Definition ( \begin{matrix}a_{1} a_{2}...a_{k−1}a_{k} \\ a_{2} a_{3}...a_{k} a_{1} \end{matrix} ) is called a k-cycle, and is denoted by (a_{1}, a_{2}, ..., a_{k}).

A 2-cycle is called a transposition. The cycles (a_{1}, ..., a_{k}) and (c_{1}, ..., c_{ℓ}) are disjoint provided a_{i} ≠ c_{j} for all 1 ≤ i ≤ k and 1 ≤ j ≤ ℓ.

Listed here are eight basic properties of permutations. They are all easy except 4), which takes a little work. Properties 9) and 10) are listed solely for reference.

Theorem

1) Disjoint cycles commute. (This is obvious.)

2) Every nonidentity permutation can be written uniquely (except for order) as the product of disjoint cycles. (This is easy.)

3) Every permutation can be written (non-uniquely) as the product of transpositions. (Proof: I = (1, 2)(1, 2) and (a_{1}, ..., a_{k}) = (a_{1}, a_{2})(a_{1}, a_{3}) ⋯ (a_{1}, a_{k}). )

4) The parity of the number of these transpositions is unique. This means that if f is the product of p transpositions and also of q transpositions, then p is even iff q is even. In this case, f is said to be an even permutation. In the other case, f is an odd permutation.

5) A k-cycle is even (odd) iff k is odd (even). For example (1, 2, 3) = (1, 2)(1, 3) is an even permutation.

6) Suppose f, g ∈ S_{n}. If one of f and g is even and the other is odd, then g ∘ f is

odd. If f and g are both even or both odd, then g ∘ f is even. (Obvious.)

7) The map h : S_{n} → Z_{2} defined by h(even)= [0] and h(odd)= [1] is a homomorphism from a multiplicative group to an additive group. Its kernel (the subgroup of even permutations) is denoted by A_{n} and is called the alternating group. Thus A_{n} is a normal subgroup of index 2, and S_{n}/A_{n} ≈ Z_{2}.

8) If a, b, c and d are distinct integers in {1, 2, …, n}, then (a, b)(b, c) = (a, c, b) and (a, b)(c, d) = (a, c, d)(a, c, b). Since I = (1, 2, 3)^{3}, it follows that for n ≥ 3, every even permutation is the product of 3-cycles.

The following parts are not included in this course. They are presented here merely for reference.

9) For any n ≠ 4, A_{n} is simple, i.e., has no proper normal subgroups.

10) S_{n} can be generated by two elements. In fact, {(1, 2), (1, 2, ..., n)} generates S_{n}. (Of course there are subgroups of S_{n} which cannot be generated by two elements).

Proof of 4) It suffices to prove if the product of t transpositions is the identity I on {1, 2, …, n}, then t is even. Suppose this is false and I is written as t transpositions, where t is the smallest odd integer this is possible. Since t is odd, it is at least 3. Suppose for convenience the first transposition is (a, n). We will rewrite I as a product of transpositions σ_{1}σ_{2} ⋯ σ_{t} where (n)σ_{i} = (n) for 1 ≤ i < t and (n)σ_{t} ≠ n, which will be a contradiction. This can be done by inductively “pushing n to the right” using the equations below. If a, b, and c are distinct integers in {1, 2, …, n − 1}, then (a, n)(a, n) = I, (a, n)(b, n) = (a, b)(a, n), (a, n)(a, c) = (a, c)(c, n), and (a, n)(b, c) = (b, c)(a, n). Note that (a, n)(a, n) cannot occur here because it would result in a shorter odd product. (Now you may solve the tile puzzle on page viii.)

Exercise

1) Write ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 6 & 5 & 4 & 3 & 1 & 7 & 2 \end{matrix} ) as the product of disjoint cycles.

Write (1,5,6,7)(2,3,4)(3,7,1) as the product of disjoint cycles. Write (3,7,1)(1,5,6,7)(2,3,4) as the product of disjoint cycles. Which of these permutations are odd and which are even?

2) Suppose (a_{1}, …, a_{k}) and (c_{1}, …, c_{ℓ}) are disjoint cycles. What is the order of their product?

3) Suppose σ ∈ S_{n}. Show that σ^{−1}(1, 2, 3)σ = ((1)σ, (2)σ, (3)σ). This shows that conjugation by σ is just a type of relabeling. Also let τ = (4, 5, 6) and find τ^{−1}(1, 2, 3, 4, 5)τ.

4) Show that H = {σ ∈ S_{6} : (6)σ = 6} is a subgroup of S_{6} and find its right cosets and its left cosets.

5) Let A ⊂ R^{2} be the square with vertices (−1, 1), (1, 1), (1, −1), and (−1, −1), and G be the collection of all isometries of A onto itself. We know from a previous exercise that G is a group with eight elements. It follows from Cayley’s theorem that G is isomorphic to a subgroup of S_{8}. Show that G is isomorphic to a subgroup of S_{4}.

6) If G is a multiplicative group, define a new multiplication on the set G by a ∘ b = b · a. In other words, the new multiplication is the old multiplication in the opposite order. This defines a new group denoted by G^{op}, the opposite group. Show that it has the same identity and the same inverses as G, and that f : G → G^{op} defined by f(a) = a^{−1} is a group isomorphism. Now consider the special case G = S_{n}. The convention used in this section is that an element of S_{n} is a permutation on {1, 2, …, n} with the variable written on the left. Show that an element of S_{n}^{op} is a permutation on {1, 2, …, n} with the variable written on the right. (Of course, either S_{n} or S_{n}^{op} may be called the symmetric group, depending on personal preference or context.)

Product of Groups

The product of groups is usually presented for multiplicative groups. It is presented here for additive groups because this is the form that occurs in later chapters. As an exercise, this section should be rewritten using multiplicative notation. The two theorems below are transparent and easy, but quite useful. For simplicity we first consider the product of two groups, although the case of infinite products is only slightly more difficult. For background, read first the two theorems on page 11.

Theorem Suppose G_{1} and G_{2} are additive groups. Define an addition on G_{1} × G_{2} by (a_{1}, a_{2}) + (b_{1}, b_{2}) = (a_{1} + b_{1}, a_{2} + b_{2}). This operation makes G_{1} × G_{2} into a group. Its “zero” is (¯0_{1}, ¯0_{2}) and −(a_{1}, a_{2}) = (−a_{1}, −a_{2}). The projections π_{1} : G_{1} × G_{2} → G_{1} and π_{2} : G_{1} × G_{2} → G_{2} are group homomorphisms. Suppose G is an additive group. We know there is a bijection from {functions f : G → G_{1} × G_{2}} to {ordered pairs of functions (f_{1}, f_{2}) where f_{1} : G → G_{1} and f_{2} : G → G_{2}}. Under this bijection, f is a group homomorphism iff each of f_{1} and f_{2} is a group homomorphism.

Proof It is transparent that the product of groups is a group, so let’s prove the last part. Suppose G, G_{1}, and G_{2} are groups and f = (f_{1}, f_{2}) is a function from G to G_{1} × G_{2}. Now f(a + b) = (f_{1}(a + b), f_{2}(a + b)) and f(a) + f(b) = (f_{1}(a), f_{2}(a)) + (f_{1}(b), f_{2}(b)) = (f_{1}(a) + f_{1}(b), f_{2}(a) + f_{2}(b)). An examination of these two equations shows that f is a group homomorphism iff each of f_{1} and f_{2} is a group homomorphism.

Exercise Suppose G_{1} and G_{2} are groups. Show that G_{1} × G_{2} and G_{2} × G_{1} are isomorphic.

Exercise If o(a_{1}) = m and o(a_{2}) = n, find the order of (a_{1}, a_{2}) in G_{1} × G_{2}.

Exercise Show that if G is any group of order 4, G is isomorphic to Z_{4} or Z_{2} ×Z_{2}. Show Z_{4} is not isomorphic to Z_{2} × Z_{2}. Show Z_{12} is isomorphic to Z_{4} × Z_{3}. Finally, show that Z_{mn} is isomorphic to Z_{m} × Z_{n} iff (m, n) = 1.

Exercise Suppose G_{1} and G_{2} are groups and i_{1} : G_{1} → G_{1} × G_{2} is defined by i_{1}(g_{1}) = (g_{1}, ¯0_{2}). Show i_{1} is an injective group homomorphism and its image is a normal subgroup of G_{1} × G_{2}. Usually G_{1} is identified with its image under i_{1}, so G_{1} may be considered to be a normal subgroup of G_{1} × G_{2}. Let π_{2} : G_{1} × G_{2} → G_{2} be the projection map defined in the Background chapter. Show π_{2} is a surjective homomorphism with kernel G_{1}. Therefore (G_{1} × G_{2})/G_{1} ≈ G_{2} as you would expect.

Exercise Let R be the reals under addition. Show that the addition in the product R × R is just the usual addition in analytic geometry.

Exercise Suppose n > 2. Is S_{n} isomorphic to A_{n} × G where G is a multiplicative group of order 2 ?

One nice thing about the product of groups is that it works fine for any finite number, or even any infinite number. The next theorem is stated in full generality.

Theorem Suppose T is an index set, and for any t ∈ T, G_{t} is an additive group. Define an addition on ∏_{t∈T}G_{t} = ∏ G_{t} by {a_{t}} + {b_{t}} = {a_{t} + b_{t}}. This op-

eration makes the product into a group. Its “zero” is {¯0_{t}} and −{a_{t}} = {−a_{t}}. Each projection π_{s} : ∏ G_{t} → G_{s} is a group homomorphism. Suppose G is an additive group. Under the natural bijection from {functions f : G → ∏ G_{t}} to {sequences of functions {f_{t}}_{t∈T} where f_{t} : G → G_{t}}, f is a group homomorphism iff each f_{t} is a group homomorphism. Finally, the scalar multiplication on ∏ G_{t} by integers is given coordinatewise, i.e., {a_{t}}n = {a_{t}n}.

Proof The addition on ∏ G_{t} is coordinatewise.

Exercise Suppose s is an element of T and π_{s} : ∏ G_{t} → G_{s} is the projection map defined in the Background chapter. Show π_{s} is a surjective homomorphism and find its kernel.

Exercise Suppose s is an element of T and i_{s} : G_{s} → ∏ G_{t} is defined by i_{s}(a) = {a_{t}} where a_{t} = ¯0 if t ≠ s and a_{s} = a. Show i_{s} is an injective homomorphism and its image is a normal subgroup of ∏ G_{t}. Thus each G_{s} may be considered to be a normal subgroup of ∏ G_{t}.

Exercise Let f : Z → Z_{30} × Z_{100} be the homomorphism defined by f(m) = ([4m], [3m]). Find the kernel of f. Find the order of ([4], [3]) in Z_{30} × Z_{100}.

Exercise Let f : Z → Z_{90} × Z_{70} × Z_{42} be the group homomorphism defined by f(m) = ([m], [m], [m]). Find the kernel of f and show that f is not surjective. Let g : Z → Z_{45} × Z_{35} × Z_{21} be defined by g(m) = ([m], [m], [m]). Find the kernel of g and determine if g is surjective. Note that the gcd of {45, 35, 21} is 1. Now let h : Z → Z_{8} × Z_{9} × Z_{35} be defined by h(m) = ([m], [m], [m]). Find the kernel of h and show that h is surjective. Finally suppose each of b, c, and d is greater than 1 and f : Z → Z_{b} × Z_{c} × Z_{d} is defined by f(m) = ([m], [m], [m]). Find necessary and sufficient conditions for f to be surjective (see the first exercise on page 18).

Exercise Suppose T is a non-void set, G is an additive group, and G^{T} is the collection of all functions f : T → G with addition defined by (f +g)(t) = f(t)+g(t). Show G^{T} is a group. For each t ∈ T, let G_{t} = G. Note that G^{T} is just another way of writing ∏_{t∈T} G_{t}. Also note that if T = [0, 1] and G = R, the addition defined on

G^{T} is just the usual addition of functions used in calculus. (For the ring and module versions, see exercises on pages 44 and 69.)