Abstract Algebra and Discrete Mathematics

By Karl Dahlke and Kermit Rose, Copyright © 2014

Chapter 10, Groups

Groups Table of Contents Start of chapter

A group is a set of elements S and an operator * possessing the following properties:

  1. The binary operator * is a well defined function mapping S cross S into S.

  2. The operator * is associative.

  3. There is a unique identity element 1, such that x*1 = 1*x = x for every x in S.  This identity element is sometimes denoted e.  When the group operator is commutative the identity element is often denoted 0, and * is replaced with +.

  4. every x has a unique inverse y such that x*y = y*x = 1.

The group is abelian if * is commutative.  Why don't they just call it a commutative group?  It is called abelian in honor of Niels Abel, who used group theory to solve some longstanding problems in mathematics.

As with regular multiplication, the star is often omitted.  Thus x*y is simply written xy, and x*x*x*x is written x4.  Realize that x4yx is not x5y, since x and y may not commute.

If the group is abelian, we often use + instead of * and 0 instead of 1.  This reminds us that the elements can be rearranged as we wish.  For instance, x+x+y+x+y = 3x+2y.

The integers form an abelian group under addition, with 0 as the identity element.  The positive rationals form an abelian group under multiplication, with 1 as the identity element.

The integers mod m, Z/m, form a group under addition, and the units mod m, denoted (Z/m)*, form a group under multiplication.

Use the clock to illustrate addition mod 12, written Z/12, which is an abelian group.  Add 4 hours + 3 hours + 7 hours, in any order, and wind up at 2:00.  The opposite of 4 is 8, since 4+8 = 0.

If p is prime, Z/p is a field; addition is a group, with 0 as the identity, and multiplication of the nonzero elements is a group, with 1 as the identity.  Thus a field has two groups running in parallel, corresponding to addition and multiplication.

modular math starts with 0

The set of 3 by 3 real orthonormal matrices is a nonabelian group under matrix multiplication.  Thinking geometrically, this is the rigid rotations and reflections about the origin in 3 space.  A rotation about the x axis and a rotation about the y axis do not commute, but a sequence of 3 rotations is always associative, and every rotation has an inverse.  You can always spin the object back to start.  Try it with a standard die.  Spin it around x, then around y, and compare that with the rotation about y, then about x.  The operations do not commute.

A semigroup has no identity or inverses, such as the positive reals under addition.

A monoid is a semigroup with an identity, such as the non-negative reals under addition.  Here 0 is the identity, but without negative numbers there are no inverses.  The simplest monoid that is not a group consists of 0 and x, where x+x = x.

rotations about the x and y axes do not commute

I'm not going to give a formal definition of a ring at this time, but as an overview, a ring is a group and a monoid.  This is less restrictive than a field, which is a group and a group.  If R is a ring, addition in R is an abelian group; that is, addition commutes, and everything has an opposite.  Multiplication in R is a monoid, with 1 as the identity.  Since x might not be invertible, e.g. the integers, multiplication does not form a group.  In the ring of 2 by 2 matrices, multiplication does not commute, and the multiplicative monoid is nonabelian.

It doesn't come up very often, but there are rings without 1, e.g. the even integers.  This is a group (addition) and a semigroup (multiplication), wherein multiplication has no identity and no inverses.

Cancellation and Order Table of Contents Start of chapter

In a group, you can always cancel x from either side.  If xy = xz then y = z; simply multiply by x inverse on the left.  But don't assume the same for xy = zx.  In the quaternions, ij = (-j)i, but j does not equal -j.

The order of x is n if n is the smallest positive integer satisfying xn = e.  If the powers of x go on forever, x has zero order.  We sometimes use the notation |x| for the order of x.  The order of e is 1.

An involution is an element with order two (its own inverse).

The order of the group G, written |G|, is the size of G, i.e. the cardinality of its underlying set.  A finite group has finite order.  If x generates the entire group, then |x| = |G|.  The group is cyclic, with generator x.

Subgroups and Cosets Table of Contents Start of chapter

If G is a group, H is a subgroup of G if H is a subset of G, and H is a group, using the same * operator.

H contains 1, and if H contains x H contains 1/x, and if H contains x and y H contains xy.

For any positive n, the multiples of n form a subgroup of the integers under addition.  If n > 1, the subgroup is a proper subgroup.

If H is a nonempty subset of the group G, H is a subgroup iff every a and b in H implies a/b in H.  The forward direction is obvious, so assume the latter.  Since H contains a/a, H includes the identity.  Since H includes 1/a, inverses are present.  Finally H contains ab, via a/(1/b), hence * does not map H to anything outside of H.

