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

§ 2.3 Permutations: Solved problems

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

Solution: We have = (1,7,8)(2,5)(3,6,4,9), and so its order is 12 since lcm[3,2,4] = 12. It is an even permutation, since it can be expressed as the product of 6 transpositions. We have
-1 = (1,8,7)(2,5)(3,9,4,6), since we can just invert the individual cycles.

Do you need more details?.

Next problem | Next solution | Up | Table of Contents
14. For the permutations and , write each of these permutations as a product of disjoint cycles:

,   ,   ,   -1,   -1,   -1,   ,   -1.

Solution: Remember to calculate the products from right to left, treating them as composition of functions.
= (1,2,5,3)(4,8,7);
-1 = (1,3,5,2)(4,7,8);
= (2,5)(3,4,7,8,9);
-1 = (2,5)(3,9,8,7,4) ;
= (1,2,5,3)(4,8,7) · (2,5)(3,4,7,8,9) = (1,2,3,8,9) ;
-1 = ( ) -1 = (1,2,3,8,9) · (1,3,5,2)(4,7,8) = (1,8,4,7,9)(3,5);
= (2,5)(3,4,7,8,9) · (1,2,5,3)(4,8,7) = (1,5,4,9,3);
-1 = ( ) -1 = (1,5,4,9,3) · (2,5)(3,9,8,7,4) = (1,5,2,4)(7,9,8).

Next problem | Next solution | Up | Table of Contents
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: We have = (1,9,6,3,8)(2,5,7), so it has order 15 = lcm[5,3], and
-1 = (1,8,3,6,9)(2,7,5).
See the detailed solution of Problem 13 if you need help with the computations.

Next problem | Next solution | Up | Table of Contents
16. Compute the order of . For = (3,8,7), compute the order of -1.

Solution: Since = (1,7,9)(3,11,5,6,8,10), it has order 6. We have -1 = (3,8,7)(1,7,9)(3,11,5,6,8,10)(3,7,8) = (1,3,9)(8,11,5,6,7,10), so the cycle structure of -1 is the same as that of , and thus -1 has order 6.

Next problem | Next solution | Up | Table of Contents
17. Prove that if in Sn is a permutation with order m, then -1 has order m, for any permutation in Sn.

Solution: Assume that in Sn has order m. It follows from the identity
( -1)k = k -1 (click here for more detail) that
( -1)m = m -1 = (1) -1 = (1). On the other hand, the order of
-1 cannot be less than n, since ( -1)k = (1) implies that
k -1 = (1), and then k = -1 = (1).

Next problem | Next solution | Up | Table of Contents
18. Show that S10 has elements of order 10, 12, and 14, but not 11 or 13.

Solution: The permutation (1,2)(3,4,5,6,7) has order 10, while the element (1,2,3)(4,5,6,7) has order 12, and (1,2)(3,4,5,6,7,8,9) has order 14. On the other hand, since 11 and 13 are prime, any element of order 11 or 13 would have to be a cycle, and there are no cycles of that length in S10.

Next problem | Next solution | Up | Table of Contents
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: Using the definition of a group of permutations, we must prove that the following conditions hold:
    (i) if and belong to G, then also belongs to G;
    (ii) the identity function belongs to G; and
    (iii) if belongs to G, then -1 also belongs to G.
Each of the properties we have to check depends on the requirement that is used to define G. Let's check the conditions one-by-one.

Proof of (i) : Suppose that we are given two permutations and that belong to G.
Then because of the way G is defined, we know that
(X) = X and (X) = X. To show that also belongs to G, we must show that
(X) = X. Here are the necessary computations:

(X) = ( (X)), using the definition of composition of functions;
( (X)) = (X) by substitution, because (X) = X;
(X) = X, since belongs to G.

Combining these steps we, we can give the computation on one line:
(X) = ( (X)) = (X) = X.

Proof of (ii) : Since 1S (x) = x for every element x in S
(1S is the identity function on S)
it will certainly be true that 1S (X) = X, and so 1S belongs to G.

Proof of (iii) : Suppose that we are given a permutations that belongs to G.
Because of the definition of G, this allows us to say that
(X) = X. We also know that has an inverse, because it is a permutation.
If we apply the function -1 to both sides of the equation (X) = X, we get
-1 ( (X)) = -1 (X),   or   -1 (X), = -1 (X) = X , since -1 is the identity function.
This shows that -1 belongs to G, and completes the proof that G is a group of permutations.

Next problem | Next solution | Up | Table of Contents
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: To simplify the notation, let G -1 = H.

First, suppose that 1 and 2 belong to H. Then
1 = µ1 -1 and 2 = µ2 -1 for some µ1 and µ2 in G, so
1 2 = ( µ1 -1) ( µ2 -1) = (µ1 µ2) -1 .
It follows that 1 2 belongs to H, since µ1 µ2 belongs to G.

Since we can write the identity 1S in the form 1S = 1S -1, it follows that 1S belongs to H.

Finally, suppose that belongs to H. Then = µ -1 for some µ in G, and
-1 = ( µ -1)-1 = (-1)-1 µ-1 -1, since we must reverse the order when taking inverses. Thus
-1 = µ-1 -1, and so -1 belongs to H since µ-1 belongs to G.

