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 not be groups 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 permutation 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 = <s1, s2>. 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 = <s1=(1 2), s2=(2 3), s3=(3 4)>.
Yet Another Mathblog 