If you haven't seen cosets before, group theory can be a difficult place to start.  Here is the idea of a coset in more general terms.

Let H be a substructure inside G.  Shifted copies of H are called cosets of H, and they cover all of G without overlap.  For example, let G be the xy plane and let H be the x axis.  For every real number c, the line running parallel to the x axis, through y = c, is a coset of the x axis.  These cosets cover the entire plane without overlap.  Each coset is a shifted version of H.

The quotient G/H is the collection of cosets.  In this example, the quotient is the y axis.

The index of H is the number of cosets of H in G.  How many cosets are required to cover G?  If the quotient makes sense, the index is the size of the quotient set.

Given a subgroup H, the left coset of an element x is the set of elements H*x.  Right cosets are defined similarly, i.e. x*H.  Note - almost every textbook will define the coset in the other direction, e.g. left coset is x*H, however, my convention is consistent with left ideals and left modules, so for consistency I very much prefer it.  My apologies to the standard literature, and to you if you are reading any other book on groups.

If a and b are in H, and ax = bx, then cancel x, and a = b.  All the elements in a coset are distinct.  In fact they all map back to H; simply multiply by 1/x.  Thus each coset is the same size as H.

Thanks to the identity in H, x is always in the coset of x (reflexivity).  Since you can always multiply by the inverse of an element in H, x is in the coset of y iff y is in the coset of x (symmetry).  If z is in the coset of y is in the coset of x, z is in the coset of x (transitivity).  In other words, y = ax and z = by, hence z = bax.  This is an equivalence relation, and G can be partitioned into well defined cosets.  All these cosets have the same size, namely |H|.

G partitioned into cosets of H

Sometimes we use designated elements from these cosets to represent them, i.e. coset representatives, somewhat like sending a representative from your district to congress.  For brevity, such a representative is called a cosrep.  As the name suggests, cosreps are usually taken directly from G, a true representative of the coset, but sometimes we rename the cosets, and assign them different symbols.  The group may have no numbers in it at all, but if the cosets behave like integers, we might rename them 1 2 3 … n.

Lagrange's theorem is an immediate consequence of the partitioning of G into cosets of H: |H| divides |G| whenever |G| is finite.  If |G| = 24, you don't have to look for a subgroup of size 7.  There isn't one.

The index of H also divides |G|.  In fact the index is |G|/|H|.  But what if G is infinite?  Is index still well defined?  Could there be more right cosets than left cosets?

Invert all the elements of G.  This maps H onto H, and builds a bijection between left and right cosets.  If x is one of our cosreps, the right coset of x corresponds to the left coset of 1/x.  The inverse of everything in x*H is H times 1/x.  Hence the inverse of a right coset is a left coset, and this process can be reversed.  Index is well defined, i.e. the cardinality of the set of cosets from either side.

If J is a subgroup of H, is a subgroup of G, then everything in G is something in H times a cosrep of H in G, and that something in H is something in J times a cosrep of J in H.  Each cosrep of J in G is a cosrep of J in H times a cosrep of H in G.  The index of J in G is the index of J in H times the index of H in G.

Let H be a subgroup of G.  If x*H = H*x for every x in G, then H is a normal subgroup.  In other words, the left and right cosets coincide.  This does not mean x commutes with the elements of H, it only means x*H and H*x produce the same set.  Of course, if H does commute with every x in G, then H has to be normal.  Every subgroup of an abelian group is normal.

An equivalent definition says H is normal iff x*y/x is in H for every x in G and every y in H.  If left and right cosets are the same, then xy = zx for some z in H, hence xy/x = z, a member of H.  Conversely, if xy/x is always some z in H, then xy (in the right coset) is the same as zx (in the left coset).  With (1/x)yx in H, yx (in the left coset) is the same as xz (in the right coset).  The left and right cosets contain each other, and H is normal.

If H has index 2 in G it is normal.  Choose any x not in H and observe that x*H = H*x.  After all, there is only one coset outside of H.

A simple group has no normal subgroups other than 1 and itself.  This may remind you of the definition of a prime number.  If G has no proper subgroups at all, it has no normal subgroups, and is simple.  Z/p, for p prime, is an example, having no subgroups by Lagrange's theorem.  It is a simple group.

An abelian group must be free of subgroups to be simple.

left and right cosets are the same for a normal subgroup

Let G be cyclic, generated by x.  The elements of G correspond to the integers, i.e. the powers of x.  Multiplication in G simply adds the exponents, so let's use additive notation instead.  This makes sense, since G is abelian.

