ORBITS, ACTIONS and COSETS
Definition: Let X be a set and let G be a group. We call X
a "G-set" and we say "G acts on X" provided the following
conditions hold:
(1) each g belongs to G gives rise to a function
g : X ---> X,
(2) the identity 1 belonging to the group G defines the
identity function on X,
(3) if g, h belong to G then the composite
gh : X ---> X
defined by g h
X -----> X -----> _ X
\________________/|
gh
(gh)(x) = h(g(x)).
Definition: Let G act on a set X. We call the action "transitive"
if for each pair x, y belonging to X there is a g in G such that
y = g(x). We call the action "free" if the only g in G which
fixes some x in X is the element g=1 (i.e., g(x)=x => g=1).
Example: Let X be a set and let G = S_X be the symmetric
group of X. Then X is a G-set and g acts on X.
Exercise: Show that the action in the previous example is both
free and transitive.
Example: Let G be the "symmetric group of the square": i.e.,
the group of symmetries of the square generated by the rigid
motions
g1 = reflection about l1,
g2 = reflection about l2,
g3 = reflection about l3,
g4 = 90 degrees clockwise rotation about O,
where l1, l2, l3 denote the lines of symmetry in the picture
below:
\ | /
\_______|_______/
|\ | /|
| \ | / |
| \ | / |
| \ | / |
| \ | / |
| \ | / |
___|______\|/______|___ l2
| /|\ |
| / |O\ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
|/______|______\|
/ | \
/ | \
l1 l3
Let X be the set of vertices of the square. Then G acts on X.
Example: Let X be the set of labels of the facets on the Rubik's
cube. Let G be the permutation group generated by the permutations
R, L, U, D, F, B, regarded as elements of S54. Then G acts on X.
Exercise: Let G be a group and let X = G. Define "left multiplication
of G on X" by:
g : X ---> X
g(x) = g*x.
(a) Show that this defines an action of G on X.
(b) Show that this action is transitive.
(c) Show that this action is free.
Exercise: Let G be a group and let X = G. Define "conjugation on
X" by:
g : X ---> X
x |-> g(x) = g*x*g^(-1).
Show that this defines an action of G on X.
Exercise: Let G be a group and let X denote the set of all subgroups
of G. Define "conjugation on X" by:
g : X ---> X
g(x) = g*x*g^(-1).
Show that this defines an action of G on X.
Remark: In general, the actions in the last two exercises are not
transitive.
Definition: Let G be a group acting on a set X. For each x belonging
to X, the set
Gx = { g(x) | g in G }
is called the "orbit" of x in X under G.
Algorithm
Input: A set S of generators of a permuation group G and an x
belonging to X
Output: The orbit of x, G*x
orbit = {x}
for y in orbit do
for g in S do
if g*y not in orbit then orbit = orbit union {g*y} endif
endfor
endfor
Note that the size of the list orbit in the for loop changes after
each iteration of the loop. As mentioned before, the meaning of
this is that the if-then command is to be executed exactly once
for each element of the list.
Exercise: Let G be the group of moves of the Rubik's cube and let
X be the set of vertices of the cube. Let H be the subgroup of G
generated by U*R. Find:
(1) the order of U*R,
(2) the orbit (in the Singmaster notation) of the ufr vertex in X
under H.
Definition: Let G be a group acting on a set X. For each x belonging
to X, the subgroup
stab_G(x) = G_x = { g in G | g(x) = x }
is called the "stabilizer" of x in G.
Example: Let G be the group of symmetries of the square, let X be the
set of vertices of the square, and let x0 be the vertex in the lower
right hand corner. Then stab_G(x0) = .
Exercise: Let G be any group and let X=G. Let G act on X by "left
multiplication":
g : X ---> X
x |-> g(x) = g*x.
Show that
stab_G(x) = {1},
for all x belonging to X=G.
Exercise: Let G be any group and let X=G. Let G act on X by "conjugation":
g : X ---> X
x |-> g(x) = g*x*g^(-1).
Show that
stab_G(x) = { g in G | g*x=x*g },
for all x belonging to X=G. (This subgroup { g in G | g*x=x*g } is called
the "centralizer" of x in G.)
Example: 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. 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 facts 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.
Cosets
Let G be a group and H a subgroup of G. For g belonging to G, the
subset g*H of G is called a "left coset" of H in G and the subset
H*g of G is called a "right coset" of H in G.
Exercise: If H is finite, show |H| = |g*H| = |H*g|.
Exercise: If X is a left coset of H in G and x is an element of G,
show that x*X is also a left coset of H in G.
The set of all left cosets is written G/H and the set of all right
cosets of H in G is denoted H\G. These two sets may npot be grouups
in themselves but they are useful none-the-less. For example, we have
the following relationship between the orbits and the cosets of
the stabilizers.
Lemma: Let G be a finite group acting on a set X. Then
|G*x| = |G/stab_G(x)|,
for all x belonging to X.
proof: The map
g*stab_G(x) |----> g*x
defines a function f : G/stab_G(x) --> G*x. This function is a bijection
since it is both and injection (Exercise: Check this) and a surjection
(Exercise: Check this). QED
Exercise: Let G be the group of symmetries of the square. Using the
notation above, compute G/ and G*x0.
Theorem (Lagrange): If G is a finite group and H a subgroup then
|G/H| = |G|/|H|.
Corollary: If H, G are as above then the order of H divides the
order of G.
proof of Theorem: Let X be the set of left cosets of H in G and let G
act on X by left multiplication. Apply the previous lemma with x=H. QED
Exercise: Let G = S3, the symmetric group on 3 letters, and let
H = , in the notation above.
(a) Compute |G/H| using Lagrange's Theorem.
(b) Explicitly write down all the cosets of H in G.
Definition: Let H be a subgroup of G and let C be a left coset of H
in G. We call an element g of G a "coset representative" of C if
C = g*H. A "complete set of coset representatives is a subset of
G
x1, x2, ..., xm,
such that
G/H = {x1*H, ..., xm*H },
without repetition (i.e., all the gi*H are disjoint).
Exercise: For g1,g2 in G, define g1 ~ g2 if and only if g1 and g2 belong
to the same left coset of H in G.
(a) Show that ~ is an equivalence relation.
(b) Show that the left cosets of H in G partition G.
Dimino's Algorithm
We saw in an earlier chapter an algorithm for computing all the
elements of a permuation group G. We shall discuss a more efficient
algorithm for doing this in this section. For more details, see
[Bu].
Notation: Let S = {g1, g2, ..., gn} be a set of generators for a
permutation group G. Let
S_0 = EMPTY,
S_i = { g1, ..., gi },
G_0 = {1},
G_i = = the group generated by the elements in S_i,
for 1 <= i <= n.
Algorithm (inductive step):
Input: The generators S of G and a list L of all the elements of the
permutation subgroup G_{i-1}.
Output: A list of elements of G_i
C = {1}
for g in C do
for s in S_i do
if s*g not in L then
C = C union {s*g}
L = L union s*g*G_{i-1}
endif
endfor
endfor
Algorithm (Dimino):
Input: The generators S of G
Output: A list of elements of G
(Initial case S_1 = )
order = 1, element[1] = 1, g = g1
while g <> 1 do
order = order + 1
element[order] = g
g = g*g1
endwhile
(General case)
for i from 2 to n do
endfor
Example: Let G = S3 = . We use Dimono's algorithm to list
all the elements of G. We have
G0 = {1} < G1 = < G2 = G.
First, we list the elements of G1 = . Since s1 = (1 2), it
is order 2, so
G1 = { 1, s1 }.
This is our list L which we will apply the "inductive step" of
Dimino's algorithm to (with i=2). We start with C={1}. Now we
look at the left cosets of G1 in G2=G. We have (with g=1, s=s1)
s1*G1 = G1,
so we don't increase the size of C or L. Next, we have (with g=1,
s=s2)
s2*G1 = { s2, s2*s1 } <> G1,
so L = {1, s1, s2, s2*s1}, C = {1, s2}. Next, we have (with g=s2,
s=s1)
s1*s2*G1 = { s1*s2, s1*s2*s1 } <> G1.
(We know s1*s2*G1 <> G1 since neither of the two elements in
s1*s2*G1 is the identity.) Thus, we increase L, C:
L = {1, s1, s2, s2*s1, s1*s2, s1*s2*s1},
and C = {1, s2, s1*s2}. We know we may stop here since we know
|S6| = 6 but the algorithm still has one more statement to
execute. Next, we have (with g=s2, s=s2)
s2*s2*G1 = G1,
so we don't increase the size of C or L (as expected). This
step terminates the algorithm and S3 = L.
Exercise: Perform Dimino's algorithm on
S4 = .