[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

A group is an algebra (see AlgebraicStructures) with an associative binary operation (usually written as either multiplication or addition), a constant identity element e such that ex = xe = x for all x, and an inverse operation x -> x-1 such that xx-1 = x-1x = e for all x. If it is also the case that xy=yx for all x and y, the group is abelian. Group theory is the study of the structure of groups.

More formally, a group is a set G together with an operation *:S×S→S that satisfies:

∀x,y ∈ G, x*y ∈ G. (This is implicit in the fact that *:S×S→S.)
∀x,y,z ∈ G, (x*y)*z = x*(y*z)
∃e∈G ∀x∈G e*x = x*e = x.

∀x∈G ∃x-1∈G x*x-1 = x-1*x = e.

An abelian group also satisfies:

∀x,y∈G xy=yx.

Abelian groups are often written using + for the group operation to emphasize their abelianness, with -x for the inverse of x. So in an abelian group we might write the inverses axiom as ∀x∈G ∃(-x)∈G x+(-x) = (-x)+x = e.

There are also words for algebras that satisfy only some of these axioms: if we take away inverses, we get a monoid; if we take away inverses and the identity, we get a semigroup, and if we take away associativity as well, we get a magma. These structures are discussed in more detail in AlgebraicStructures, but for now we will content ourselves with groups.

1. Some common groups

2. Arithmetic in groups

Here are some useful facts that apply in any group:

3. Subgroups

A subgroup is a subalgebra of a group. In English, H is a subgroup of G if H is a subset of G that is closed under G's group operation, i.e. such that for all x,y∈H, x*y ∈ H. For example, the even integers are a subgroup of the integers (with addition as the group operation). The statement that H is a subgroup of G is sometimes abbreviated as H < G.

The subgroup of G generated by an element x, written <x>, is the smallest subgroup of G that contains x, where subgroups are ordered by inclusion. The existence of <x> is immediate from the fact that (a) there is at least one subgroup of G that contains x---G itself, and (b) the intersection of any number of subgroups that contain x is itself a subgroup containing x. So we can take the intersection of all the subgroups that contain x and get <x>.

There is a simpler way to write <x>. If we define x0 = e, xn for n > 0 as xxn-1, and x-n for n > 0 as x-1x-(n-1), then <x> is precisely { xn | n ∈ ℤ }, the set of all powers of x. Note that it is possible that this set contains duplicates: for example, in ℤ6, 3+3 = 0 and so <3> consists only of the elements 0 and 3. The size of the subgroup generated by x is equal to the smallest n such that xn = e (if such an n exists); this quantity is called the order or index of x in G. A subgroup generated by a single element is called a cyclic subgroup; we'll talk more about these below.

4. Homomorphisms and isomorphisms

A homomorphism f:G→H is a function from the elements of G to the elements of H such that f(xy) = f(x)f(y) for all x,y in G. For example, the function n↦(n mod m) is a homomorphism from ℤ to ℤm, since taking remainders preserves addition. It is not hard to show that homomorphisms preserve the identity (if f(eG) ≠ eH, we are in trouble when we compute f(xeG) = f(x)f(eG) ≠ f(x)) and inverses (since f(x)f(x-1) = f(eG) = f(x-1)f(x) implies f(x-1) = f(x)-1). A homomorphism that is bijective is called an isomorphism.

5. Cartesian products

Given G and H, the product group G×H has elements of the form (x,y) where x∈G and y∈H and the product rule (x,y)(x',y') = (xx',yy').

Isomorphisms between various products of cyclic groups are discussed in BiggsBook §20.6.

6. How to understand a group

Groups in general can be very complex, and it may be difficult to wrap your mind around an arbitrary group unless you can find some way to break up its structure into brain-sized pieces. Here are four basic strategies that group theorists have come up with for doing this:

  1. By looking at it as a subgroup of Sn, i.e. as a collection of bijections (called actions) on some set. This works for any finite group: we can always take the group itself as the set, and for each group element a the function f:G->G defined by f(x) = xa is a bijection (the inverse is f-1(x) = xa-1). Other examples of groups constructed in this way are the symmetry groups of various figures described above, or the automorphism group of a graph (or any structure that has automorphisms).

  2. By giving a set of generators a, b, c, etc. and relations that describe when various products of the generators and their inverses are equal. An example of this was the description of the dihedral group Dn as being generated by elements a and b (generators) with an = e and ab = ba-1 (relations). Formally, this approach is equivalent to taking a quotient of the free group by a congruence generated by one of its subgroups, as we will describe in more detail below.

  3. By looking at what subgroups the group has. Even if the original group itself is hard to grasp, it may have simpler structures buried within it.
  4. By expressing the group as a product of simpler groups. This is particularly useful for abelian groups, as all abelian groups are isomorphic to a product of cyclic groups ℤm, where m is a power of a prime.

We will start by looking at how subgroups relate to a group, and in particular how subgroups can sometimes generate congruences that can be used to construct quotient groups.

7. Subgroups, cosets, and quotients

Let G be a group, and let H be a subgroup of G. For each element a of G, define Ha = { xa | x in H }. Such a set is called a right coset. We can similarly define aH = { ax | x in H }, a left coset; everything we say about right cosets will also be true of left cosets, after reversing the group operation throughout.

The right cosets of a subgroup have the same size (sometimes called order by group theorists) as the subgroup itself:

Lemma 1
|H| = |Ha| for all a.

Let f:H->Ha be the function f(x) = xa. Observe that f has an inverse f-1(y) = ya-1; it follows that f is a bijection.

It is also not hard to show that the cosets partition G:

Lemma 2
For any a, b, either Ha = Hb or Ha∩Hb = Ø.

Suppose y appears in both Ha and Hb; we will show that any z in Ha is also in Hb. We have y = xa = wb for some x, w in H. It follows that a = x-1wb. Let z = qa where q is in H. Then z = qx-1wb. But q, x, and w are all in H, so qx-1w is as well, and z is in Hb. A symmetric argument shows that any z'∈Hb is also in Ha, so Ha = Hb.

Combining the two lemmas gives:

Theorem 3
If H is a subgroup of G, then |H| divides |G|.

This is not true in general for e.g. monoids---the important difference is that the existence of a-1 means that multiplying by a is invertible and creates a bijection. Though one can define right cosets for any subalgebra and binary operation, both the equal-size lemma and the partition lemma depend on the existence of inverses.

An immediate consequence of the Theorem is that any group whose size is a prime (e.g. ℤp) has no nontrivial2 proper3 subgroups.

7.1. Normal subgroups

Partitioning all elements of G into right cosets of a subgroup H creates an equivalence relation: a is right congruent to b, written a ≡r b (mod H), if Ha = Hb, or equivalently if ab-1 is in H. For non-abelian groups, right congruence is not in general a congruence in the algebraic sense. We can see this by observing that if it were a congruence, then then we could construct a quotient group G/≡r in which H (as the equivalence class containing e) acted as the identity. But since the identity commutes, we would need aH = Ha for all a. Though this equation is true for many subgroups, it is not true for all.

A subgroup H of G for which aH = Ha for all a is called a normal subgroup. If H is a normal subgroup of, we write H ⊲ G. Any subgroup of an abelian group is normal. A group is called simple if it has no normal subgroups; an example is the dihedral group Dn. This group has a subgroup of order n (the rotations that don't flip) and many subgroups of order 2 (the flips around particular vertices), but none of them are normal.

Given a subset S of G, the intersection of all normal subgroups of G that are supersets of S is a also normal subgroup, called the normal subgroup generated by S. In general the normal subgroup generated by S will be larger than the subgroup generated by S.

If N is a normal subgroup of G, then ≡r (mod N) is a congruence: (Ha)(Hb) = HaHb = HHab = Hab. We write G/H for the quotient group obtained from G and this congruence. Group theorists have historically approached the understanding of groups by trying to dividing them into quotients over subgroups, ultimately leading to towers of simple groups that cannot be divided further. This doesn't entirely identify the group: for example, the distinct groups ℤ4 and ℤ2×ℤ2 both have ℤ2 as a normal subgroup and in both cases ℤ4/ℤ2 = ℤ2×ℤ2/ℤ2 = ℤ2, but it gives some information.

The problem of identifying the simple groups, at which this process stops, is known as the problem of classification of finite simple groups and was a major outstanding problem in group theory from the mid-19th century until its final completion in 1985.

7.2. Cyclic subgroups

Let G be a group and let a be an element of G. Then the set <a> = { ak | k in ℤ } is a subgroup of G, called the cyclic subgroup generated by a. (Proof that it's a subgroup: <a> contains the identity e = a0, and for any ai and aj in <a>, aiaj = ai+j is in <a>.) This is an easy way to generate subgroups of a group; for example, the non-normal subgroups of the dihedral group consisting of all non-flipping rotations or particular non-rotating flips are just the cyclic groups generated by particular operations.

Some other examples of cyclic subgroups of a group:

The index of an element a is the least positive integer k for which ak = e, or 0 if there is no such integer (this only happens in infinite groups: the proof is that in a finite group, as we generate the sequence a0, a1, a2, ... we must eventually get ai = aj for some i, j; but then a|i-j| = e). When the index is nonzero, it is also the size of <a>, as any element am where m is less than 0 or greater than or equal to k will be equal to some element in the set { a0, a1, ..., ak-1 }. It follows from the theorem in the previous section that the index of any element of a finite group (if nonzero) divides the order of the group that contains it.

For permutations, the index can be calculated directly from the cyclic decomposition; it's the least common multiple of the cycle lengths. A well-known application of this is the answer to the problem "how many perfect shuffles does it take to restore a 52-card deck of playing cards to its original state?" Here we define a "perfect shuffle" as a permutation that interleaves the top and bottom halves of the deck, which (if we number the cards from 0 to 51) sends card 0 to position 0, 26 to position 1, 1 to position 2, 27 to position 3, and so on, ultimately leaving card 51 in place. Formally, we can think of this as the function f(x) = 2x mod 51 for x < 51, and we want to know how many iterations of f are needed to get the identity.

If we try writing down the cyclic decomposition of f, we get (0)(1 2 4 8 16 32 13 26)(3 6 12 24 48 45 39 27)(5 10 20 40 29 7 14 28)(9 18 36 21 42 33 15 30)(11 22 44 37 23 46 41 31)(17 34)(19 38 25 50 49 47 43 35)(51). This is the product of many 8-element cycles, one 2-element cycle, and two 1-element cycles; so the LCM is 8 and 8 perfect shuffles equals the identity. (A quicker way to see this is to observe that f(k)(x) = 2k x mod 51 when x < 51, and 28 mod 51 = 256 mod 51 = 1.)

7.3. Finding the subgroups of a group

Given a group, how do we find subgroups? For finite groups, it's often enough to pick a few elements and ask "what subgroup is generated by these elements?" The more difficult problem is knowing when you've gotten all the subgroups. Here facts like Theorem 3 (|H| divides |G| when H is a subgroup of G) can be handy for excluding possibilities we might have missed.

For example, let's find all the subgroups of Dp where p is a prime. The order of Dp is 2p, and the only subgroup orders we are interested in that divide 2p are 2 and p, so any nontrivial proper subgroup either has size 2 (i.e., it consists of the identity and one other element that is its own inverse) or p. It's not hard to see where we can get size 2 subgroups (any flip generates one) and a size p subgroup (all the rotations). But are these all the subgroups?

First observe that the subgroup of non-flipping rotations is generated by any nontrivial rotation. The proof is that any such rotation is of the form x=ak for some k (where a is our rotate-one-position-to-the-right generator), and if the index of x is some m < p we have akm = e which implies km is a multiple of p. But then km contains a factor of p and p is not prime.

It follows that as soon as we have a single rotation, we have all the rotations. So we can't get any more subgroups using just rotations.

Can we get another subgroup using, say, two flips? Suppose we flip around 1 and then around some other position c. Then after both flips 1 is moved to position 2c-1 and the polygon is not flipped---in other words, the product of these two flips is a nontrivial rotation. So we have a subgroup that contains a nontrivial rotation, which means that it contains all p rotations, and it also contains at least two flips. This means the subgroup has at least p+2 elements; but the only number greater than or equal to p+2 that divides 2p is 2p itself. So as soon as we have two flips (or a rotation and a flip), we have the entire group.

We have just shown that the nontrivial proper subgroups of Dp consist precisely of (a) p 2-element subgroups generated by flips around particular vertices of the polygon, and (b) one p-element subgroup containing all rotations. Note that we used the fact that p was prime; for general Dn we might get more subgroups.

8. Homomorphisms, kernels, and the First Isomorphism Theorem

Let f:G→H be a homomorphism. Define the kernel of f as the set Ker(f) = f-1(eH) = { x∈G | f(x) = eH }.

It is easy to show that the kernel is always a normal subgroup of G. To show that it is a subgroup, first observe that if x, y are in Ker(f), then f(xy) = f(x)f(y) = eHeH = eH implies xy is also in Ker(f). Similarly if f(x) = eH then f(x-1) = eH-1 = eH and thus Ker(f) is closed under inverses. To show that Ker(f) is normal, we need to show that for any a, the coset a Ker(f) = Ker(f) a. We can do so by observing that for any b in Ker(f), f(ab) = f(a)f(b) = f(a), and similarly f(ba) = f(b)f(a) = f(a). So a Ker(f) = Ker(f) a = f-1(f(a)), or equivalently a' is in a Ker(f) = Ker(f) a precisely when f(a') = f(a). This latter equation defines the kernel relation of f, which does not depend on G being a group and has useful properties for more general algebraic structures; but for groups it is enough to track the kernel as a subgroup.

It is also the case that the image of f, defined as Im(f) = { y∈H | y = f(x) for some x∈G } is a subgroup of H. The proof is that if y and y' are both in Im(f), then y=f(x) and y'=f(y') for some x, x' in G, and so yy' = f(x)f(x') = f(xx') ∈ Im(f). (For a surjective homomorphism, Im(f) = H, but not all homomorphisms are surjective.) The image of f is not necessarily normal; for example, the image of f:ℤ2→S3 given by f(0) = () and f(1) = (1 2) is a subgroup { (), (1 2) } of S3, but this subgroup is not normal.

We can use the fact that the image of a homomorphism is a subgroup to rule out certain homomorphisms between groups. For example, if there is an injective homomorphism f from ℤm to ℤn, then Im(f) is a subgroup of ℤn of size m, and we must have m|n.

Because the kernel is normal, we can take a quotient G/Ker(f). The First Isomorphism Theorem says that G/Ker(f) is always isomorphic to Im(f). This is a special case of an even more general theorem for arbitrary algebras, but for groups we can prove it quickly. Observe first that the elements of G/Ker(f) are precisely the inverse images of elements of Im(f), i.e. the sets f-1(y) = { x∈G | f(x) = y } for each y in Im(f). We will show that this map f-1 from elements if Im(f) to elements of G/Ker(f) is the desired isomorphism. Given two elements f-1(y) and f-1(y') of G/Ker(f), their product is obtained by taking representatives x and x', multiplying them, and taking the equivalence class that contains them. But then we have f(xx') = f(x)f(x') = yy' and so f-1(y)f-1(y') = f-1(yy'). By a similar argument, we have (f-1(y))-1 = f-1(y-1), and so f-1 is a homomorphism. But it is also an isomorphism: it's surjective (easy) and injective (since f is a function) and thus a bijection.

For example, the homomorphism f from Sn to ℤ2 based on whether a permutation is the product of an even or odd number of transpositions (see SymmetricGroup) has as its kernel the alternating group An of even permutations, and the quotient group Sn/An consists of the set of even permutations and the set of odd permutations and is isomorphic to ℤ2.

On the other hand, we can use the First Isomorphism Theorem to rule out the existence of certain homomorphisms. For example, there is no nontrivial homomorphism4 from Sn to ℤp when p > n, since ℤp has no nontrivial proper subgroups, and if f were a surjective homomorphism from Sn to ℤp, we'd have a subgroup Ker(f) of Sn such that |Sn| = n! would be a multiple of |Sn/Ker(f)| = p, but n isn't big enough for this to happen. Or for a homomorphism f from ℤm to ℤn, we can show that |Im(f)| divides both n (because Im(f) is a subgroup of ℤn) and m (because Im(f) ≈ ℤm/Ker(f) implies that |Im(f)| = |ℤm|/|Ker(f)| divides m); it follows that any such homomorphism has |Im(f)| ≤ gcd(m, n).

9. Generators and relations

One way to define a group is to specific a set of generators, and to give relations between them. Such groups are written as (S|R) where S is the set of generators and R is the set of relations. In principle any group can be defined in this way: we let the set of generators be all the elements of the group, and let the relations be all equations of the form xy=z that are true in the group. In practice this approach is only useful when a group is generated by a small number of generators and relations, as with ℤ = (a|), ℤm = (1|m1 = 0), Dn = (a,b|an=e,b=b-1,ab=ba-1), or ℤ2×ℤ2 = (a,b|a2=e,b2=e,ab=ba). The notation can be further simplified by converting each relation to the form w=e where w is some word and dropping the "=e" part; this gives ℤ = (a|), ℤm = (1|m1), Dn = (a,b|an,b2,abab), and ℤ2×ℤ2 = (a,b|a2,b2,aba-1b-1) for the examples. A definition of a group in this form is called a presentation of the group.

The intuition behind a presentation is that the resulting group is just big enough to contain all the generators and everything that can be generated from them, but not so big that the relations stop being true. This intuition should remind you of free algebras, and in fact the formal definition of (S|R) takes a quotient of the free group F(S) on S:

Let S be a set of elements and R a set of words (i.e., elements of F(S)) over S. Then (S|R) = F(S)/N, where N is the normal subgroup of F(S) generated by the elements of R.

As before, the normal subgroup generated by R is just the intersection of all normal subgroups of F(S) that contains R. This will consist in particular of all words of the form r0s1r1s2r2...skrk where each ri is the product of elements of R and their inverses and s1...sk = e in F(S).

Note that the same group may have multiple presentations; the S part will be the same, but different sets of relations might generate the same subgroup of F(S).

One consequence of the definition of (S|R) is that (S|R) inherits some of the properties of the free group. In particular, any homomorphism from G=(S|R) to some group H is completely determined by where it sends the generators:

Theorem 4

Let G=(S|R) and let f:G->H and g:G->H be homomorphisms. Then if f(x)=g(x) for all x in S, f(x)=g(x) for all x in G.


Because G is a quotient group of F(S), there exists a homomorphism h:F(S)->G with h(x) = x for all x in S. Now consider the homomorphisms (f∘h) and (g∘h) from F(S) to H. If x is in S, we have (f∘h)(x) = f(x) = g(x) = (g∘h)(x). Using the definition of a free algebra, there is a unique homomorphism that maps each x in S to f(x) = g(x), so we have (f∘h) = (g∘h). Now take some y in G, and let z be such that h(z) = y. Then f(y) = f(h(z)) = g(h(z)) = g(y).

10. Decomposition of abelian groups

Finite abelian groups have a particularly simple structure:

Theorem (Kronecker Decomposition Theorem)

Let G be a finitely abelian group of size n > 1. Then G is isomorphic to a product of cyclic groups of prime power order, i.e. there are prime numbers p1, p2, ... pm and positive integers k1, k2, ... km such that

\[G \approx \prod_{i=1}^{m} {\mathbf Z}_{p_i^{k_i}}.\]

Note that the product of the sizes of the groups in the product must equal the size of the product group. This allows us to quickly identify all the isomorphism classes of abelian groups of a given size. For example, there is one (up to isomorphism) 6-element group, isomorphic to ℤ2×ℤ3, because 2×3 is the only way to factor 6 into prime powers. In contrast, there are two 4-element groups: ℤ2×ℤ2 and ℤ4; and five 16-element groups: ℤ2×ℤ2×ℤ2×ℤ2, ℤ2×ℤ2×ℤ4, ℤ2×ℤ8, ℤ4×ℤ4, and ℤ16.

The proof of the Theorem was hard enough to get Kronecker's name attached to it, so we will not attempt it here.


  1. Sometimes reversed composition, so that πρ means do π then ρ rather than the usual do ρ then π; watch out for different authors handling this in different ways. (1)

  2. Containing more than just the identity element. (2)

  3. Not equal to the entire group. (3)

  4. In this case, nontrivial means that the homomorphism doesn't send everything to e. (4)

2014-06-17 11:58