Let H be a subgroup of G, and let H contain k and l.  By closure, H contains all the linear combinations of k and l, such as 3k+5l, 7k-11l, etc.  Let d be the gcd of k and l, and write d as a linear combination of k and l.  Thus H contains d.  Therefore H is determined by its least integer, i.e. the least multiple of x contained in H, and H consists of the multiples of d for some d.

If G is infinite, so that it looks like the integers, there is a subgroup H for each positive integer d.

Assume G is finite, and isomorphic to the integers mod m.  If H contains d then H contains the multiples of d mod m, which is all linear combinations of d and m.  Thus H contains the gcd of d and m.  Ratchet d down to gcd(d,m).  Only the divisors of m are valid seeds for H.  This reaffirms lagrange's theorem.  There is a subgroup H for each divisor d in m.

Whether G is finite or infinite, all subgroups of a cyclic group are cyclic.

Kernel and Quotient Table of Contents Start of chapter

When the subgroup H is normal, the cosets form their own group.  The product of two cosets is found by multiplying any two cosreps together, and taking that coset.  We need to prove this is well defined, i.e. you always get the same coset no matter which cosreps you select.  If, instead of xy, we had selected xuyv, where u and v come from H, replace uy with yw, since the left and right cosets of y are the same.  Now wv lives in H, so this is another member in the same coset, the coset of xy.  H has to be normal for this to work.

The identity represents the identity coset, and a coset's inverse is found by inverting one of its cosreps.  The resulting group of cosets is called the quotient group, or the factor group, and H is called the kernel.  In fact, I will now switch notation, whence K is the kernel and H is the quotient group.  After all, kernel starts with K.  Hope this isn't too confusing.

You'll notice that the quotient retains the coarse structure of the group, without all the fine detail; like looking at an object through the wrong end of a telescope.  Z/15 has a normal subgroup of 0,5,10, and a quotient group with cosreps 0,1,2,3,4, i.e. Z/5.  The quotient tells us that the original group has some similarity to the integers mod 5; the kernel tells us the group has something to do with Z/3.  Of course we could have used 0,3,6,9,12 as kernel, making Z/3 the quotient.  We don't always have the option to switch kernel and quotient, but in this case we do. the quotient of Z mod 15 by Z mod 3 is Z mod 5

I've used the word "kernel" before, as the preimage of 0 (or 1) under a homomorphism.  In fact the map from G onto H, where x becomes the coset Kx, is a homomorphism, with K as kernel.  We already showed this map respects multiplication in G and in H.  That is, K*(xy) = Kx * Ky.  Everything in K maps to the trivial coset of K, K*1, and things outside of K produce some other coset, thus K is the kernel.

Conversely, let f be a homomorphism from the group G onto the set H, which possesses a preexisting operator *.  Since f is a homomorphism, f(x)f(y) = f(xy).  In other words, f commutes with *.  It is not hard to show that H is a group, inheriting all the group properties (e.g. associativity and inverses) through f. 

homomorphism from G to the quotient of G by K

Let 1 (the identity) in G map to an element called 1 in H, and verify that 1 acts as an identity element in H.  That is, f(1)f(x) = f(1x) = f(x), hence 1 leaves H where it is.

Let K be the set of elements in G that map to 1 in H.  For any x and y in K, f(x) = f(y) = 1 in H.  Their product is 1 in H, hence f(xy) = 1, hence xy is still in K.  Inverses must also map to 1 in H, and are present in K, hence K is a subgroup of G.

It is easy to show that xK/x remains in K, as f(xK/x) = 1, hence K is a normal subgroup of G.

Finally, the elements of H correspond to the cosets of K, and are multiplied accordingly.  The image group H is indistinguishable from the quotient group G/K.  A group homomorphism defines, and is defined by, its normal subgroup K.

The Group of Automorphisms of G Table of Contents Start of chapter

Review the various morphisms; they all apply to groups.

Multiply the integers by 29, and find an endomorphism from Z into itself.  It also happens to be a monomorphism, a perfect copy of Z living inside itself.

A finite group also supports a proper endomorphism, with a nontrivial kernel; though the image cannot be a perfect copy of G any more.  Map Z/4 into itself by mapping 0 and 2 to 0, and 1 and 3 to 2.

An automorphism amps G onto itself, and is basically a relabeling of G.  Multiply the integers by -1 for an automorphism on Z.

automorphism of Z sending 1 to -1

