Forward to §3.1 | Back to §2.2 | Up | Table of Contents | About this document

**Definition 2.3.1.**
Let S be a set. A function
: S -> S is called a
**permutation**
of S if is one-to-one and onto.

The set of all permutations of S will be denoted by Sym(S).

The set of all permutations of the set { 1, 2, ..., n }
will be denoted by S_{n}.

Proposition 2.1.6
shows that the composition of two permutations
in Sym(S) is again a permutation.
It is obvious that the identity function on S is one-to-one and onto.
Proposition 2.1.8
shows that any permutation in Sym(S) has an
inverse function that is also one-to-one and onto.
We can summarize these important properties as follows:

**(i)**If , are elements of Sym(S), then is in Sym(S);**(ii)**1_{S}is in Sym(S);**(iii)**if is in Sym(S), then^{-1}is in Sym(S).

**Definition 2.3.2.**
Let S be a set, and let
be an element of Sym(S).
Then is called a
**cycle of length k**
if there exist elements a_{1},
a_{2}, ...,
a_{k} in S such that

(a_{1}) =
a_{2},
(a_{2}) =
a_{3}, . . . ,
(a_{k-1}) =
a_{k},
(a_{k}) = a_{1},
and

(x) = x for all
x a_{i}
(for i = 1, 2, ..., k).

We can also write
=
(a_{2},a_{3},...,a_{k},a_{1}) or
=
(a_{3},...,a_{k},a_{1},a_{2}),
etc. The notation for a cycle of length k
can thus be written in k different ways,
depending on the starting point.
The notation (1) is used for the identity permutation.

**Definition 2.3.3.**
Let =
(a_{1},a_{2},...,a_{k})
and =
(b_{1},b_{2},...,b_{m})
be cycles in Sym(S), for a set S.
Then
and are said to be
**disjoint**
if a_{i} b_{j}
for all i,j.

**Proposition 2.3.4.**
Let S be any set. If
and
are disjoint cycles in Sym(S), then

= .

**Theorem 2.3.5.**
Every permutation in S_{n}
can be written as a product of disjoint cycles.
The cycles that appear in the product are unique.

**Definition 2.3.6.**
Let
belong to S_{n}.
The least positive integer m such that
^{m} = (1) is called the
**order**
of .

**Proposition 2.3.7.**
Let
in S_{n} have order m. Then for all integers j,k we have

^{j} =
^{k}
if and only if
j k (mod m).

**Proposition 2.3.8.**
Let
in S_{n} be written as a product of disjoint cycles.
Then the order of
is the least common multiple of the lengths of its cycles.

**Definition 2.3.9.**
A cycle (a_{1},a_{2})
of length two is called a
**transposition**.

**Proposition 2.3.10.**
Any permutation in S_{n}, where
n 2,
can be written as a product of transpositions.

**Theorem 2.3.11.**
If a permutation is written as a product of transpositions in two ways,
then the number of transpositions is either even in both cases
or odd in both cases.

**Definition 2.3.12.**
A permutation
is called
**even**
if it can be written as a product of an even number of transpositions, and
**odd**
if it can be written as a product of an odd number of transpositions.

You need to do enough calculations so that you will feel comfortable in working with permutations. Certain sets of permutations provide the last major example that we need before we begin studying groups in Chapter 3. You will need the next definition to work some of the problems.

**Definition.**
If G is a nonempty subset of Sym (S),
we say that G is a **group of permutations** if
the following conditions hold:

**(i)**If , are elements of G, then is in G;**(ii)**1_{S}is in G;**(iii)**if is in G, then^{-1}is in G.

**13.**
For the permutation ,
write
as a product of disjoint cycles.
What is the order of ?
Is an even permutation?
Compute ^{ -1}.
*Solution*

**14.**
For the permutations
and
,
write each of these permutations as a product of disjoint cycles:

,
,
,
^{-1},
^{-1},
^{-1},
,
^{-1}.

**15.**
Let
= (2, 4, 9, 7,) (6, 4, 2, 5, 9) (1, 6) (3, 8, 6) in S_{9} .
Write
as a product of disjoint cycles.
What is the order of ?
Compute ^{-1}.
*Solution*

**16.**
Compute the order of
.
For = (3,8,7),
compute the order of
^{-1}.
*Solution*

**17.**
Prove that if in S_{n}
is a permutation with order m,
then
^{-1}
has order m, for any permutation
in
S_{n}.
*Solution*

**18.**
Show that S_{10} has elements of order
10, 12, and 14, but not 11 or 13.
*Solution*

**19.**
Let S be a set, and let X be a subset of S. Let

G = { in Sym(S) | (X) = X }.

Prove that G is a group of permutations.
**20.**
Let G be a group of permutations, with
G Sym (S),
for the set S. Let
be a fixed permutation in Sym(S). Prove that

G
^{-1}
= { in Sym(S) |
=
µ
^{-1}
for some µ in G }

Solutions to the problems | Forward to §3.1 | Back to §2.2 | Up | Table of Contents