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 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₁, a₂, ..., a_k in S such that

(a₁) = a₂, (a₂) = a₃, . . . , (a_k-1) = a_k, (a_k) = a₁,     and

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

 
We can also write = (a₂,a₃,...,a_k,a₁) or = (a₃,...,a_k,a₁,a₂), 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₁,a₂,...,a_k) and = (b₁,b₂,...,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₁,a₂) 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.

§ 2.3 Permutations: Solved problems

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₉ . 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₁₀ 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 }.

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