The set of automorphisms of G forms a group.  Two functions are "multiplied" by applying the first, then the second.  These functions are really permutations on the underlying set, that happen to commute with *.  Applying permutations is associative, and the identity permutation is the identity automorphism, so we only need to prove that inverse automorphisms exist.

An automorphism f has an inverse permutation j; just move the elements back into position.  Apply j first, and let z = j(x)*j(y).  Now f(z) = f(j(x)*j(y)) = f(j(x))*f(j(y)) = x*y.  If f(z) = xy, then j(xy) = j(f(z)) = z = j(x)j(y), and j is a homomorphism.  The automorphisms form a group under function composition.

Consider the automorphisms of Z/m, as an additive group.  This is a cyclic group, generated by 1, so once f(1) is defined, the entire group is mapped.  The resulting map is an automorphism iff f(1) is coprime to m.  There are φ(m) such automorphisms, including the trivial automorphism that maps 1 to 1.

If the first function maps 1 to u, and the second maps 1 to v, their composition maps 1 to uv.  The group of automorphisms is modular multiplication mod m, which is described here.

Inner Automorphisms Table of Contents Start of chapter

The conjugate of an element w with respect to x is xw/x.  If w and x commute then the conjugate of w is w.

This has nothing to do with the roots of an irreducible polynomial, wherein the conjugate of one root is another.  It's the same word, but the concepts are unrelated.

Given a group G and an element x, replace every element w in G with its conjugate.  In other words, f(w) = xw/x.  This map commutes with *, and is an automorphism.  By definition, it is an inner automorphism.  An automorphism that is not an inner automorphism is an outer automorphism.

If G is abelian, xw/x = w, and every inner automorphism is trivial.

The composition of two inner automorphisms, derived from x and y, is the inner automorphism derived from yx.  One can use x inverse to produce the inverse of the inner automorphism based on x.  Thus the inner automorphisms form a subgroup of all the automorphisms of G.

If x produces an inner automorphism, and f is any other automorphism, having inverse j, apply f, then the x automorphism, then j.  If w is a group element, we have j(x*f(w)/x).  Since j commutes with *, this is j(x)*j(f(w))/j(x), or j(x)*w/j(x).  The composition gives another inner automorphism, hence the subgroup of inner automorphisms is normal inside the (possibly larger) group of automorphisms of G.  This implies a quotient group, the automorphisms mod the inner automorphisms.

Conjugation by x permutes the elements of G

The center of G, i.e. those elements that commute with all of G, produce trivial inner automorphisms.  If x commutes with everything then xG/x leaves G fixed.  Conversely, if x is not in the center of G then xy/x is different from y for some y, and the resulting inner automorphism is nontrivial.

Map G onto the inner automorphisms of G by carrying x to the function xG/x.  Show that this is a homomorphism.  Compose xG/x with yG/y and get yxG/x/y, the inner automorphism associated with yx.  Technically, we were hoping for the inner automorphism associated with xy.  This is not a show stopper though.  Change the convention so that the composition of two automorphisms is the second followed by the first, rather than the first followed by the second.  The automorphisms of G still form a group.  Now the composition of xG/x and yG/y is xyG/y/x, as it should be, and the map from G onto its inner automorphisms is indeed a group homomorphism.

The kernel of this map is precisely the center of G.  Thus the inner automorphisms of G, with function composition defined as above, form a group that is isomorphic to G mod its center.

Direct Product, Direct Sum Table of Contents Start of chapter

Let G and H be arbitrary groups, and let J be a larger group whose elements, as a set, are defined by the cross product of G and H.  Let g1 and g2 be members of G, while h1 and h2 are members of H.  The product of g1,h1 * g2,h2 is g1g2,h1h2.  In other words, the groups G and H run in parallel.

We've already seen examples of this.  The group Z/7 * Z/7 contains 49 elements, two parallel copies of the integers mod 7.  Thus 2,5 + 3,3 = 5,1.

Project J onto G or H by throwing away the "other" component.  This is a group homomorphism, hence either G or H can act as the kernel of J, with H or G playing the role of factor group.

direct product of two copies of Z mod 7

Apply the above several times to take the direct product of a finite number of groups.

The direct product of an infinite set of groups is also well defined.  We don't have to worry about the axiom of choice, because every set has a special element, the group identity.  The direct product includes the element 1,1,1,1,1,1…, which acts as the identity element for the composite group.  Group operations are performed per component.

The direct sum is essentially defined in the same way as the direct product, group operations are still performed per component, but almost all components are set to the identity element.  See more on the direct sum here.

