Many counting problems count objects up to some transformations. For
example, we can ask how many ways there are to make a round bracelet with
beads, each black or red. Turning a bracelet does not change it, so two
arrangements that differ by a rotation are the same bracelet. In
Figure 13.1, reading the beads counterclockwise from the
marked bead gives black, red, black, red on the left, and
black, red, black, red, black on the right; turning the
left bracelet by two beads produces the right one.
Figure13.1: Two descriptions of the same bracelet with beads. Reading counterclockwise from the marked bead gives 3B 2R 2B 3R on the left and 1B 2R 2B 3R 2B on the right. Turning the left bracelet by two beads gives the right one.#
To count such quantities efficiently, we need a precise language for the
transformations themselves. The algebraic notion that encodes transformations
is called a group.
After studying these notes, you will be able to do the following.
State what a group is, and recognize groups of transformations.
Describe every symmetry of a regular -gon as , and compute products using the relations and .
Describe the symmetric group of permutations of objects, and analyze the cycle structure of its elements.
Explain what a presentation of a group is, and the difficulties involved in studying a group given by a presentation.
Compose and invert permutations given by tables, and write permutations in cycle notation.
Compose overlapping cycles, and compute conjugates of permutations by relabeling.
Decide whether a subset of a finite group is a subgroup, and compute the order of an element.
Find the cyclic subgroup generated by an element, relate its size to the order of the element, and decide whether a group is cyclic.
We start with a smaller version of the bracelet problem, coloring the four
corners of a square, and identify the properties of the rotations that the
solution uses.
We label the corners of a square counterclockwise, starting at the
bottom left, and color each corner black or white. A coloring is recorded by
the string of the colors of corners ; for example,
BWWW colors corner black and the other three corners white. Each
of the four corners has two possible colors, so by the product rule there are
colorings.
Suppose now that the square is a tile lying on a table, with its corners
painted, and that the tile can be turned. Turning the tile by
counterclockwise carries the paint on corner to the place of corner ,
the paint on corner to the place of corner , the paint on corner to
the place of corner , and the paint on corner to the place of corner
. In terms of strings, each letter moves one place to the right and the
last letter moves to the front: BWWW becomes WBWW. We regard
two colorings as the same up to rotation if one of the four rotations,
by ,,, or , carries one coloring to
the other.
To find all colorings that are the same as a given one, we apply the
rotation repeatedly until we return to the starting coloring. For
example,
These four colorings form one class. Figure 13.2 sorts
all colorings into classes in this way.
Figure13.2: The black-and-white colorings of the corners of a square, sorted into classes of colorings that are rotations of one another. Corner is at the bottom left, and the corners continue counterclockwise. Going down a column turns the square by counterclockwise. The number above each column is the size of the class.#
We describe the classes by the number of black corners.
No black corners: WWWW is unchanged by every rotation, so its class has coloring.
One black corner: the black corner can be carried to any of the corners, so the class has colorings.
Two black corners that are adjacent, that is, joined by a side: the black pair can be carried to any of the sides, so the class has colorings.
Two black corners that are opposite: the black pair is one of the diagonals. The half turn carries BWBW to itself, so the class has only colorings.
Three black corners: the white corner can be any of the corners, so the class has colorings.
Four black corners: BBBB is unchanged by every rotation, so its class has coloring.
Every coloring appears in exactly one class, and indeed
So there are colorings of the corners of a square up to rotation.
Notice that is the wrong answer: the classes do not all have
elements, because some colorings are unchanged by some rotations. Counting
classes of different sizes without listing them is the subject of
the next lecture note.
Calling these sets classes makes a claim: the colorings split into sets
of colorings that are the same up to rotation, and no coloring lies in two
different sets. This claim depends on three properties of the four
rotations.
Every coloring is the same as itself, because the rotation by changes nothing.
If a rotation carries the coloring to , then the rotation by the opposite angle carries back to . So “the same up to rotation” does not depend on the order in which the two colorings are named.
If one rotation carries to and another carries to , then performing the two rotations in succession is again one of the four rotations, and it carries to .
The third property shows that the class found by repeated rotation of
BBWW contains every coloring that can be reached from BBWW,
and the second shows that every member of that class finds the same class.
Thus the classes are well defined because the rotations contain the
“do nothing” rotation, contain the reverse of each rotation, and are closed
under performing one rotation after another. These are the properties that
define a group.
The rotations of the square rearrange its corners, so we describe them as
permutations. A permutation of a finite set is a bijection
. For permutations and of , the composition
is the permutation
so is applied first. The identity is defined by ,
and the inverse sends back to . The rotation of the
square by counterclockwise is the permutation of
with
since the corner in place is carried to the place of corner , and
corner to the place of corner . The four rotations are ,,, and .
A group is a set together with an operation that assigns to every
an element , such that
(associativity) for all ;
(identity) there is an element with for all ;
(inverses) for every there is an element with .
The number of elements is the order of .
The requirement that lie in is the closure property used for the
colorings; the identity and inverses are the other two properties. For sets
of permutations with composition, associativity holds automatically:
and both equal . So a set of
permutations of is a group under composition exactly when it contains
, contains the inverse of each of its elements, and contains the
composition of any two of its elements.
The four rotations of the square, with composition. Composing two rotations adds their angles, the identity is , and the inverse of is , since turning by and then by is a full turn.
The set of all permutations of , with composition. Its order is . We study it in Section 13.5.
, where is defined as the remainder of on division by . The identity is , and the inverse of is .
In the operation is addition, written as multiplication only to
use one notation for all groups. In and in we always have
, but we will see in Section 13.3 that this fails for
the symmetries of the square. The set with addition is not
a group, because has no inverse in it.
Powers are defined by , ( factors), and
for ; then for all integers
and . The following consequences of the axioms hold in every group.
For (1), multiply on the left by and use associativity:
; the second statement is similar. For
(2), if and are both identities, then ; if and are
both inverses of , then , and cancellation gives . For (3),
, and similarly
.
Rule (3) reverses the order of the factors: to undo “first , then ,”
we first undo and then undo .
Let , and label the corners of a regular -gon
counterclockwise. We compute with corner labels modulo , so that
means corner and means corner . Two corners are adjacent
if they are joined by a side; the corners adjacent to are and
. A rotation or reflection that carries the polygon onto itself
preserves distances, so it sends adjacent corners to adjacent corners. We use
this as the definition.
A symmetry of the regular -gon is a permutation of
such that and are adjacent whenever and
are adjacent. The set of symmetries, with composition, is the
dihedral group.
The set is a group: the composition of two maps that preserve adjacency
preserves adjacency, does, and so does the inverse of a symmetry, because a
symmetry sends the adjacent pairs to different adjacent pairs, so its
inverse sends them back to adjacent pairs.
Where can a symmetry send the corners? The next proposition says that only two
pieces of information matter: where corner goes, and whether the images of
the corners run counterclockwise or clockwise.
Proposition13.5(A symmetry is determined by two choices)#
Let and . Then either for all , in which
case places the labels counterclockwise, or for all , in
which case places them clockwise. Conversely, each of these maps is a
symmetry. In particular, .
Corner is adjacent to corner , so is adjacent to : either
or . Suppose ; we show by
induction on . If and for some
, then corner is adjacent to , so is one of the two
neighbors and of . The first is already , and
is one-to-one, so . The case is the same with every
sign reversed.
Conversely, for each the maps and
are bijections of the corners modulo , and they send the adjacent corners
to the adjacent corners or . There are
choices of and directions, so .
Every symmetry of the polygon can be built from two particular ones. The
rotation turns the
polygon by counterclockwise, so
The reflection flips the polygon across the axis through corner
and the center. It fixes corner and exchanges corners that lie
symmetrically on the two sides of the axis:
Figure 13.3 shows and for the square and for the
pentagon. For the square, fixes corners and , which both lie on the
axis, and exchanges and . For the pentagon, fixes corner and
exchanges with and with ; the axis passes through corner and
the midpoint of the opposite side.
Figure13.3: The rotation by counterclockwise and the axis of the reflection , which passes through corner and the center, for the square () and the pentagon ().#
To picture a symmetry , we imagine the labels painted on the corners and
move the painted polygon by : the label ends up in the place of corner
.Figure 13.4 shows the square after the motions
,,, in the first row. In each picture the labels still run
counterclockwise, and label (in red) has moved one more place. The second
row starts from , where the labels run clockwise, then turns the result by
, and then reflects that result by . Each new motion is written to the
left of the motions already performed, so the second picture is , “first
, then ,” and the third is .
Figure13.4: The painted square after various motions. In the picture for , the label is in the place of corner ; label is red. First row: ,,,. Second row: , then (first , then ), then . The last picture agrees with the picture of .#
A permutation of a small set is conveniently written as a table: the top row
lists and the row below lists the image. For the square, each power of
is obtained from the previous one by applying once more, that is, by
adding to every entry of the previous row (with meaning ):
The last row is the top row, so . For the -gon, , so
, and the rotations are different, since
sends corner to corner . They form the rotation group.
For the square, ,,,. Applying twice
returns every corner to its place, so ; this holds for every , since
. To compute , we apply , then , then ,
filling in one row at a time:
The last row agrees with the row of in the previous table, so
Figure 13.4 shows the same computation. Geometrically,
reflecting, turning counterclockwise, and reflecting back amounts to turning
clockwise. The same holds for every :. Multiplying on the
right by and using gives the rule
which tells us how to move past . In particular, for
, since would give , that is, .
The rule answers the question of which elements make up . The
rotation sends corner to and keeps the counterclockwise order.
The product also sends corner to , since , but it
sends corner to , the corner before ; so places the
labels clockwise. By Proposition 13.5, the elements
are exactly the elements of , each listed once. The elements
are the reflections of the polygon. For the square, the four reflections have
the axes shown in Figure 13.5:
where and are the reflections across the vertical and horizontal axes,
and and are the reflections across the diagonals through
corners and through corners .
Figure13.5: The labeled square. Left: the rotation by counterclockwise. Right: the axes of the reflections ,,, and .#
A table listing all products quickly becomes impractical:
already has products. The previous section suggests a shorter
description. A word in and is a string of these letters, such
as , and it stands for the composition of the corresponding symmetries.
Every element of is given by some word, and we found three
relations
These relations are enough to compute every product. Applying
once for each factor gives , so each can be
moved to the right of each . Then removes pairs of ’s and
reduces the exponent of to one of . Every word
therefore reduces to one of the normal forms .
In ,, as we found from the tables. In ,
the word reduces as follows. First , so
using in the last step. The result has the form , so it is a
reflection.
We record such a description as a presentation, listing the
generators and then the relations:
In the same way and
.
In general, a presentation describes the group whose
elements are words in the generators and their inverses, where two words
represent the same element exactly when one can be transformed into the other
by inserting or deleting a relation from , or a pair or
. We do not need the formal construction of this group. A
presentation can be finite even when the group is not; for example,
, with no relations, describes the integers under
addition. For we could decide when two words are equal because we found
normal forms. For a general presentation no such procedure exists.
There is no algorithm that, given a finite presentation and a word in its
generators, decides whether the word equals the identity (Novikov 1955,
Boone 1958). Consequently, there is no algorithm that, given two finite
presentations, decides whether they define the same group; even deciding
whether a presentation defines the group with one element is impossible
(Adian 1957, Rabin 1958).
These results are proved by building presentations that simulate Turing
machines, in the same spirit as the undecidability of the halting problem; the
proofs are beyond this course. For a finite group given by explicit
permutations, these questions can be decided by checking finitely many cases.
This is one reason why, for counting, we work with explicit groups of
permutations.
The symmetries of a polygon are those permutations of its corners that
preserve adjacency. Dropping that condition and allowing every permutation of
objects gives the largest group of permutations of an -element set.
The symmetric group is the set of all permutations of
, with composition. It has elements.
is a group because the composition of two bijections is a bijection,
the identity is a bijection, and the inverse of a bijection is a bijection;
associativity holds for compositions, as we saw in Section 13.2. The
symmetries of the -gon are some of the elements of , namely those that
preserve adjacency. For every permutation of the corners of a triangle
preserves adjacency, so ; for , has elements.
We write an element of as a table whose top row lists and
whose bottom row lists the images. For example, in let
The identity is the table whose two rows agree. The inverse
reverses every arrow : we exchange the two rows of the table and
then sort the columns by the new top row. Since sends
,,,,, its inverse
sends ,,,,:
To check, , and similarly for the other entries.
To compose, we read the tables from right to left. For , each is
looked up first in the table of and then in the table of :,,,,. In the other order, . So , and
the order of composition matters in as it did in .
A table hides how a permutation moves the elements. Consider
Following through repeated applications of gives
, so these three elements are moved around in a
loop. The smallest element not yet visited is , and
. Next , so does not move. Finally
. Every element lies on exactly one of the loops
,,,. The next theorem says that
this always happens.
Let be a permutation of a finite set and . There is a
smallest with , and the elements
are distinct. These elements form the
cycle of containing , written ,
and every element of lies in exactly one cycle.
The elements cannot all be different, so
for some . Applying a total of times
gives . Let be the smallest positive integer with
. If with , the same argument gives
with , which is impossible; so the listed elements
are distinct. Starting from any element of the cycle and applying runs
through the same elements in the same cyclic order, so the cycle containing
is determined by any of its elements, and two cycles that share an
element are the same.
Listing the cycles of a permutation describes it completely and shows at once
how it moves the elements, so we use the cycles as the standard way to write
permutations.
In cycle notation a permutation is written by listing its cycles,
each in parentheses: means ,,,, and . A cycle
with elements is an -cycle, and a -cycle is a
transposition.
The permutation above is . A cycle of
length is a fixed point: it does not move anything, so cycles of
length are usually omitted, and we write . Every
element not listed is understood to be fixed, and the identity is written
. Because Theorem 13.8 lets a cycle start at any of its
elements, ,, and are the same cycle; but
is a different cycle, sending . Reading a cycle
backwards gives the inverse: .
We write for the number of cycles of ,including
the fixed points. The list of the lengths of the cycles, including the fixed
points and written in decreasing order, is the cycle type of .
The permutation above has and cycle type
. In cycle notation, the eight symmetries of the square are
So ,,, and
; for instance, has the
cycles ,, and . This number will count colorings in
the next lecture note:
a coloring is unchanged by exactly when it is constant on each cycle of
.
Each cycle is itself a permutation, which moves the elements of the cycle and
fixes all others. Cycle notation such as can therefore
also be read as a composition of three permutations. The two readings agree,
and the order in which the cycles are written does not matter, because of the
following fact. Two cycles are disjoint if they have no element in
common.
Let be any element. If lies in , then also lies in
, so fixes both and . Then
and . The
case where lies in is the same with the roles exchanged. If
lies in neither cycle, both products fix . So
for every .
For the second statement, let lie in the cycle of . In a
composition of the cycles of , every cycle other than fixes both
and , so the composition sends to , in any
order.
For example, : in either order, ,,,,, and every other element
stays fixed.
When two cycles share an element, Proposition 13.10 does not
apply, and the product usually cannot be read off from the factors. The only
reliable method is to follow each element through the factors from right to
left. Let us compute in , applying first:
Following from gives , so
In the other order we apply first:
so
The two products are different: one sends and the other
. Both are -cycles, although the factors are a -cycle and a
transposition, so even the cycle type of a product cannot be read from the
cycle types of overlapping factors. A common error is to apply the left factor
first; in this example that error turns one answer into the other.
Sometimes two permutations do the same thing to differently named elements.
In the square, and are both reflections across
a diagonal, and turning the square by carries the first diagonal to the
second. Conjugation makes this kind of renaming precise.
Let and be elements of a group . The conjugate of
by is .
For permutations, first undoes , then applies ,
then applies again. If we think of as renaming each element as
, then does to the new names what did to the
old ones.
Let . If , then sends to
. Consequently, the cycle notation of is obtained from
that of by replacing every entry by :
and similarly for each cycle of . In particular, and
have the same cycle type.
We compute .
Each arrow of therefore becomes the arrow
of . Since is a bijection, every element
has the form , so these arrows describe completely. A
cycle of becomes
the cycle of the same length.
With and , the proposition gives
Turning the square by carries the axis of , through corners
and , to the diagonal through corners and , and the conjugate is the
reflection across that rotated axis. In the other direction, since ,
which recovers without a table: the conjugate of a rotation by a
reflection is the rotation in the opposite direction.
Let and , so that ,,,,. Replacing each entry of by its
image under gives
As a check, , and ,
in agreement with the transposition . Both and its conjugate
have cycle type .
The converse of the last statement in Proposition 13.12 also
holds in : if and have the same cycle type, write both in
cycle notation including fixed points, with cycles of equal length in the same
positions, and let send each entry of to the entry of in the
same position. Then . So two permutations in are
conjugate exactly when they have the same cycle type.
A subgroup of is a subset that is a group with the
same operation: , and and whenever .
A subgroup of the group of all permutations of a set is a
permutation group on .
The rotations form a subgroup of , and so does
, since . The set is a subgroup of .
The permutations in that fix form a subgroup with
elements. The groups and are permutation groups on the corners of
the -gon. For finite subsets, closure under the operation is the only
condition that needs checking.
Let . By closure, all lie in . Since is
finite, for some , and cancelling gives
. So , and (which is if )
also lies in .
The proof shows that some power of every element of a finite group equals
. The first such power measures how many times must be repeated before
everything returns to its starting place.
The order of an element of a finite group is the smallest
positive integer with .
Such an exists by the argument in Proposition 13.16. In
, the rotations and have order , the five other elements
besides have order , and has order . In , the
element has order , since is the first multiple of
divisible by .
Write with . Then , which equals
exactly when , by the minimality of . If with
, cancellation gives with , which is
impossible. For a permutation , an element on a cycle of length
returns to itself after steps exactly when divides , so
exactly when is a common multiple of the cycle lengths; the
smallest such is their least common multiple.
For example, has order .
Every order we have found so far divides the order of the group: orders ,, in , and in . This always happens.
Theorem13.19(The order of an element divides the order of the group)#
Let be a finite group and . Then the order of divides ,
and .
Let be the order of . Multiplication on the right by , the function
, is a permutation of ; it is undone by . By
Theorem 13.8, splits into the cycles of . The cycle of
containing has length equal to the smallest with
, that is, . By cancellation, exactly
when , so every cycle has length exactly . The elements of
are therefore split into cycles of elements each, so divides
, and by Proposition 13.18.
For instance, no symmetry of the square has order , since does not
divide . If is prime, every element other than has order ,
so its powers are all of .
The divisibility goes in one direction only: divides , but the
cycle types of elements of are ;;;; and ,
so their orders are ,,,, and no element of has order .
Theorem 13.19 is a special case of a statement about
subgroups. If has order , then the powers form a
subgroup with elements, as we show in Section 13.9, so the
theorem says that the order of this subgroup divides .
If is a subgroup of a finite group , then divides .
We prove Lagrange’s theorem in
the next lecture note,
where it follows from the orbit–stabilizer theorem in the same way that
Theorem 13.19 followed from the cycles of . For
example, every subgroup of has order ,,, or , so no three
symmetries of the square form a group.
The rotation group consists of the powers of the single rotation ,
and every element of is obtained by adding to itself
repeatedly. Groups built from one element in this way are the simplest
groups, and the number of elements they contain turns out to be the order of
that element.
Let be an element of a finite group . The cyclic subgroup
generated by is the set
of all powers of , with positive, zero, and negative exponents.
The definition lists infinitely many powers, but in a finite group only
finitely many of them are different, and the order of tells us exactly how
many.
Proposition13.22(Order of an element and size of its cyclic subgroup)#
Let have order . Then
these powers are distinct, and is a subgroup of . In
particular, equals the order of .
Let be any integer, and divide by with remainder: with
. This works for negative as well; for example,
. Since divides ,Proposition 13.18 gives
, so . Thus every power of is one of
, and these are distinct by Proposition 13.18.
The set contains . The product of
two powers of is a power of , and so is the inverse of
. So is a subgroup.
In , the powers of are , so has
elements, matching the order of . The reflection has order ,
and .
In , the powers of are the remainders of
on division by . So and
, with and elements, the orders of and
. The multiples of give the remainders , so
. Different elements can generate
the same cyclic subgroup.
Proposition 13.22 turns Theorem 13.19 into
a statement about subgroups: the order of is the number of elements of the
subgroup , so once Lagrange’s theorem is proved, it gives a
second proof that the order of divides .
A group is cyclic if for some .
Such an element is called a generator of .
Since has as many elements as the order of , and
, a finite group equals
exactly when has order . So a finite group is cyclic exactly when it
contains an element whose order equals the order of the group, and its
generators are exactly the elements of that order.
The rotation group is cyclic, and so is
. By Example 13.23, the
generators of are and ; the elements ,,, and
have orders ,,, and , smaller than .
The group has elements, but its elements have orders ,, and
, so is not cyclic. There is also a reason that applies to every
. In a cyclic group, any two elements and commute, since
. In with we found , so
is not cyclic. For the same reason is not cyclic: following each element
from right to left gives but .
A group in which all elements commute need not be cyclic. The subgroup
of , consisting of the symmetries of the square that
also carry a non-square rectangle onto itself, is a subgroup. Using
,, and , we find , and
,; moreover commutes with every element of ,
because . So any two elements of this subgroup commute, but
every element has order or , and none has order ; the subgroup is
not cyclic.
The group is defined by addition, not by permutations, but it
behaves exactly like the rotation group : matching with , adding
residues corresponds to composing rotations. Two groups that match in this way
are considered the same.
By Proposition 13.22, has order and the powers
are the distinct elements of , so is
a bijection. For , the product in is
the remainder of on division by . As in the proof of
Proposition 13.22, , since divides
. Therefore .
For example, the rotation group is isomorphic to , and the
subgroup of is isomorphic to . A group of prime
order is cyclic: by Theorem 13.19, an element
has an order that divides and is not , so it has order and
. By Proposition 13.27, every group of prime
order is isomorphic to .
Every finite group is isomorphic to a permutation group. The permutations
come from the group itself: each element rearranges the elements of
by multiplication on the left.
Let be a finite group. For , define by
. Then each is a permutation of , the set
is a permutation group on , and
is an isomorphism from to . In particular, if
, then is isomorphic to a subgroup of .
By associativity,
, and similarly
. So undoes ,
and is a bijection.
Step 2: Products correspond to compositions.
For all ,, so
.
Step 3: Different elements give different permutations.
, so implies .
Step 4: Conclusion.
By Step 2, is closed under composition, so by
Proposition 13.16 it is a permutation group on . By Steps 2
and 3, is a bijection from to that turns
products into compositions, that is, an isomorphism. Numbering the elements
of as turns permutations of into elements of .
In , the element gives , which sends
; so . Similarly
and . Up to the names of the
four elements, these are the rotations ,, of the square.
Cayley’s theorem means that studying permutation groups loses no finite
groups. In the rest of this unit every group will be given as a group of
permutations.
Sort the black-and-white colorings of the corners of an equilateral
triangle into classes up to rotation. Using the relations of , write
in the form , and check the answer with tables.
Compute and in , and find the
conjugate of by . Find the order of
. List the elements of
and in , find all generators of
, and decide whether is cyclic.
