Excerpted from Beachy/Blair, Abstract Algebra, 2nd Ed. © 1996

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


§ 2.3 Permutations

 
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 Sn.

 
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) 1S 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 a1, a2, ..., ak in S such that

(a1) = a2, (a2) = a3, . . . , (ak-1) = ak, (ak) = a1,     and

(x) = x     for all x ai     (for i = 1, 2, ..., k).

    In this case we write = (a1,a2,...,ak).

 
We can also write = (a2,a3,...,ak,a1) or = (a3,...,ak,a1,a2), 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 = (a1,a2,...,ak) and = (b1,b2,...,bm) be cycles in Sym(S), for a set S. Then and are said to be disjoint if ai bj 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 Sn 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 Sn. The least positive integer m such that m = (1) is called the order of .

 
Proposition 2.3.7. Let in Sn 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 Sn 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 (a1,a2) of length two is called a transposition.

 
Proposition 2.3.10. Any permutation in Sn, 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.



§ 2.3 Permutations: Solved problems

If you are reading another book along with Abstract Algebra, you need to be aware that some authors multiply permutations by reading from left to right, instead of the way we have defined multiplication. Our point of view is that permutations are functions, and we write functions on the left, just as in calculus, so we have to do the computations from right to left.

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) 1S is in G;

(iii) if is in G, then -1 is in G.
We will see later that this agrees with Definition 3.6.1 in the text.


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.

Solution

15. Let = (2, 4, 9, 7,) (6, 4, 2, 5, 9) (1, 6) (3, 8, 6) in S9 . 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 Sn is a permutation with order m, then -1 has order m, for any permutation in Sn.     Solution

18. Show that S10 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.     Solution

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 }

is a group of permutations.     Solution


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