As an example, consider the direct product or sum of Z/p for all primes p.  The prime cycles run in parallel, and independent of each other.  The element 0,0,0,0… is the group identity.  In the direct product, the element 1,2,3,4,5,6,7,8,9… is well defined.  In the direct sum, almost all components must be 0, as in 1,2,3,0,5,0,0,0,0… zeros thereafter.

direct product of Z mod p for p prime

Semidirect Product Table of Contents Start of chapter

Let G and H be arbitrary groups, and let a group homomorphism map H into the automorphisms of G.  In other words, every element x in H is associated with an automorphism on G.  Call this automorphism fx.

Use the reverse convention described earlier, wherein the automorphism defined by xy is the automorphism of y followed by the automorphism of x.  This seems backwards, but it's what we need.  Naturally, f1 = 1, the trivial automorphism, and the automorphism f1/x is the inverse automorphism of fx.

If automorphisms have been assigned to the generators of H, then the entire map from H into the automorphisms of G is defined.  If H is cyclic, for instance, generated by x, we only need know fx.  Then fx*x is fx applied twice, and so on.

Now let's define the semidirect product.  The product of two elements g1,h1 * g2,h2 has the following formula.

g1*fh1(g2), h1h2

Is J a group?  Well 1,1 is certainly the two-sided identity.  Let's bring in g3,h3 and verify associativity.  The second component, from the group H, is clearly associative; we only need look at the first component.

First component of (J1 * J2) * J3 =

g1 fh1(g2) fh1h2(g3) =

g1 fh1(g2) fh1(fh2(g3)) =

g1 fh1( g2fh2(g3) ) =

First component of J1 * (J2 * J3)

Does g1,h1 have an inverse?  Let f be the automorphism associated with h1.  Apply f inverse to the inverse of g1 and call this g2.  Sure enough, g1f(g2) produces the identity in G, g2,h2 is the inverse of g1,h1, from either side, and J is a group.

A simple homomorphism maps J onto H, with G as kernel.  Thus J is the "semidirect product of G by H".  Notice that J contains a copy of H inside it, and the homomorphism carries H perfectly onto the factor group H.  Seen another way, you can select a cosrep for every coset of G in J, and these cosreps form a closed subgroup inside J.  This subgroup is a mirror of H inside J.

A copy of the quotient group H lives in the larger group J. This copy of H maps forward onto H via the group homomorphism.

Now let's run things in the other direction.  Let J be a group with kernel G and factor group H.  Thus J is an "extension of G by H".  Let H be a set of cosreps of G in J, such that H is a closed subgroup inside J.  Now H represents and defines the factor group.

Let x be any element of H.  Since G is the kernel, xG/x equals G, as a set.  That is, conjugation by x permutes the elements of G.  Apply this to g1g2, and the result is the same as xg1/x * xg2/x.  Therefore conjugation by x implements a group automorphism on G.  (This automorphism is trivial if J is abelian.)  Call this automorphism fx.  This holds for every x in J, so it certainly holds for every x in H.

Since left and right cosets are the same, let the members of H represent left cosets of G.  The elements of J can now be labeled unambiguously.  Each element is gi,hi for some gi in G and some hi in H.

Now consider the product g1,h1 * g2,h2.  Realize that x,y is the same as x*y, and you're almost there.

g1,h1 * g2,h2 =

g1 * h1 * g2 * h2 =

g1 * h1 * g2 / h1 * h1 * h2 =

g1 * fh1(g2) * h1 * h2 =

g1 fh1(g2), h1h2

The group J, with kernel G and factor group H, is a semidirect product iff a copy of H exists inside J, and maps onto the factor group H.  Such a group is called "split exact".

Here is a group with a copy of H inside J, yet it is not split exact.  Consider the cyclic group of order p2 for some prime p.  The multiples of p form the kernel, and the integers mod p form the factor group.  We have G and H in hand, but is J a semidirect product?  Suppose x is an integer that is nonzero mod p, such that x generates a copy of H inside J.  The elements x, 2x, 3x all map to 1 2 3 etc in the factor group, but px is not 0.  The subgroup is not closed.  J is a group that has a kernel and quotient, but is not a semidirect product.

Things are different when |G| and |H| are relatively prime.  Let G be the kernel and let H be the quotient, with a copy of H in J.  Let c and d be elements of H that happen to lie in the same coset of G.  Thus c/d also lies in G.  This means the order of c/d divides into |G| and |H|, which are relatively prime.  Thus c/d is the group identity, and c = d.  The members of H represent distinct cosets of G in J.  In other words, the members of H faithfully represent the factor group J/G.  Multiplication in H corresponds to multiplication in J/G, and H is in fact a copy of the factor group living in J.  The group is split exact - a semidirect product.