Forward to Chapter 2 review | Forward to Chapter 2 review solutions | Back to §2.2 problems | Up | Table of Contents
Detailed solution for Problem 13. To show that = (1,7,8)(2,5)(3,6,4,9), we need to write as a product of disjoint cycles. The algorithm for doing this is given in the text, in the proof of Theorem 2.3.5.

Since , we see that maps 1 to 7, that it maps 7 to 8, and that it maps 8 back to 1. It makes sense (in everyday language) that this would be called a ``cycle'' determined by . The notation (1,7,8) shows what is happening (remember that it folds back on itself at the end, so that 8 goes back to 1).

To get the first cycle, we began with 1. To get the next cycle, we start with the smallest number we haven't used, which is 2. We see that maps 2 to 5, and then it maps 5 right back to 2. The second cycle is (2,5), which is just a transposition.

Since we have used 1 and 2 already, but not 3, we begin the next cycle with 3. We see that maps 3 to 6, then it maps 6 to 4, then 4 goes to 9, and finally 9 is mapped back to 3. This produces the third cycle (3,6,4,9).

In writing down the final answer, the order in which we write the individual cycles does not matter, since Proposition 2.3.4 shows that disjoint cycles commute.

Once we know that = (1,7,8)(2,5)(3,6,4,9), it follows from Proposition 2.3.4 that
k = ((1,7,8)(2,5)(3,6,4,9))k = (1,7,8)k(2,5)k(3,6,4,9)k, for any positive power k.
To find the order of , we need to find the smallest positive k for which k is the identity.
Every third power of (1,7,8) is the identity,
every even power of (2.5) is the identity,
and every fourth power of (3,6,4,9) is the identity.
This tells us that the order of must be the least common multiple of these three numbers
(we have to get the identity at the same time for each of the three cycles)
and so the order of is lcm[3,2,4] = 12.

To decide whether is an even permutation or an odd permutation, we need to express it as a product of transpositions. The algorithm for doing this is given in the text in the proof of Proposition 2.3.10. You can check that (1,7,8) = (7,8)(1,8). You may find it easier to remember that you can also write (1,7,8) = (1,7)(7,8). Using the second form, we can write (3,6,4,9) = (3,6)(6,4)(4,9). This finally gives us
= (1,7,8)(2,5)(3,6,4,9) = (1,7)(7,8)(2,5)(3,6)(6,4)(4,9),
so is an even permutation because it can be written as the product of 6 transpositions.
Shortcuts : the number of transpositions is equal to the number of commas in the expresson (1,7,8)(2,5)(3,6,4,9), so you could just check to see if the number of commas is even or odd.
You could also say that (2,5) and (3,6,4,9) are odd permutations, so their product must be even. (This always works, because the sum of two odd integers is even.) Then you have the produce of two even permutations, (1,7,8) and (2,5)(3,6,4,9), so is an even permutation because it can be expressed as the product of two even permutations. (Again, the product of two even permutations is always even because the sum of two even integers is even.)

To find the inverse of , we should use the information we already have, in terms of its cycles. We have (1,7,8)-1 = (8,7,1), by just reversing the order in the cycle. Of course, this is usually written in the standard form (1,7,8)-1 = (1,8,7). Obviously (2,5)-1 = (5,2) = (2,5), and then for the third cycle we have (3,6,4,9)-1 = (9,4,6,3) = (3,9,4,6). How can we put these together to get -1?
The general rule for the composition of functions is that if the functions f and g have inverses, and their product fg is defined, then (fg)-1 is equal to g-1f -1. (See Exercise 2.1.13 in the text.) You should remember that this is the same rule that applies to invertible n × n matrices: (AB)-1 = A-1B-1.
Fortunately, in the way we have written , we have used disjoint cycles, so they commute with each other, and the order in which we write them does not matter. That justifies simply inverting the individual cycles in the expression
= (1,7,8)(2,5)(3,6,4,9), to get the inverse -1 = (1,8,7)(2,5)(3,9,4,6).

Back to the solution of Problem 13 | Next problem | Next solution | Up | Table of Contents
Details for Problem 17.
In looking at ( -1)k, remember that you cannot just write
( -1)k = k k -k, because you do not know that and commute.
You must write ( -1)k = ( -1) ( -1) · · · ( -1) .
In this form, you can see that all of the terms -1 will cancel, leaving
( -1)k = k -1 .

We now give a more careful proof of the identity, using mathematical induction.
For the case k=2 we have
( -1)2 = ( -1) ( -1) = (-1 ) -1 = -1 = 2 -1 .
Note that in this calculation we used the fact that composition of functions obeys the associative law.
Next, given that the identity holds for k, we can prove it for k+1 as follows:
( -1)k+1 = ( -1)k ( -1) = ( k -1) ( -1)
      = k (-1 ) -1 = k -1 = k+1 -1.
By induction, the identity therefore holds for all positive integers k.

Back to the solution of Problem 17 | Next problem | Next solution | Up | Table of Contents