Permutation Groups
Suppose a set G is closed under an operation ∗. That is, suppose a ∗ b ∈ G
for all a, b ∈ G. Then ∗ is called a binary operation on G. We will use the
notation (G, ∗) to represent the set G with this operation. Suppose (G, ∗)
also satisfies the following three properties.
1. (a ∗ b) ∗ c = a ∗ (b ∗ c) for all a, b, c ∈ G.
2. There exists an identity element e ∈ G for which e ∗ a = a ∗ e = a for
all a ∈ G.
3. For each a ∈ G, there exists an inverse element b ∈ G for which
a ∗ b = b ∗ a = e. The inverse of a is usually denoted a−1 or −a.
Then (G, ∗) is called a group. For example, it can easily be verified that for
the set Z of integers, (Z,+) is a group with identity element 0.
c 1999 by CRC Press LLCLet S be a set, and let A(S) be the set of bijections on S. Then an
element α ∈ A(S) can be uniquely expressed by its action (s)α on the
elements s ∈ S.
Example 1.1 If S = {1, 2, 3}, then A(S) contains six elements. One of
the α in A(S) can be expressed as (1)α = 2, (2)α = 3, and (3)α =1.
Let ◦ represent the composition operation on A(S). Specifically, if
α, β ∈ A(S), then define α ◦ β by the action (s)(α ◦ β)=((s)α)β for s ∈ S.
Since the composition of two bijections on S is also a bijection on S, then
α ◦ β ∈ A(S). Hence, ◦ is a binary operation on A(S). It can easily be
verified that (A(S), ◦) is a group (see Written Exercise 1).
A group (G, ∗) is said to be abelian or commutative if a∗b = b∗a for all
a, b ∈ G. For example, since m+n = n+m for all m, n ∈ Z, then (Z,+) is
abelian. However, for a set S with more than two elements, α◦β = β ◦α for
some α, β ∈ A(S). Therefore, if a set S contains more than two elements,
then (A(S), ◦) is not abelian.
We will represent the number of elements in a set S by |S|. Suppose
S is a set with |S| = n. Then (A(S), ◦) is denoted by Sn and called the
symmetric group on n letters. It can easily be shown that |Sn| = n! (see
Written Exercise 2). Suppose α ∈ Sn. Then α can be viewed as a bijection
on the set {1, 2,...,n}. This bijection can be represented by listing the
elements in the set {1, 2,...,n} in a row with their images under α listed
immediately below.
α :
12 ··· n
(1)α (2)α ··· (n)α
Example 1.2 Let S = {1, 2, 3}, and let α ∈ S3 be given by (1)α =2,
(2)α = 3, and (3)α = 1. Then α can be represented as follows.
α :
123
231
An element α ∈ Sn is called a permutation. Note that for permutations
α, β ∈ Sn, we can represent α ◦ β as follows.
1 ··· n
(1)α ··· (n)α
1 ··· n
(1)β ··· (n)β
=
1 ··· n
(1α)β ··· (nα)β
For example, let α ∈ S4 be given by (1)α = 2, (2)α = 4, (3)α = 3, and
(4)α = 1, and let β ∈ S4 be given by (1)β = 4, (2)β = 3, (3)β = 2, and
c 1999 by CRC Press LLC(4)β = 1. Then we can express α ◦ β as follows.
1234
2431
1234
4321
=
1234
3124
We now discuss another way to express elements in Sn. Let i1,i2,...,is
be distinct elements in the set S = {1, 2,...,n}. Then (i1 i2 i3 ··· is−1 is)
is called a cycle of length s or an s-cycle, and represents the permutation
α ∈ Sn that maps i1 → i2, i2 → i3,...,is−1 → is, is → i1, and every other
element in S to itself. For example, the permutation
α :
123456
345162
in S6 can be expressed as the 6-cycle (135624). Note that this expression
of α as a cycle is not unique, for α can also be expressed as (356241) and
(562413), among others.
Next, consider the permutation
β :
123456
345612
in S6. To express β using cycle notation, we must use more than one cycle.
For example, we can express β as the following “product” of two 3-cycles:
(135)(246). Since these cycles contain no elements in common they are
said to be disjoint. And because they are disjoint, the order in which they
are listed does not matter. The permutation β can also be expressed as
(246)(135).
Every permutation in Sn can be expressed as either a single cycle or a
product of disjoint cycles. When a permutation is expressed as a product of
disjoint cycles, cycles of length one are not usually included. For example,
consider the permutation
γ :
123456
345216
in S6. Even though the fact that γ maps 6 to itself would be expressed as
the 1-cycle (6), this cycle would not usually be included in the expression
of γ as a product of disjoint cycles. That is, γ would usually be expressed
as (135)(24) or (24)(135).
In an expression of a permutation as a product of cycles, the cycles
need not be disjoint. For example, the permutation α = (135624) defined
above can also be expressed as the product (13)(15)(16)(12)(14) of 2-cycles.
c 1999 by CRC Press LLCBecause these 2-cycles are not disjoint, the order in which they are listed
matters.
A 2-cycle is also called a transposition. Any permutation can be ex-
pressed as a product of transpositions in the way illustrated above for α.
Specifically, the cycle (i1 i2 i3 ··· is−1 is) can be expressed as the product
(i1 i2)(i1 i3) ··· (i1 is−1)(i1 is) of transpositions. If a permutation can be
expressed as a product of more than one disjoint cycle, then each cycle can
be considered separately when expressing the permutation as a product of
transpositions. For example, the permutation β = (135)(246) defined above
can be expressed as (13)(15)(24)(26), and the permutation γ = (135)(24)
defined above can be expressed as (13)(15)(24).
There are many ways to express a permutation as a product of trans-
positions, and the number of transpositions in these expressions may vary.
However, the number of transpositions in the expression of a permutation
as a product of transpositions is either always even or always odd. A per-
mutation is said to be even if it can be expressed as a product of an even
number of transpositions, and odd if it can be expressed as a product of an
odd number of transpositions. Thus, the product of two even permutations
is even, and the product of two odd permutations is also even.
The inverse of the cycle (i1 i2 i3 ··· is−1 is)is(is is−1 ··· i3 i2 i1).
Suppose α = α1α2 ··· αk ∈ Sn, where each αi is a transposition. Then
α−1 = α−1
k ··· α−1
2 α−1
1 = αk ··· α2α1 since α−1
i = αi for each transposition
αi. Hence, the inverse of an even permutation is even. And because the
identity permutation is even, the subset of even permutations in Sn forms a
group. This group is denoted by An and called the alternating group on n
letters. Since An is a subset of Sn and forms a group, we call An a subgroup
of Sn.
Definition 1.1 Let (G, ∗) be a group, and suppose H is a nonempty subset
of G.If (H, ∗) is a group, then H is called a subgroup of G.
Consider a regular polygon P, such as, for example, an equilateral
triangle or a square. Any movement of P that preserves the general shape of
P is called a rigid motion. There are two types of rigid motions – rotations
and reflections. For a regular polygon P with n sides, there are 2n distinct
rigid motions. These include the n rotations of P through 360j/n degrees
for j =1,...,n. The remaining n rigid motions are reflections. If n is even,
these are the reflections of P across the lines that connect opposite vertices
or bisect opposite sides of P.If n is odd, these are the reflections of P
across the lines that are perpendicular bisectors of the sides of P. Since
the rigid motions of P preserve the general shape of P, they can be viewed
c 1999 by CRC Press LLCas permutations of the vertices or sides of P. The set of rigid motions of a
regular polygon P forms a group called the symmetries of P.
Example 1.3 Consider the group of symmetries of a square. To express
these symmetries as permutations of the vertices of a square, consider the
following general figure.
1
2
4
3
The 8 symmetries of a square can be expressed as permutations of the
vertices of this general figure as follows (rotations are counterclockwise).
Rigid Motion Permutation
90◦ rotation (1234)
180◦ rotation (13)(24)
270◦ rotation (1432)
360◦ rotation identity
reflection across horizontal (12)(34)
reflection across vertical (14)(23)
reflection across 1–3 diagonal (24)
reflection across 2–4 diagonal (13)
Note that expressing these rigid motions as permutations on the vertices of
the preceding general figure yields a subgroup of S4.
When the symmetries of an n-sided regular polygon are expressed as
permutations on the set {1, 2,...,n}, the resulting subgroup of Sn is de-
noted by Dn and called the dihedral group on n letters. The subgroup of
S4 in Example 1.3 is the dihedral group D4.
A group (G, ·), or just G for short, is called cyclic if there is an element
a ∈ G for which G = {ai
| i ∈ Z}. In this case, a is called a cyclic generator
for G. More generally, suppose a is an element in a group G, and let
H = {ai
| i ∈ Z}. Then H is a subgroup of G called the cyclic group
generated by a. Let ai
= aj
for some 0
a−i
= e,
where e is the identity element in G. Thus, there is a smallest positive
integer m for which am = e. Now, suppose at
= e. Since t = mq + r
for some 0 ≤ r
r = 0. Hence, m divides t. Since ai
= aj
for i
contradiction if 0
for some 0 ≤ r
theorem.
Theorem 1.2 Suppose a is an element in a group G.If m is the smallest
positive integer for which am = e, where e is the identity element in G,
then the cyclic group generated by a contains m elements.
The value of m in Theorem 1.2 is called the order of a. Also, a set
S with |S| = n is said to have order n. Hence, the order of an element a
in a group G is the order of the cyclic subgroup of G generated by a.We
will show in Theorem 1.4 that for an element of order m in a group G of
order n, m must divide n. Therefore, in a group G of order n, an = e for
all a ∈ G where e is the identity element in G. We summarize this as the
following corollary.
Corollary 1.3 Suppose a is an element in a group G of order n. Then
an = e where e is the identity element in G.
Example 1.4 Consider the dihedral group Dn of order 2n. Recall that
the elements in Dn can be viewed as the symmetries of an n-sided regular
polygon P. Each of the n reflections of P has order 2. Also, the rotations
of P through 360/n and 360(n−1)/n degrees have order n (as do, possibly,
some other rotations). Note that these orders divide |Dn|.
1.2 Cosets and Quotient Group
Suppose a set G is closed under an operation ∗. That is, suppose a ∗ b ∈ G
for all a, b ∈ G. Then ∗ is called a binary operation on G. We will use the
notation (G, ∗) to represent the set G with this operation. Suppose (G, ∗)
also satisfies the following three properties.
1. (a ∗ b) ∗ c = a ∗ (b ∗ c) for all a, b, c ∈ G.
2. There exists an identity element e ∈ G for which e ∗ a = a ∗ e = a for
all a ∈ G.
3. For each a ∈ G, there exists an inverse element b ∈ G for which
a ∗ b = b ∗ a = e. The inverse of a is usually denoted a−1 or −a.
Then (G, ∗) is called a group. For example, it can easily be verified that for
the set Z of integers, (Z,+) is a group with identity element 0.
c 1999 by CRC Press LLCLet S be a set, and let A(S) be the set of bijections on S. Then an
element α ∈ A(S) can be uniquely expressed by its action (s)α on the
elements s ∈ S.
Example 1.1 If S = {1, 2, 3}, then A(S) contains six elements. One of
the α in A(S) can be expressed as (1)α = 2, (2)α = 3, and (3)α =1.
Let ◦ represent the composition operation on A(S). Specifically, if
α, β ∈ A(S), then define α ◦ β by the action (s)(α ◦ β)=((s)α)β for s ∈ S.
Since the composition of two bijections on S is also a bijection on S, then
α ◦ β ∈ A(S). Hence, ◦ is a binary operation on A(S). It can easily be
verified that (A(S), ◦) is a group (see Written Exercise 1).
A group (G, ∗) is said to be abelian or commutative if a∗b = b∗a for all
a, b ∈ G. For example, since m+n = n+m for all m, n ∈ Z, then (Z,+) is
abelian. However, for a set S with more than two elements, α◦β = β ◦α for
some α, β ∈ A(S). Therefore, if a set S contains more than two elements,
then (A(S), ◦) is not abelian.
We will represent the number of elements in a set S by |S|. Suppose
S is a set with |S| = n. Then (A(S), ◦) is denoted by Sn and called the
symmetric group on n letters. It can easily be shown that |Sn| = n! (see
Written Exercise 2). Suppose α ∈ Sn. Then α can be viewed as a bijection
on the set {1, 2,...,n}. This bijection can be represented by listing the
elements in the set {1, 2,...,n} in a row with their images under α listed
immediately below.
α :
12 ··· n
(1)α (2)α ··· (n)α
Example 1.2 Let S = {1, 2, 3}, and let α ∈ S3 be given by (1)α =2,
(2)α = 3, and (3)α = 1. Then α can be represented as follows.
α :
123
231
An element α ∈ Sn is called a permutation. Note that for permutations
α, β ∈ Sn, we can represent α ◦ β as follows.
1 ··· n
(1)α ··· (n)α
1 ··· n
(1)β ··· (n)β
=
1 ··· n
(1α)β ··· (nα)β
For example, let α ∈ S4 be given by (1)α = 2, (2)α = 4, (3)α = 3, and
(4)α = 1, and let β ∈ S4 be given by (1)β = 4, (2)β = 3, (3)β = 2, and
c 1999 by CRC Press LLC(4)β = 1. Then we can express α ◦ β as follows.
1234
2431
1234
4321
=
1234
3124
We now discuss another way to express elements in Sn. Let i1,i2,...,is
be distinct elements in the set S = {1, 2,...,n}. Then (i1 i2 i3 ··· is−1 is)
is called a cycle of length s or an s-cycle, and represents the permutation
α ∈ Sn that maps i1 → i2, i2 → i3,...,is−1 → is, is → i1, and every other
element in S to itself. For example, the permutation
α :
123456
345162
in S6 can be expressed as the 6-cycle (135624). Note that this expression
of α as a cycle is not unique, for α can also be expressed as (356241) and
(562413), among others.
Next, consider the permutation
β :
123456
345612
in S6. To express β using cycle notation, we must use more than one cycle.
For example, we can express β as the following “product” of two 3-cycles:
(135)(246). Since these cycles contain no elements in common they are
said to be disjoint. And because they are disjoint, the order in which they
are listed does not matter. The permutation β can also be expressed as
(246)(135).
Every permutation in Sn can be expressed as either a single cycle or a
product of disjoint cycles. When a permutation is expressed as a product of
disjoint cycles, cycles of length one are not usually included. For example,
consider the permutation
γ :
123456
345216
in S6. Even though the fact that γ maps 6 to itself would be expressed as
the 1-cycle (6), this cycle would not usually be included in the expression
of γ as a product of disjoint cycles. That is, γ would usually be expressed
as (135)(24) or (24)(135).
In an expression of a permutation as a product of cycles, the cycles
need not be disjoint. For example, the permutation α = (135624) defined
above can also be expressed as the product (13)(15)(16)(12)(14) of 2-cycles.
c 1999 by CRC Press LLCBecause these 2-cycles are not disjoint, the order in which they are listed
matters.
A 2-cycle is also called a transposition. Any permutation can be ex-
pressed as a product of transpositions in the way illustrated above for α.
Specifically, the cycle (i1 i2 i3 ··· is−1 is) can be expressed as the product
(i1 i2)(i1 i3) ··· (i1 is−1)(i1 is) of transpositions. If a permutation can be
expressed as a product of more than one disjoint cycle, then each cycle can
be considered separately when expressing the permutation as a product of
transpositions. For example, the permutation β = (135)(246) defined above
can be expressed as (13)(15)(24)(26), and the permutation γ = (135)(24)
defined above can be expressed as (13)(15)(24).
There are many ways to express a permutation as a product of trans-
positions, and the number of transpositions in these expressions may vary.
However, the number of transpositions in the expression of a permutation
as a product of transpositions is either always even or always odd. A per-
mutation is said to be even if it can be expressed as a product of an even
number of transpositions, and odd if it can be expressed as a product of an
odd number of transpositions. Thus, the product of two even permutations
is even, and the product of two odd permutations is also even.
The inverse of the cycle (i1 i2 i3 ··· is−1 is)is(is is−1 ··· i3 i2 i1).
Suppose α = α1α2 ··· αk ∈ Sn, where each αi is a transposition. Then
α−1 = α−1
k ··· α−1
2 α−1
1 = αk ··· α2α1 since α−1
i = αi for each transposition
αi. Hence, the inverse of an even permutation is even. And because the
identity permutation is even, the subset of even permutations in Sn forms a
group. This group is denoted by An and called the alternating group on n
letters. Since An is a subset of Sn and forms a group, we call An a subgroup
of Sn.
Definition 1.1 Let (G, ∗) be a group, and suppose H is a nonempty subset
of G.If (H, ∗) is a group, then H is called a subgroup of G.
Consider a regular polygon P, such as, for example, an equilateral
triangle or a square. Any movement of P that preserves the general shape of
P is called a rigid motion. There are two types of rigid motions – rotations
and reflections. For a regular polygon P with n sides, there are 2n distinct
rigid motions. These include the n rotations of P through 360j/n degrees
for j =1,...,n. The remaining n rigid motions are reflections. If n is even,
these are the reflections of P across the lines that connect opposite vertices
or bisect opposite sides of P.If n is odd, these are the reflections of P
across the lines that are perpendicular bisectors of the sides of P. Since
the rigid motions of P preserve the general shape of P, they can be viewed
c 1999 by CRC Press LLCas permutations of the vertices or sides of P. The set of rigid motions of a
regular polygon P forms a group called the symmetries of P.
Example 1.3 Consider the group of symmetries of a square. To express
these symmetries as permutations of the vertices of a square, consider the
following general figure.
1
2
4
3
The 8 symmetries of a square can be expressed as permutations of the
vertices of this general figure as follows (rotations are counterclockwise).
Rigid Motion Permutation
90◦ rotation (1234)
180◦ rotation (13)(24)
270◦ rotation (1432)
360◦ rotation identity
reflection across horizontal (12)(34)
reflection across vertical (14)(23)
reflection across 1–3 diagonal (24)
reflection across 2–4 diagonal (13)
Note that expressing these rigid motions as permutations on the vertices of
the preceding general figure yields a subgroup of S4.
When the symmetries of an n-sided regular polygon are expressed as
permutations on the set {1, 2,...,n}, the resulting subgroup of Sn is de-
noted by Dn and called the dihedral group on n letters. The subgroup of
S4 in Example 1.3 is the dihedral group D4.
A group (G, ·), or just G for short, is called cyclic if there is an element
a ∈ G for which G = {ai
| i ∈ Z}. In this case, a is called a cyclic generator
for G. More generally, suppose a is an element in a group G, and let
H = {ai
| i ∈ Z}. Then H is a subgroup of G called the cyclic group
generated by a. Let ai
= aj
for some 0
a−i
= e,
where e is the identity element in G. Thus, there is a smallest positive
integer m for which am = e. Now, suppose at
= e. Since t = mq + r
for some 0 ≤ r
r = 0. Hence, m divides t. Since ai
= aj
for i
contradiction if 0
for some 0 ≤ r
theorem.
Theorem 1.2 Suppose a is an element in a group G.If m is the smallest
positive integer for which am = e, where e is the identity element in G,
then the cyclic group generated by a contains m elements.
The value of m in Theorem 1.2 is called the order of a. Also, a set
S with |S| = n is said to have order n. Hence, the order of an element a
in a group G is the order of the cyclic subgroup of G generated by a.We
will show in Theorem 1.4 that for an element of order m in a group G of
order n, m must divide n. Therefore, in a group G of order n, an = e for
all a ∈ G where e is the identity element in G. We summarize this as the
following corollary.
Corollary 1.3 Suppose a is an element in a group G of order n. Then
an = e where e is the identity element in G.
Example 1.4 Consider the dihedral group Dn of order 2n. Recall that
the elements in Dn can be viewed as the symmetries of an n-sided regular
polygon P. Each of the n reflections of P has order 2. Also, the rotations
of P through 360/n and 360(n−1)/n degrees have order n (as do, possibly,
some other rotations). Note that these orders divide |Dn|.
1.2 Cosets and Quotient Group
EmoticonEmoticon