Next suppose G is normal in J, and |G| and |J/G| are relatively prime, and J/G is known to be cyclic.  Let c be an element of J that generates J/G.  If |J/G| = u, cu is back in G, and has some order v in G.  Replace c with cv.  Since v and u are coprime, we are merely selecting a new generator for J/G.  Now, cu is the identity element in G, and in J.  Thus c generates a copy of the factor group inside J, and J is split exact - a semidirect product.

Intersection and Join Table of Contents Start of chapter

The intersection of arbitrarily many subgroups is a subgroup.  Furthermore, the arbitrary intersection of normal subgroups is normal.  If w is in each of the normal subgroups, then xw/x is in each of these subgroups.  We don't have to worry about an empty intersection; every subgroup contains the identity element.

The union of two normal subgroups may not even be a subgroup.  When multiples of 3 and 5 are combined, they don't contain the number 8, and are not a subgroup of Z.  However, any set of elements, including the union of preexisting subgroups, can be used to generate a new subgroup.

If Q is a collection of group elements, let R contain Q, the inverses of Q, and all finite products taken from Q and its inverses.  If a and b are in R, then a/b is in R, hence R is a subgroup; in fact it is the smallest subgroup that contains Q.

What about a normal subgroup generated by Q?  Here's what we're not going to do: expand Q into R as above, then set S to all the conjugates of R, i.e. xw/x for every w in R and every x in G.  Illustrate by setting Q to the transposition 213.  Bring in the identity permutation 123 and you have the subgroup R.  Conjugate 123 by any permutation and get 123.  The conjugate of 213 has odd parity.  Thus S contains 123 and the three transpositions.  This set of size 4 is not a subgroup of the 6 permutations on 3 elements, since 4 does not divide into 6.

Given Q, let S be all the conjugates of all the elements in Q and their inverses, then let R be all the finite products thereof.  Conjugate anything in R and find another word in R.  Thus R is the normal subgroup generated by Q, and the smallest normal subgroup containing Q.

Let K be normal in G and let H be any subgroup of G.  Let R be the subgroup generated by K and H, also called K join H, and let J be the intersection of K and H.

For every x in G, x*K/x winds up in K.  This still holds if x belongs to R, hence K is normal in R.

Except for J itself, each coset of J is completely separate from J.  If part of a coset of J is in H, the entire coset is in H, since all of J is in H - and similarly for K.  A coset of J might belong to K, or H, but not both, as J is their intersection.

Let X be the right cosets of J in H, and Y the right cosets of J in K.  Formally, X is a collection of cosreps, somewhat arbitrary, and so is Y.  Let 1, the group identity, represent J in both X and Y.  Since J is the complete intersection of H and K, 1 is the only element common to X and Y.

K and H are partitioned into cosets of J. The join consists of elements of J, cross cosreps of J in K, cross cosreps of J in H.

If an element e1 is x1y1j1, and e2 is x2y2j2, what can we say about e3, the product of e1 and e2?  It begins life as x1y1j1x2y2j2.  Since K is normal in R, the left and right cosets of x2 are the same.  Move y1j1 to the right of x2, replacing it with a new value from K.  This gives x1x2y3j3y2j2.  Now everything to the right of x2 is an element of K, and x1x2 is another coset of J in H, so the element e3 is the product of elements taken from x, y, and J, in that order.  Then build an inverse for x1y1j1 starting with the inverse of x1 in H, and all of R is represented by these triples.

If two triples lead to the same element, i.e. x1y1j1 = x2y2j2, multiply by x2 inverse on the left.  Now the product x2 inverse times x1, call it x3, is multiplied by something in K, and produces something in K.  This places x3 in K, and in H, and in J, whereupon x3 = 1.  The original cosreps x1 and x2 are the same.  Divide these out, leaving elements in K.  Now y1 = y2, and j1 = j2, and the triples were in fact identical.  Elements of R correspond 1 for 1 with triples drawn from x, y, and J.

The xyj representation is convenient, but don't assume you can just multiply components together.  After all, R is not a direct product.  When we pull elements past each other, y1 is replaced with y3, and so on.  However, the projection onto H/J is a proper group homomorphism.  This is not surprising, since K is normal in R.  If e1 starts with x1, and e2 starts with x2, then e1e2 starts with x1x2.  The cosets of J in H faithfully represent the cosets of K in R.

