396
Relations, Functions, and Matrices
Let A = 51, 2, 3, 46 and consider the cycle f [ S A given by f = (1, 2). If we
compute f + f = (1, 2) + (1, 2), we see that each element of A is mapped to itself.
The permutation that maps each element of A to itself is the identity function on
A, i A , also called the identity permutation.
If A is an infinite set, not every permutation of A can be written as a cycle. But
even when A is a finite set, not every permutation of A can be written as a cycle;
for example, the permutation g + f of Practice 36(b) cannot be written as a cycle.
However, every permutation on a finite set that is not the identity permutation can
be written as a composition of one or more disjoint cycles. The permutation
a
1 2 3 4 5
4 2 5 1 3
b
of Practice 36(b) is (1, 4) + (3, 5) or (3, 5) + (1, 4).
PRaCtiCe 36 Let A = 51, 2, 3, 4, 56. Compute g + f and f + g for the following cycles in S A .
a. f = (5, 2, 3); g = (3, 4, 1). Write the answers in cycle form.
b. f = (1, 2, 3, 4); g = (3, 2, 4, 5). Write the answers in array form.
c. f = (1, 3); g = (2, 5). Write the answers in array form.
■
PRaCtiCe 37 Write
a
1 2 3 4 5 6
2 4 5 1 3 6
b
as a composition of disjoint cycles.
■
Among the permutations of A, some will map certain elements of A to themselves, while others will so thoroughly mix elements around that no element in A
is mapped to itself. A permutation on a set that maps no element to itself is called
a derangement.
example 40
The permutation f on A = 51, 2, 3, 4, 56 given in array form by
a
1 2 3 4 5
2 5 4 1 3
b
is a derangement. Members of S A that are not derangements, if written as a cycle
or a product of cycles, will have at least one element of A that is not listed. Thus
g [ S A defined as g = (1, 4) + (3, 5) maps 2 to itself, so g is not a derangement.