"The art of doing mathematics consists in finding that special
case which contains all the germs of generality."
David Hilbert
GROUPS, II
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 3x3 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 = 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 3x3 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 isomorophic
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.