The cosets of J in K become cosets of H in R, but this is not a faithful representation; there is no homomorphism from R onto K.

If R is finite, the order of R is |H|/|J| * |K|/|J| * |J| = |H|*|K|/|J|.  Divide both sides by |J|, and the index of J in R is the index of J in H times the index of J in K.

Watch what happens when H and K are not normal.  Let G = Sp, the permutation group on p letters.  Let H be a p cycle, and let K be a 2 cycle.  The intersection is 1.  H join K looks like it should be a group of size 2p; yet H and J generate all of G, a group of size p!.  (This will be demonstrated later.)

At the other end of the spectrum, let H and K both be normal in G, and let R be H join K as described above.  The projection onto H/J and the projection onto K/J are both group homomorphisms.  In other words, you can simply multiply x1x2 and y1y2.

If H and K are disjoint, intersecting only in the identity element, then you don't have to worry about J at all.  R becomes the direct product of H and K.

Center, Centralizer, Normalizer Table of Contents Start of chapter

Recall that the center of G is the set of elements that commute with all of G.  This includes 1 at a minimum.  Verify that the center is a subgroup, in fact it is a normal subgroup of G.

The centralizer of a subgroup H is the set of elements that commute with everything in H.  Verify that the centralizer of H is a group.  Inverse is the only tricky part.  If b commutes with H, does b inverse?  Given H/b, multiply by 1 = (1/b)*b on the left.  Replace bH with Hb and get 1/b times H.

The centralizer of G is the center of G.  Descend down through a chain of subgroups, and the centralizer gets larger, until the centralizer of 1 is all of G.

The normalizer of a subgroup H is the set of all elements x such that xH/x = H, as a set.  Clearly H is in the normalizer of H.  Remember that conjugation by x is an inner automorphism on G, thus an automorphism on H.  This can be reversed, hence 1/x implements an automorphism on H, and 1/x is in the normalizer.  Similarly, xy is in the normalizer when x and y are both in the normalizer.  Thus the normalizer is a group.

Since everything in the normalizer fixes H by conjugation, H is normal in its normalizer.

Don't confuse the normalizer of H with the normal subgroup generated by H.  They are quite different.  When H is normal in G it is its own normal subgroup, yet its normalizer is all of G.  Conversely, the smallest normal subgroup containing H might be all of G, and the normalizer of H could simply be H.

H is normal in its normalizer N, which is a subgroup of G.

The Correspondence / Isomorphism Theorems Table of Contents Start of chapter

The correspondence theorems assert the equivalence of the subgroups (first correspondence theorem) or normal subgroups (second correspondence theorem) of G with those in the factor group H.  In other words, subgroups containing K, or normal subgroups containing K, correspond 1 for 1 with subgroups or normal subgroups in the factor group H = G/K.  The third correspondence theorem equates G/F with (G/K)/(F/K).  This is similar to 100/25 = (100/5)/(25/5).  The two quotient groups are isomorphic, hence these three theorems are sometimes called the three isomorphism theorems, though only the third builds a true isomorphism, so I prefer the word correspondence.  Let's get started.

Let K be a normal subgroup of G, with factor group H.  If R is a subgroup of G, its image S is a subgroup of H.  Conversely, if S is a subgroup of H, its preimage R, which contains K, is a subgroup of G.  Use the a/b test to verify this.

S, the image of R, is a subgroup of G/K.

Apply the x*w/x test, and verify R is normal in G iff its image S is normal in H.  Subgroups and normal subgroups of H correspond 1 for 1 with subgroups and normal subgroups of G containing K.

Now assume F is normal in G, and K is normal in both F and G.  Let H be the factor group G/K, as it was above.  By the above, the image of F in H is a normal subgroup of H.  This leads to a factor group R.  We will show that R is the same as G/F.  Mod out by K first, and then F; it's the same as G/F.

The map is straightforward, though somewhat technical.  Given a coset of F in G, choose a cosrep x, let it define a coset of K in G, i.e. an element of H, and let that element of H define a coset of the image of F in H, i.e. an element of R.  First show this is well defined.  Multiply x by y for some y in F, and see if this changes anything.  Moving to H, the image of x is multiplied by something in the image of F.  This leads to the same element of R.  So it doesn't matter which cosrep we use.

Use the property of group homomorphism, from G to H to R, to show this map commutes with *, and is a group homomorphism.  Since H is the image of G and R is the image of H, the map is onto.  Finally, back up from 1 in R, to the image of F in H, to F in G, hence the kernel contains only F, and no other cosets of F, and the map is an isomorphism.

