*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

,
,
,
^{-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

*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

*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

*Solution:*
Assume that in S_{n}
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

*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 S_{10}.

Next problem | Next solution | Up | Table of Contents

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 1_{S} (x) = x for every element x in S

(1_{S} is the identity function on S)

it will certainly be true that
1_{S} (X) = X,
and so 1_{S} 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

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

*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 1_{S} in the form
1_{S}
=
1_{S}
^{-1},
it follows that 1_{S} 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

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^{-1}f ^{-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^{-1}B^{-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

In looking at (

(

You must write (

In this form, you can see that all of the terms

(

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