[ Pobierz całość w formacie PDF ]

Theorem 2.35. The orbits of an action of (G, ") on X decompose X into a union of disjoint
subsets,
X = U.
U an orbit
Corollary 2.36. If X is finite then
|X| = |U|.
U an orbit
In these results, each orbit U has the form OrbG(xU ) for some element xU " X. Moreover,
if G is finite, then
|G|
|U| = [G : StabG(xU )] = .
| StabG(xU )|
The formula in Corollary 2.36 becomes the orbit-stabilizer equation:
|G|
(2.3) |X| = .
| StabG(xU )|
U an orbit
If there is only one orbit, then the action is said to be transitive, and in this case, for any x " X
we have X = OrbG(x) and |X| = |G|/| StabG(x)|.
Given an action of (G, ") on X, another useful idea is that of the fixed point set or fixed set
of an element g " G,
FixG(g) = {x " X : gx = x}.
FixG(g) is also often denoted Xg.
Theorem 2.37 (Burnside Formula). If (G, ") acts on X with G and X finite, then
1
number of orbits = | FixG(g)|.
|G|
g"G
7. GROUP ACTIONS 41
Proof. The right hand side of the formula is
1 1
| FixG(g)| = 1
|G| |G|
g"G g"G x"FixG(g)
1
= 1
|G|
x"X g"StabG(x)
1
= | StabG(x)|
|G|
x"X
1
= |U| · | StabG(x)| (by Corollary 2.34)
|G|
U = OrbG(x)
an orbit
1
= |G|
|G|
U an orbit
= 1
U an orbit
= number of orbits.
Example 2.38. Let X = {1, 2, 3, 4} and let G S4 be the subgroup
G = {¹, (1 2), (3 4), (1 2)(3 4)}
acting on X in the obvious way. How many orbits does this action have?
Solution. Here |G| = 4 = |X|. Furthermore we have
FixG(¹) = X, FixG((1 2)) = {3, 4}, FixG((3 4)) = {1, 2}, FixG((1 2)(3 4)) = ".
The Burnside Formula gives
1 8
number of orbits = (4 + 2 + 2 + 0) = = 2.
4 4
So there are 2 orbits, namely {1, 2} and {3, 4}.
Example 2.39. Let X = {1, 2, 3, 4, 5, 6} and let G = (1 2 3)(4 5) S6 be the cyclic
subgroup acting on X in the obvious way. How many orbits does this action have?
Solution. Here |G| = 6 and |X| = 6. The elements of G are
¹, (1 2 3)(4 5), (1 3 2), (4 5), (1 2 3), (1 3 2)(4 5).
The fixed sets of these are
FixG(¹) = X, FixG((1 2 3)(4 5)) = FixG((1 3 2)(4 5)) = {6},
FixG((4 5)) = {1, 2, 3, 6}, FixG((1 2 3)) = FixG((1 3 2)) = {4, 5, 6}.
By the Burnside Formula,
1 18
number of orbits = (6 + 1 + 3 + 4 + 3 + 1) = = 3.
6 6
So there are 3 orbits, namely {1, 2, 3}, {4, 5} and {6}.
Example 2.40. A dinner party of seven people is to sit around a circular table with seven
seats. How many distinguishable ways are there to do this if there is to be no  head of table ?
42 2. GROUPS AND GROUP ACTIONS
Solution. View the seven places as numbered 1 to 7. There are 7! ways to arrange the
diners in these places. Take X to be the set of all possible such arrangements, so |X| = 7!.
Regard two such arrangements as indistinguishable if one is obtained from the other by a rotation
of the diners around the places. Clearly there are 7 such rotations, each involving everyone
moving k seats to the right for some k = 0, 1, . . . , 6. Let ± denote the rotation corresponding
to everyone moving one seat to the right. Then to get everyone to move k seats we repeatedly
apply ± k times in all, i.e., ±k. This suggests we should consider the group
G = {¹, ±, ±2, ±3, ±4, ±5, ±6}
consisting of all of these operations, with composition as the binary operation. This provides
an action of G on X.
The number of indistinguishable seating plans is the number of orbits under this action, i.e.,
1
| FixG(g)|.
|G|
g"G
Notice that apart from the identity element, no rotation can fix any arrangement, so when
g = ¹, FixG(g) = ", while FixG(¹) = X. Hence the number of indistinguishable seating plans is
7!/7 = 6! = 720.
Example 2.41. Find the number of distinguishable ways there are to colour the edges of
an equilateral triangle using four different colours, where each colour can be used on more than
one edge.
Solution. Let X be the set of all possible such colourings of the equilateral triangle ABC
whose symmetry group is G = S3, which we view as the permutation group of {A, B, C}; hence
|G| = 6. Also |X| = 43 = 64 since each edge can be coloured in 4 ways. G acts on X in the
obvious way. A pair of colourings is indistinguishable precisely if they are in the same orbit.
By the Burnside formula, the number of distinguishable colourings is given by
1
number of orbits = | FixG(Ã)|.
6
Ã"G
The fixed sets of elements of the various cycle types in G are as follows.
Identity element ¹: FixG(¹) = X, | FixG(¹)| = 64.
3-cycles (i.e., Ã = (A B C), (A C B)): these give rotations and can only fix a colouring that has
all sides the same colour, hence | FixG(Ã)| = 4.
2-cycles (i.e., Ã = (A B), (A C), (B C)): each of these gives a reflection in a line through a vertex
and the midpoint of the opposite edge. For example, (A B) fixes C and interchanges the edges
AC, BC, it will therefore fix any colouring that has these edges the same colour. There are
4 × 4 = 16 of these, so | FixG((A B))| = 16. Similarly for the other 2-cycles.
By the Burnside formula,
1 120
number of distinguishable colourings = (64 + 2 × 4 + 3 × 16) = = 20.
6 6
PROBLEM SET 2 43
Problem Set 2
2-1. Which of the following pairs (G, ") forms a group?
(a) G = {x " Z : x = 0}, " = ×;
(b) G = {x " Q : x = 0}, " = ×;
a b
(c) G = : a, b " R, a2 + b2 = 1 , " = multiplication of matrices;
-b a
z w
(d) G = : z, w " C, |z|2 + |w|2 = 1 , " = multiplication of matrices;
-w z
a b
(e) G = : a, b, c, d " Z, ad - bc = 0 , " = multiplication of matrices;
c d
a b
(f) G = : a, b, c, d " Z, ad - bc = 1 , " = multiplication of matrices;
c d
(g) G = {Õ " Sn : Õ(n) = n}, " = composition of functions.
2-2. For each of the following permutations in S6, determine its sign and decompose it into
disjoint cycles:
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
± = , ² = , ³ = .
3 4 2 5 6 1 3 6 4 1 5 2 3 4 1 6 2 5
2-3. Find the orders of the symmetry groups of the following geometric objects, and in each
case try to describe the symmetry groups as groups of permutations:
a) a regular pentagon;
b) a regular hexagon;
c) a regular hexagon with vertices alternately coloured red and green;
d) a regular hexagon with edges alternately coloured red and green;
e) a cube;
f) a cube with the pairs of opposite faces coloured red, green and blue respectively.
2-4. [Challenge question.] Suppose Tet is a regular tetrahedron with vertices A, B, C, D.
a) Show that the symmetry group Sym(Tet) of Tet can be identified with the symmetric group
S4 which acts by permuting the vertices.
b) For each pair of distinct vertices P, Q, how many symmetries map the edge P Q into itself?
Show that these symmetries form a group.
c) Find a geometric interpretation of the alternating group A4 acting as symmetries of Tet.
2-5. In each of the following groups (G, ") decide whether the subset H is a subgroup of G and
when it is, decide whether it is cyclic. [ Pobierz całość w formacie PDF ]