You might think there is another form of correspondence, wherein isomorphic kernels lead to isomorphic quotients, but this is not the case.  Let G = Z/p * Z/p2, the integers mod p cross the integers mod p2.  Let the kernel be the first component, and the quotient is the integers mod p2.  Then let the kernel be the multiples of p within Z/p2.  This is a subgroup of order p, just like the first kernel, but the quotient is Z/p * Z/p.

Dihedral Group Table of Contents Start of chapter

The continuous dihedral group, Dc, is the rotations and reflections of the plane, or the unit circle representing the plane.  This group is isomorphic to the orthonormal matrices in 2 dimensions.  Those matrices implement rigid rotations and reflections of the plane.  The matrices with norm 1 are the rotations, and the matrices with norm -1 are the reflections.  These are true reflections, through a line that passes through the origin.

The rotations are a subgroup of index 2, and are normal in the dihedral group.

turn the unit circle into an n-gon, and the dihedral group is quantized.  Only certain angles of rotation are allowed, so that edges correspond to edges; and only certain reflections are allowed.  There are, as you would imagine, n rotations and n reflections.  If n is even, the line of reflection runs from one vertex to the opposite vertex, or from the midpoint of an edge to the midpoint of the edge on the opposite side; if n is odd the axis runs from one vertex to the midpoint of the opposite side.  Flip the coin over about this axis to realize the reflection.

This group is denoted Dn, and is called the dihedral group on n edges.  In fact dihedral comes from the latin for two sides, like heads and tails of a coin.

Verify that this group is nonabelian.  Rotate one step clockwise, then flip; that is not the same as a flip followed by a rotation.

Octagon with edges labeled 1 to 8

We characterized the subgroups of a cyclic group before; what are the subgroups of G = Dn?

Let R be the group of rotations in G.  R is normal in G, and its subgroups correspond to the divisors of n.  These are still subgroups of G, in fact they are normal subgroups of G.  Stand at the axis of reflection, flip, rotate by θ, and flip back.  This realizes a rotation of -θ, which is part of the cycle.  Thus a rotational subgroup is normal even in Dc.

Let H be a subgroup of G, and intersect H with R, and find a cycle K.  If K is all of H then we are done.

Now assume H contains a reflection, implemented as f(x) = j-x.  For each rotation c in K, H includes the composite function j+c-x.  In other words, j represents a coset of K in R.  If H also contains i-x, where i is in some other coset, compose the two flips and get i-j+x.  Now i-j is a rotation that is not in K, and that is a contradiction.  Thus H is K in R, along with a coset of K acting as reflections.

Remember that K could be trivial, whence H is a single flip, an involution.

General Linear, Special Linear Table of Contents Start of chapter

The general linear group of order n is the set of nonsingular nn matrices under multiplication.  The special linear group is the kernel of the homomorphism implemented by the determinant, namely the nn matrices with determinant 1.  These groups are written GLn(R) and SLn(R), for nn matrices over a ring R.  You can read more about these groups over finite fields here.

Coliniation Table of Contents Start of chapter

A coliniation is a permutation group that carries subsets of points to other subsets of points.  The name coliniation is related to the word colinear, where the predefined subsets all contain two points.  Each permutation carries pairs of points to other pairs of points, hence lines to lines.  Each graph determines a coliniation.

Consider a regular n-gon.  A permutation begins by mapping one vertex onto any other vertex in the n-gon.  But lines must map to lines, so the adjacent vertex must map to a vertex that is adjacent to the image of the first.  This continues as we work our way around the n-gon.  The coliniation is Dn.

Map 1, then there are two places to map 2, and the rest is determined

Symmetric, Alternating Table of Contents Start of chapter

The symmetric group on n letters, written Sn, is the group of all possible permutations on n letters.  The order of Sn is n!.

The alternating group on n letters, written An, is the group of all even permutations on n letters.  The order of An is n!/2.  An is normal in Sn, in fact it is the kernel of the parity homomorphism.

The group An+1 defines the group of rotations of a generalized tetrahedron in n-space, while Sn+1 defines the group of rotations and reflections.  This can be seen by placing any vertex in position, then the next, then the next, and so on, and reflecting if the last two must be swapped.

The symmetric group is the group of rotations and reflections of a tetrahedron

For S, parity, and hence A, may be well defined if permutations transpose only a finite number of letters in an infinite set corresponding to the integers.  The parity function is well defined, and A is the kernel of this homomorphism, and is normal in S.