“The art of doing mathematics consists in finding that special
case which contains all the germs of generality.”
David Hilbert
Given two groups G1, G2, a natural question is to ask how “similar” are they? (Exactly what is meant by “similar” will be explained later.) We shall, in this chapter, introduce notions and techniques useful for comparing two group. In a later chapter, we will apply this to the case of the 3×3 Rubik’s cube group, comparing it to “better understood” groups.
Homomorphisms
A homomorphism between two groups is, roughly speaking, a function between them which preserves the (respective) group operations.
Definition: Let G1, G2 be groups, with * denoting the group operation for G1 and ** the group operation for G2. A function f : G1 –> G2 is a homomorphism if and only if, for all a,b in G1, we have
f(a*b) = f(a)**f(b).
Example: Let G be a group and h a fixed element of G. Define f : G –> G by
f(g) = h^(-1)*g*h, g in G.
Then the following simple trick
f(a*b) = h^(-1)*(a*b)*h
= h^(-1)*a*h*h^(-1)*b*h
= f(a)*f(b)
shows that f is a homomorphism.
Exercise: Let
[ 0 1 0 ] [ 1 0 0 ]
A = [ 1 0 0 ], B = [ 0 0 1 ],
[ 0 0 1 ] [ 0 1 0 ]
To help yourself visualize the effect these matrices have, let
[ 1 ]
v = [ 2 ]
[ 3 ]
and notice that Av is the same as v, except that 1, 2 have been swapped. Thus A has an analogous effect as the permutation (1 2). (Exercise: What is Bv?) Now, let G = <A,B> denote the group of all matrices which can be written as any arbitrary product of these two matrices (in any order and with as many terms as you want). We have
[ 1 0 0 ] [ 0 1 0 ] [ 1 0 0 ]
G = { I3 = [ 0 1 0 ], [ 1 0 0 ], [ 0 0 1 ],
[ 0 0 1 ] [ 0 0 1 ] [ 0 1 0 ]
[ 0 1 0 ] [ 0 0 1 ] [ 0 0 1 ]
[ 0 0 1 ], [ 1 0 0 ], [ 0 1 0 ] }.
[ 1 0 0 ] [ 0 1 0 ] [ 1 0 0 ]
(You may want to try to check this as an exercise by regarding each such matrix as a permutation matrix.) Define f : G –> S3 by
g | f(g)
--------------
I3 | 1
A | s1
B | s2
AB | s1*s2
BA | s2*s1
ABA | s1*s2*s1
Show that this is a homomorphism.
Lemma: If f : G1 –> G2 is a homomorphism then
(a) f(e1)=e2, where e1 denotes the identity element of G1 and e2 denotes
the identity element of G2,
(b) f(x^(-1))=f(x)^(-1), for all x belonging to G1,
(c) f(y^(-1)*x*y)=f(y)^(-1)**f(x)**f(y), for all x,y belonging to G,
(* denoting the group operation for G1 and ** the group operation
for G2).
proof: (a) We have f(x)=f(x*e1)=f(x)**f(e1), for any x in G. Multiply both sides of this equation on the left by f(x)^(-1).
(b) We have, by part (a), e2=f(e1)=f(x*x^(-1))=f(x)**f(x^(-1)). Multiply both sides of this equation on the left by f(x)^(-1).
(c) Exercise. QED
Definition: A homomorphism f : G1 –> G2 is a isomorphism if it is a bijection (as a function between sets). If f is an isomorphism from a group G to itself then we call f an automorphism.
The notion of an isomorphism is the notion we will use when we want to same two groups are “essentially the same group”.
Example: Let G be the group in the above exercise and f : G –> S3 the homomorphism. This is in fact an isomorphism.
Exercise: As above, let G be a group and h a fixed element of G. Define f : G –> G by
f(g) = h^(-1)*g*h, g in G.
Show that this is an automorphism.
(solution: To verify this, we must show that f is injective and surjective. First, we show that f is injective. Suppose f(g1)=f(g2). Then f(g1*g2^(-1))=1, so that h^(-1)*g1*g2^(-1)*h=1. Multiply both sides of this equation on the left by h and on the right by h^(-1). We obtain g1*g2^(-1)=1. This implies g1=g2, so f is injective. Now we show f is surjective. Let g be an arbitrary but fixed element of G. Let y=h*x*h^(-1). Then
f(y)=f(h*x*h^(-1))=h^(-1)*h*x*h^(-1)*h=x.
Therefore, f is surjective.)
Notation: The set of all automorphisms of a group G is denoted Aut(G).
Exercise: Show Aut(G) is a group with composition as the group operation.
Kernels and normal subgroups
Let f : G1 –> G2 be a homomorphism between two groups. Let
ker(f) = { g in G1 | f(g)=e2 },
where e2 is the identity element of G2. This set is called the kernel of f.
Lemma: ker(f) is a subgroup of G1.
This is left as an exercise.
The following properties of the kernel are useful:
Lemma: Let f : G1 –> G2 be a homomorphism between two groups.
(a) f is injective if and only if ker(f)={1}.
(b) if g belongs to the kernel and x is any element of G1 then x^(-1)*g*x must belong to the kernel.
proof: (a) f is injective if and only if f(g1)=f(g2) implies g1=g2 (g1,g2 in G1). Note f(g1)=f(g2) is true if and only if f(g1*g2^(-1))=1. If ker(f)={1} then f(g1*g2^(-1))=1 implies g1*g2^(-1)=1, which implies g1=g2, which implies f is injective. Therefore, if ker(f)={1} then f is injective. Conversely, if f is injective then f(x)=f(e1) (=e2) implies x=e1 (x in G1). This implies ker(f)={1}.
(b) Multiply both sides of e2=f(g) on the left by f(x)^(-1)
and on the right by f(x). We get
e2 = f(x)^(-1)*e2*f(x) = f(x^(-1))*f(g)*f(x) = f(x^(-1)*g*x),
as desired.
Definition: Let H be a subgroup of G. We say that H is a normal subgroup if, for each g in G, g^(-1)*H*g=H (i.e., for each g in G and each h in H, g^(-1)*h*g belongs to H).
Notation: Sometimes we denote “H is a normal subgroup of G” by
H <| G
(this is supposed to be an isosceles triangle but it doesn’t come out
well in ascii).
We have already shown the following
Lemma: If f : G1 –> G2 is a homomorphism between two groups then ker(f) is a normal subgroup of G1.
One of the most useful facts about normal subgroups is the following:
Lemma: If H is a normal subgroup of G then G/H is a group with the following operation:
aH*bH = abH, (aH)^(-1)=a^(-1)H,
for all a, b belonging to G. The identity element of this group is the trivial coset H.
The proof of this is left as an exercise. This group G/H is called the quotient group of G by H and is sometimes pronounced “G mod H”.
Example: If f : G1 –> G2 is a homomorphism between two groups then G1/ker(f) is a group.
The following basic result tells us essentially what the quotient group G1/ker(f) is:
Theorem: (“first isomorphism theorem“) If f : G1 –> G2 is a homomorphism between two groups then G1/ker(f) is isomorphic to f(G1).
The other isomomorphism theorems will not be needed but help to illustrate the usefulness of the notion of “normality”:
Theorem: (“second isomorphism theorem“) If H, N are subgroups of a group G and if N is normal then
(a) H intersect N is normal in H,
(b) there is an isomorphism between
H/(H intersect N)
and
NH/N.
Theorem: (“third isomorphism theorem“) If N1, N2 are subgroups of a group G, if N1 subset N2, and if N1 and N2 are both normal then
(a) N2/N1 is normal in G/N1,
(b) there is an isomorphism between
(G/N1)/(N2/N1)
and
G/N2.
We shall not prove this result here – see [G] or [R].
Direct products
Let H1, H2 be two subgroups. We say that a group G is the direct product of H1 with H2, written
G = H1 x H2,
if (a) G=H1xH2 (Cartesian product, as sets), (b) multiplication in G is given by
(x1,y1)*(x2,y2) = (x1*x2,y1*y2),
x1, x2 in H1, y1, y2 in H2 (where * denotes multiplication in H1, H2, and G).
Example: Let’s return to an example from the above chapter on orbits. Let X be the set of consisting of the 48 facets of the Rubik’s cube which are not center facets – i.e., the “movable” facets. Let Xc denote the subset of facets which belong to some corner subcube, Xe the subset of facets which belong to some edge subcube. Let G denote the Rubik’s cube group. Let F be the subgroup of the Rubik’s cube which preserves edges and corner vertices (and hence does not move a corner subcube to another corner subcube but may rotate it, and does not move an edge subcube to another edge subcube but may flip it).
Note that G acts on X, Xc, Xe. The action of G on X induced an equivalence relation as follows: we say that a facet f1 is “equivalent” to a facet f2 if there is an element of G (i.e., a
move of the Rubik’s cube) which sends one facet to the other. There are exactly two equivalence classes, or orbits, of G in X: Xc and Xe. In particular, the action of G on Xc is
transitive and the action of G on Xe is transitive. The same is true for F: The action of F on X induced an equivalence relation as follows: we say that a facet f1 is “equivalent” to a facet f2 if there is an element of F which sends one facet to the other. There are exactly two equivalence classes, or orbits, of F in X: Xc and Xe. In particular, the action of F on Xc is transitive and the action of F on Xe is transitive.
Let S_X, S_Xc, S_Xe, denote the symmetric group on X, Xc, Xe, respectively. We may regard F, G, as subgroups of S_X. We may also regard S_Xc, S_Xe as subgroups of S_X (for example, S_Xc is the subgroup of S_X which leaves all the elements of Xe fixed). Let
Gc = S_Xc intersect G,
Ge = S_Xe intersect G,
Fc = S_Xc intersect F,
Fe = S_Xe intersect F.
The interesting thing is that we have
F = Fc x Fe (direct product).
Exercise: Notation as in the above example.
(a) Show F = Fc x Fe (direct product).
(b) Is G = Gc x Ge?
(c) Is S_X = S_Xc x S_Xe?
Semi-direct products
Now suppose that H1, H2 are both subgroups of a group G. We say that G is the “semi-direct product” of H1 with H2, written
G = H1 |x H2
if (a) G=H1*H2, (b) H1 and H2 only have 1, the identity of G, in common, (c) H1 is normal in G. This is the “internal version” of the semi-direct product. Note that the multiplication rule in G doesn’t have to be mentioned since we are assuming here that G is “known”.
The “external version” is defined by a construction as follows: assume we have a homomorphism
phi : H2 --> Aut(H1).
Define multiplication on H1 |x H2 by
(x1,y1)*(x2,y2) = (x1*phi(y1)(x2),y1*y2).
This defines a group operation. As a set, H1 |x H2 is simply the cartesian product H1xH2.
Example: Let
S3 = { 1, s1, s2, s1*s2, s2*s1, s1*s2*s1 },
H1 = { 1, s2, s1*s2*s1 },
H2 = { 1, s1 }.
(Note: H1, H2 are not normal subgroups of G.) Let
phi : H2 --> Aut(H1)
be defined by
phi(1) = 1 (the identity automorphism)
phi(s1)(h) = s1^(-1)*h*s1 = s1*h*s1 (since s1^(-1)=s1), h in H1.
Define the (external) semi-direct product of H1, H2 by
G = H1 x| H2.
This is not a subgroup of S3 since H1 is, by construction, a normal subgroup of G and we already H1 is not a normal subgroup of S3.
Wreath products
Let G1 be a group acting on a set X1, let G2 be a group acting on a set X2. We shall assume that these are all finite. Let S_(X1xX2) denote the symmetric group of the cartesian product X1xX2. Define the “wreath product” of G1, G2 by
G1 wr G2 = { t in S_(X1xX2) |
t : (x1,x2) |--> (psi(x2)(x1),g2(x2)), for
some g2 in G2, and some function
psi : X2 --> G1 }.
Thus, to each t in G1 wr G2 there is an g2 in G2. We denote this “projection” by g2 = pr(t). Define the “base” of the wreath product by
B = { t in G1 wr G2 | pr(t) = 1 }.
Lemma: (a) B is isomorphic to the cartesian product
G1^|X2|
(i.e., to G1xG1x…xG1, n times, where n is the number of elements of X2),
(b) B is a nornmal subgroup of G1 wr G2,
(c) (G1 wr G2)/B is isomorphic to G2.
For this, we refer to [NST], chapter 8.
Example: ([NST], chapter 19) Let Q be the group of all “legal and illegal moves” of the 3×3 Rubik’s cube. In other words, in addition to the usual moves, we allow you to take apart the cube and reassemble it (but we do not allow you to remove stickers from the facets). As in the example above, Q acts on X, Xc, Xe. Let
Qc = S_Xc intersect Q,
Qe = S_Xe intersect Q.
Let Z3 denote the group of all rotations of a corner subcube by a 120 degree angle (actually, this group depends on the corner being rotated but since these groups are all isomorphic
we drop the dependence from the notation). Let Z2 denote the group of all flips of an edge subcube (rotations by a 180 degree angle). (Again, this group depends on the edge being flipped but since these groups are all isomorophic we drop the dependence from the
notation). Then
Q = Qc x Qe,
Qc is isomorphic to Z3 wr S_Xc,
and
Qe is isomorphic to Z2 wr S_Xe.
This is left as an exercise.
Yet Another Mathblog 