📚 The CoCalc Library - books, templates and other resources

cocalc-examples / paulsen-abstract-algebra / group05.ipynb

¹³²⁹²² views
License: OTHER

Kernel: SageMath (stable)

Abstract Algebra: An Interactive Approach, 2e

Chapter 5
Permutation Groups

Initialization: This cell MUST be evaluated first:

In [0]:

%display latex
try:
    load('absalgtext.sage')
except IOError:
    load('/media/sf_sage/absalgtext.sage')

Symmetric Groups
Cycles
Cayley's Theorem
Numbering the Permutations
Sage Interactive Problems

Symmetric Groups

In this chapter we will explore one class of finite groups that has important applications. These groups are called the permutation groups, or symmetric groups. We have already seen S₃, the permutation group on 3 objects.

Recall that we used 3 different colored books to illustrate this group. We can easily generalize this to consider the group of all permutations of n objects. For example, with four books the beginning position would be

In [0]:

InitBooks(4)

We have seen several ways of rearranging the books. We can swap the first two books with the command

In [0]:

MoveBooks(First)

We can also swap the last two books:

In [0]:

MoveBooks(Last)

We can move the first book to the end, sliding the other books to the left.

In [0]:

MoveBooks(Left)

The opposite of the proceedure is to move the last book to the beginning.

In [0]:

MoveBooks(Right)

We can also reverse the order of the books.

In [0]:

MoveBooks(Rev)

Finally, we can leave the books alone.

In [0]:

MoveBooks(Stay)

For three books, any permutation can be obtained by just one of these six commands. But it is apparent that with four books, there are even more ways to rearrange the books. One possible operation would be to move the left-most book two positions to the right. This can be accomplished by the sequence

In [0]:

MoveBooks(Left, Last)

EXPERIMENT:
Using just the six commands mentioned above, put the books back into their original positions (Red, Red, Purple, Orange). Try doing this using the fewest number of commands.

This experment shows that it can be somewhat tricky to represent any permutation order using only a few commands. The more books there are, the more of a puzzle this can be. Let us introduce a notation for a permutation of books that explicitly states where each book ends up.

One natural way to do this is to number the books in consecutive order, and determine the numbers in the final position. For example, if we put the books in their original order,

In [0]:

InitBooks(4)

and then shift the books to the left,

In [0]:

MoveBooks(Left)

we find that if the books started in 1, 2, 3, 4 order, the final position will be 2, 3, 4, 1. Here, book 1 is red, book 2 is green, book 3 is purple, and book 4 is orange. Since the final position of the books (green, purple, orange, red) translates to 2, 3, 4, 1. We write the ending position below the starting position, as follows.

⎛	1	2	3	4	⎞
⎝	2	3	4	1	⎠

We can now multiply the permutations by first performing one action, and then the other. For example, doing the opperation Left, followed by Last, leaves us with the books in the order

green purple red orange

which, when compared to the original position, translates to 2, 3, 1, 4, giving the permutation

⎛	1	2	3	4	⎞
⎝	2	3	1	4	⎠

We write the Left·Last as a product of two permutations

⎛	1	2	3	4	⎞	·	⎛	1	2	3	4	⎞	=	⎛	1	2	3	4	⎞
⎝	2	3	4	1	⎠	·	⎝	1	2	4	3	⎠	=	⎝	2	3	1	4	⎠

If we did these operations in the other order, we would get

⎛	1	2	3	4	⎞	·	⎛	1	2	3	4	⎞	=	⎛	1	2	3	4	⎞
⎝	1	2	4	3	⎠	·	⎝	2	3	4	1	⎠	=	⎝	2	4	3	1	⎠

Obviously, Left · Last does not equal Last · Left.

We can also view a permutation as a function whose domain is a subset of the integers. Consider the functions ƒ(x) and ϕ(x) given by the table

ƒ(1) = 2	ϕ(1) = 2
ƒ(2) = 3	ϕ(2) = 3
ƒ(3) = 1	ϕ(3) = 4
ƒ(4) = 4	ϕ(4) = 1.

We could denote these two functions by the same type of notation, as follows:

ƒ(x) =	⎛	1	2	3	4	⎞	ϕ(x) =	⎛	1	2	3	4	⎞
ƒ(x) =	⎝	2	3	1	4	⎠	ϕ(x) =	⎝	2	3	4	1	⎠

Notice that each column shows the value of ƒ(x) or ϕ(x) directly beneath x. Since the range and domain of these functions are the same, we can consider the composition of the two functions. Let us consider ƒ·ϕ:

ƒ(ϕ(1)) = ƒ(2) = 3
ƒ(ϕ(2)) = ƒ(3) = 1
ƒ(ϕ(3)) = ƒ(4) = 4
ƒ(ϕ(4)) = ƒ(1) = 2

So the composition function ƒ(ϕ(x)), that is, of doing ϕ first, and then ƒ, can be written as

⎛	1	2	3	4	⎞
⎝	3	1	4	2	⎠

We can write this permutation as ƒ·ϕ, so we have that

ƒ(ϕ(x)) = (ƒ·ϕ)(x).

There is something curious here. When we view permutations as ways to rearrange a set of objects, such as books, the permutations are multiplied from left to right, which is the natural order. But when we view permutations as functions, the permutations are multiplied from right to left, which is again the natural order for function composition.

DEFINITION 5.1
For the set {1, 2, 3, … n}, we define the group of permutations on the set by S_n. That is, S_n is the set of functions which are one-to-one and onto on the set {1, 2, 3, … n}. The group operation is function composition.

EXPERIMENT:
Consider the following product:

⎛	1	2	3	4	5	⎞	·	⎛	1	2	3	4	5	⎞
⎝	5	4	1	2	3	⎠	·	⎝	4	3	5	1	2	⎠

First work this product by viewing the permutations as two ways to rearrange 5 books. If you work the rearrangements from left to right, what is the resulting rearrangement of the books? Now work this product by viewing the permutations as functions, working from right to left. Do you get the same answer? Which of the two methods was easier? If you work the problem viewing the permutations as functions, and worked from left to right, would you get the right answer?

Sage can easily work with permutations. The top line of the permutation is only for convenience since the bottom line contains all of the information about the permutation. Thus, we can write these permutations like this:

P(5,4,1,2,3) · P(4,3,5,1,2).

In general, a permutation in S_n can be written

P(x₁, x₂, x₃, … x_n).

Note that the numbers x₁, x₂, x₃, … x_n must all be different and must consist of the numbers from 1 to n. This permutation corresponds to the function

ƒ(1) = x₁
ƒ(2) = x₂
ƒ(3) = x₃
………
ƒ(n) = x_n.

This notation is a little more difficult since one must count four numbers to determine ƒ(4). Yet Sage prefers this notation for its conciseness. Let's try using Sage to check the above product:

In [0]:

P(5,4,1,2,3)*P(4,3,5,1,2)

Is this the answer you got? We do not have to define this group the way we have been defining the other groups in these notebooks. The symmetric group is pre-loaded in the initialization. Let us determine the product of these two permutations multiplied in the other order:

In [0]:

P(4,3,5,1,2)*P(5,4,1,2,3)

What happened to the 5? Since the composition function maps 5 to itself, Sage can safety drop the 5, treating this as a permutation on four objects instead. To save space Sage displays only up to the last number which is out of position. All of the necessary information is still in the permutation.

Since all permutations in S₄ can be expressed in terms of some combinations of the Left and Last book rearrangements, we can find all of the elements of S₄.

In [0]:

S4 = Group(P(2, 3, 4, 1), P(1, 2, 4, 3)); S4

In [0]:

len(S4)

Note that the identity element of S₄ is denoted by P(), since the corresponding function leaves all objects fixed. We can determine the size of the group S_n in general, by counting the number of one-to-one and onto functions from the set {1, 2, 3, … n} to itself. We have n choices for f(1), but then there will be only n − 1 choices for f(2), n − 2 choices for f(3), and so on. Thus, the size of the group S_n is given by

n! = n·(n − 1)·(n − 2)·(n − 3)·… · 2·1

The number n! is read "n factorial," and represents the product of the first n numbers. Here is a short table of n!:

1!	=	1
2!	=	2
3!	=	6
4!	=	24
5!	=	120
6!	=	720
7!	=	5040
8!	=	40320
9!	=	362880
10!	=	3628800

From this table we see that 4! = 24, so this verifies that S₄ has 24 elements. One can see that the size of S_n grows very quickly. S₁ has only one element, so it is the trivial group. S₂ has two elements, so this must be isomorphic to Z₂. We have already seen S₃ was isomorphic to Terry's group. Now we find that S₄ has 24 elements. Since the octahedral group also has 24 elements, so we could ask if these two groups are isomorphic. The octahedral group can be reloaded by the commands

In [0]:

InitGroup("e")
AddGroupVar("a", "b", "c")
Define(a^2, e)
Define(b^3, e)
Define(c^4, e)
Define(b*a, a*b^2)
Define(c*a, a*b*c)
Define(c*b, a*c^2)
Oct = ListGroup();Oct

Let us try to find an isomorphism. We discovered that there is a copy of S₃ inside of the octahedral group, generated by the elements a and b. Let us begin there. In S₃, the element a represented an element of order 2, such as P(2, 1), and b represented an element of order 3, such as P(2, 3, 1). Let us construct a possible isomorphism. The command

In [0]:

F = Homomorph(Oct, S4)

defines F to be a homomorphism. We can tell Sage where the elements a and b are mapped to:

In [0]:

HomoDef(F, a, P(2,1) )

In [0]:

HomoDef(F, b, P(2,3,1) )

This should be consistent, since

ƒ(b)·ƒ(a) = ƒ(a)·ƒ(b)·ƒ(b).

The way to have Sage check that ƒ is so far defined consistently is to find whether ƒ is a homomorphism on the subgroup containing a and b. If we enter

In [0]:

FinishHomo(F)

then Sage indicates that so far the homomorphism is consistant, but it still is not defined for the whole group Oct. We can find the range of F so far with the command

In [0]:

HomoRange(F)

This shows that we have defined the homomorphism for 6 elements.

We now need to determine a value for ƒ(c) that makes an isomorphism. Note that ƒ(c) must be of order 4. We want to find all elements of S₄ which are of order 4 so we will be able to choose one for ƒ(c).

Finding all of the elements of a given order is not hard using Sage. This is because Sage can raise all of the elements to a given power in one step. Here is every element squared:

In [0]:

[ x^2 for x in S4]

Note that many of the elements, when squared, yield the identity element. In fact, elements 1, 2, 3, 6, 7, 8, 15, 17, 22, and 24 (counting from the left) have a² = e. The first element is the identity, but the others must be elements of order 2. Thus there are nine elements of S₄ that are of order 2.

We can use the same method to find the elements of order 4. Let us raise all elements to the fourth power:

In [0]:

[ x^4 for x in S4]

So elements 1, 2, 3, 6, 7, 8, 10, 11, 14, 15, 17, 18, 19, 22, 23, and 24 have the fourth power equaling the identity. Many of these are of order 2, as we have seen before. But the square of elements 10, 11, 14, 18, 19 and 23 are not the identity. Therefore, we have six elements of order 4. Comparing this with the original group

In [0]:

S4

tells us the six elements:

P(4, 1, 2, 3)
P(2, 4, 1, 3)
P(3, 1, 4, 2)
P(4, 3, 1, 2)
P(2, 3, 4, 1)
P(3, 4, 2, 1)

If the octahedronal group is isomorphic to S₄, then the element c must map to one of these six elements. But which one? Let us try the first permutation, The entire homomorphism would be defined by the commands

In [0]:

F = Homomorph(Oct, S4)
HomoDef(F, a, P(2, 1) )
HomoDef(F, b, P(2, 3, 1) )
HomoDef(F, c, P(4, 1, 2, 3) )
FinishHomo(F)

Unfortunately, this does not produce a homomorphism, since Sage found a contradiction. But perhaps by defining F(c) to be one of the other six elements of S₄ which is of order 4, we can produce a homomorphism.

EXPERIMENT:
By changing P(4, 1, 2, 3) with one of the other elements of S₄ which is of order 4:

P(2, 4, 1, 3)
P(3, 1, 4, 2)
P(4, 3, 1, 2)
P(2, 3, 4, 1)
P(3, 4, 2, 1)

see if you can find one which creates a homomorphism.

Once we have found a homomorphism, we want to see that ƒ is an isomorphism by showing that the kernel of ƒ is just the identity.

In [0]:

Kernel(F)

Since the kernel is the identity element, ƒ is an isomorphism.

Finally, we can check that the image of ƒ is S₄. The image is generated by the command

In [0]:

Image(F, Oct)

In [0]:

len(_)

Since there are 24 elements here, all of which are in S₄, this must be S₄. Therefore, we have shown that S₄ is isomorphic to the octahedral group. So we immediately see a relationship between one of the groups we have been working with and the permutation groups. Later this chapter, we will see an application of the permutation groups that will apply to any finite group.

Since a permutation is a function from the integers 1, 2, 3, … n onto themselves, we can use the circle graphs that we have used before to visualize these permutations. For example, to draw a picture of the permutation P(5,4,1,2,3), use the command:

In [0]:

CircleGraph([1,2,3,4,5], P(5,4,1,2,3))

Notice that this forms one triangle in red, which maps 1 to 5, 5 to 3, and then 3 back to 1. There is also a green "double arrow" that maps 2 to 4 and back to 2. So this circle graph reveals some additional structure to the permutation which we will study later. For now, let us study the geometrical significance of multiplying two permutations together.

We can graph two or more permutations simutaneously by adding the additional permutations to the Sage command.

In [0]:

CircleGraph([1,2,3,4,5], P(5,4,1,2,3), P(4,3,5,1,2))

Here, the red arrows represent the permutation P(5,4,1,2,3), while the green arrows represent P(4,3,5,1,2).

EXPERIMENT:
On the above circle graph, imagine what would happen if for each of the numbers {1,2,3,4,5}, one first traveled through a green arrow, and then traveled through a red arrow. Does this form a permutation on the set {1,2,3,4,5}? If so, which permutation is it? Is it the same permutation as P(5,4,1,2,3)·P(4,3,5,1,2) ?

The following command maps three permutations simutaniously:

In [0]:

CircleGraph([1,2,3,4,5], P(5,4,1,2,3), P(4,3,5,1,2),  P(2,1,3,5,4))

This circle graph answers the questions raised in the last experiment. In this graph, if one travels a green arrow, and immediately travel through a red arrow, one ends up exactly in the same place as if one traveled just a purple arrow. Thus, this "arrow composition" results in the permutation P(2,1,3,5,4), which is the product of P(5,4,1,2,3) and P(4,3,5,1,2). Note that the arrows are like functions, in that we apply the arrow of the second permutation first, and then the arrow for the first permutation.

Sage can help us to find the inverse of a permutation. The inverse of P(5,4,1,2,3) would be

In [0]:

P(5,4,1,2,3)^-1

We can make a circle graph of this new permutation.

In [0]:

CircleGraph([1,2,3,4,5], P(5,4,1,2,3)^-1 )

How does this circle graph compare to the circle graph of the original permutation?

In [0]:

CircleGraph([1,2,3,4,5],  P(5,4,1,2,3) )

It is easy to see that the graphs are the same, except that the arrows are all going in the opposite direction. (Of course, when the direction is reversed on the green "double arrow," it remains a double arrow.) Thus, we see that

⎛	1	2	3	4	5	⎞^-1	=	⎛	1	2	3	4	5	⎞
⎝	5	4	1	2	3	⎠	=	⎝	3	4	5	2	1	⎠

We can check this using Sage to see if the product of the two really is the identity:

In [0]:

P(5,4,1,2,3)*P(3,4,5,2,1)

We noted before that Sage displays only up to the last number not in position. The identity element has all of its numbers in position, so Sage does not display any of them! Therefore, P() represents the identity element of this group.

Because we can think of a permutation as a function of positive integers, we can evaluate a permutation at a given number. For example, the permutation

⎛	1	2	3	4	5	⎞
⎝	5	4	1	2	3	⎠

evaluated at 2 gives us 4. Since the Sage notation for a function of x is F(x), the Sage command for evaluation this permutation at 2 is:

In [0]:

P(5,4,1,2,3)(2)

We can evaluate this permutation at 7 as well.

In [0]:

P(5,4,1,2,3)(7)

Since this permutation does not mention the number 7, Sage assumes that it is fixed.

In spite of the simplicity of the notations for a permutation, we will find that there is yet another notation that is even more concise. We will study this in the next section.

Cycles

Throughout this chapter, we have been using the circle graphs to represent a permutation in S_n. For example, the permutation P(5,4,1,2,3) could be diagramed by the following graph:

In [0]:

CircleGraph([1,2,3,4,5], P(5,4,1,2,3) )

We can immediately see from this graph the red triangle connecting 1, 5, and 3, while a green "double arrow" connecting 2 and 4. In this section we will consider the significance of the two different colors of arrows.

We begin by noticing that some of the permutations have circle graphs that are all in one color. Consider the graph of the permutation P(4,5,2,3,1):

In [0]:

CircleGraph([1,2,3,4,5], P(4,5,2,3,1) )

This circle graph consists entirely of red arrows. These arrows indicate that the permutation can be expressed by a single chain

1 → 4 → 3 → 2 → 5 → 1.

This can be read, "1 goes to 4 which goes to 3 which goes to 2 which goes to 5 which goes back to 1." Any permutation which can be expressed as a chain like this one is called a cycle.

Here is another example of a circle graph of a permutation.

In [0]:

CircleGraph([1,2,3,4,5,6], P(2,4,1,6,5,3) )

In this graph, there is a green loop mapping 5 to itself, but all of the straight arrows are the same color―red. We can still represent this permutation by a single chain:

1 → 2 → 4 → 6 → 3 → 1.

This chain states where each number goes except for the number 5. However, if we stipulate that all numbers that are not mentioned in the chain map to themselves, we have expressed the permutation P(2,4,1,6,5,3) as a single chain, and hence this is also a cycle.

DEFININTION 5.2
Any permutation that can be expressed as a single chain is called a cycle. A cycle that moves exactly r of the numbers is called an r-cycle.

Whenever a permutation can be expressed as an r-cycle, it is easier to read the chain then the permutation. For example, to find where 4 is mapped to in the permutation P(2,4,1,6,5,3), one must count 4 numbers from the left, whereas in the notation

1 → 2 → 4 → 6 → 3 → 1.

one only has to spot the 4 and see that it maps to 6. We can further simplify the chains by using a more compact notation:

(1 2 4 6 3)

Here, each number is mapped to the next number in the chain. The last number always maps back to the first number. This notation is called the cycle notation of the permutation.

In general, the r-cycle (i₁ i₂ i₃ ··· i_r) represents the permutation that maps i₁ to i₂, i₂ to i₃, etc., and finally i_r back to i₁. Notice that

(i₁ i₂ i₃ ··· i_r)^-1 = (i_r i_r−1 ··· i₃ i₂ i₁).

so the inverse of an r-cycle will always be an r-cycle. However, the product of two cycles may not always give a cycle, but a permutation. The identity element can be written as the 0-cycle ( ).

A 1-cycle is actually impossible, since if one number is not fixed by a permutation, then the number that it maps to cannot be fixed. Thus, a non-identity permutation must move at least two numbers. We say that an [removed]r-cycle is a nontrivial cycle if r > 1.

Because the cycle notation is in general easier to use then standard permutation notation, we would like to find a way to write any permutation in terms of cycles. If we look back at the first circle graph of a permutation,

In [0]:

CircleGraph([1,2,3,4,5], P(5,4,1,2,3) )

we see that this permutation cannot be expressed as a single chain. However, the two different colored arrows suggests the following idea. Suppose we considered one permutation which consisted mainly of the red triangle, (with 2 and 4 mapping to themselves) and another permutation consisting mainly of the green double arrow, with 1, 3, and 5 mapping to themselves. These two permutations are given by

In [0]:

CircleGraph([1,2,3,4,5], P(5,2,1,4,3) )

and

In [0]:

CircleGraph([1,2,3,4,5], P(1,4,3,2,5) )

EXPERIMENT:
Is there a way to multiply the permutations P(5,2,1,4,3) and P(1,4,3,2,5) to produce the original permutation P(5,2,1,4,3)? Which order do the permutations need to be multiplied?

To help explain why the permutations acted the way that they did in the experiment, try graphing both permutations on the same graph:

In [0]:

CircleGraph([1,2,3,4,5], P(5,2,1,4,3), P(1,4,3,2,5) )

One can see the simularity between this graph and the graph of P(5,4,1,2,3). Let us write the permutations P(5,2,1,4,3) and P(1,4,3,2,5) in cycle notation:

P(5,4,1,2,3) = (1 5 3), P(1,4,3,2,5) = (2 4).

Notice that when these two permutations are writen as cycles, there are no numbers in common between these two cycles. We give a name to these type of cycles.

DEFINITION 5.3
Two cycles

(i₁ i₂ i₃ ··· i_r) and (j₁ j₂ j₃ ··· j_s)

are disjoint if none of the i's are equal to any of the j's.

We saw that (1 5 3) and (2 4) are disjoint. It is fairly clear that two disjoint cycles will commute with one another, as demonstrated in the experiment.

Can we express other permutations as a product of cycles? Consider the permutation

⎛	1	2	3	4	5	6	7	8	⎞
⎝	4	6	1	8	2	5	7	3	⎠

Here is the circle graph of this permutation:

In [0]:

CircleGraph([1,2,3,4,5,6,7,8], P(4,6,1,8,2,5,7,3) )

We see from the circle graph that this permutation maps 1 into 4, 4 into 8, 8 into 3, and 3 back into 1. So the cycle (1 4 8 3) describes part of the permutation. However, we also have 2 mapping to 6, which maps to 5, which maps back to 2. So the cycle (2 6 5) is also a component of the permutation. Finally, 7 maps to itself, so it will not be the part of any cycle. Thus we can describe this permutation as

(1 4 8 3)·(2 6 5).

We can imitate this process for any permutation. As a result, we have the following lemma:

LEMMA 5.1
Let x be an element of S_n which is not the identity. Then x can be written as a product of nontrivial disjoint cycles. This representation of x is unique up to the rearrangement of the cycles.

Click here for the proof.

Since any permutation can be written succinctly in terms of cycles, we are given another way to express any permutation. Sage uses the notation

C(i, j, k, … )

to denote the cycle (i j k …). Sage can multiply two cycles together. For example, to multiply (2 3 4 5)·(1 2 4), type

In [0]:

C(2,3,4,5)*C(1,2,4)

Notice that Sage forms the answer as a product of 2 disjoint cycles, without the times sign between them. We call this the cycle decomposition of the permutation. Can we see why this is the product? Remember to work from right to left in multiplying permutations or cycles.

We can convert back and forth between the permutation notation and the cycles. The commands

PermToCycle( P(………)) and CycleToPerm( C(………))

tell Sage to switch between the two notations. Thus, to convert our answer to a permutation, we type

In [0]:

CycleToPerm( C(1,3,4)*C(2,5) )

Likewise, Sage can use the procedure described in Lemma 5.1 to find the cycle decomposition of the permutation

⎛	1	2	3	4	5	6	7	8	⎞
⎝	4	6	1	8	2	5	7	3	⎠

by the command

In [0]:

PermToCycle( P(4,6,1,8,2,5,7,3) )

To enter the identity element in Sage, use C( ), which corresponds to the 0-cycle ().

We may even mix the two notations within an expression:

In [0]:

C(1,2,3)*P(3,1,2,5,4)*C(4,5)

Whenever Sage encounters a mixture like this, it puts the answer in terms of cycles. In this case the answer is the identity permutation, so Sage returned ( ).

We can evaluate a cycle or a product of cycles at a given number, just as we did for permutations. For example, to determine where the cycle (1 4 8 3) sends the number 3, type

In [0]:

C(1,4,8,3)(3)

This evaluates the cycle at 3, giving the value 1. We can also form a circle graph of a cycle as we would a permutation:

In [0]:

CircleGraph([1,2,3,4,5,6,7,8], C(1,4,8,3) )

This even works for a product of cycles.

In [0]:

CircleGraph([1,2,3,4,5,6,7,8], C(1,4,8,3)*C(2,6,5) )

However, to evaluate a product of cycles at a given number, we need an extra pair of parentheses:

In [0]:

(C(1,4,8,3)*C(2,6,5))(2)

Although Sage works faster using the standard permutation notation, cycles are more succinct in most cases and more readable. Thus, for large operations that could take time, such as checking that a function is a homomorphism, it will be much faster using the P(………) notation.

We mentioned that there are no permutations that move just one element, but the permutations which move exactly 2 elements will be important. We will give these 2-cycles a special name.

DEFINITION 5.4

A transposition is a 2-cycle (i₁ i₂), where i₁ ≠ i₂.

We can find the number of transpositions in S[removed] as follows: i₁ can be any of the n integers, and i₂ can be any of the n − 1 integers left over. Thus, there are

n(n − 1) = n² − n

ways of forming an ordered pair (i₁, i₂) with i₁ unequal to i₂. However, the transposition (i₁ i₂) is the same as the transposition (i₂ i₁). Thus, by counting ordered pairs, we have counted each transposition twice. Therefore, to find the number of transpositions, we divide that count by 2 to get

n² − n	.
2

LEMMA 5.2
For n > 1, the set of transpositions in S_n generates S_n.

Click here for the proof.

Of course, a particular permutation can be expressed as a product of transpositions in more than one way. But an important property of the symmetric groups is that the number of transpositions used to represent a given permutation will always have the same parity, that is, even or odd. To show this, we will first prove the following lemma.

LEMMA 5.3
The product of an odd number of transpositions in S_n cannot equal the identity element.

Click here for the proof.

We can use this lemma to prove the following theorem.

THEOREM 5.1: The Signature Theorem
For the symmetric group S_n, define the function

σ: S_n → ℤ

σ(x) = (−1)^N(x),

where N(x) is the minimum number of transpositions needed to express x as a product of transpositions. Then this function, called the signature function, is a homomorphism from S_n to the integers {−1, 1}.

Click here for the proof.

With Sage, can compute the signature function on both permutations and products of cycles, using the Signature command.

In [0]:

Signature( P(4,3,5,1,2) )

In [0]:

Signature( C(1,4,2,7)*C(6,7,3) )

Try this out with several permutations. You will notice that the signature will always be ±1.

The signature of an r-cycle will be −1 if r is even, and +1 if r is odd. The fact that this function is a homomorphism has some important ramifications.

DEFINITION 5.5
A permutation is an alternating permutation or an even permutation if the signature of the permutation is 1. A permutation is an odd permutation if it is not even, that is, if the signature is −1. The set of all alternating permutations of order n is written A_n.

COROLLARY 5.1
The set of all alternating permutations A_n is a normal subgroup of S_n. If n > 1, then S_n/A_n is isomorphic to Z₂.

Click here for the proof.

Finally, we can ask which permutations generate the group A_n. Since the set of 2-cycles generated S_n, it is not too surprising that A_n can also be generated by cycles.

PROPOSITION 5.1

For n > 2, the alternating group A_n is generated by the set of 3-cycles.

Click here for the proof.

Let us use this proposition to find the elements of A₄. We know that this is generated by 3-cycles, and has 24/2 = 12 elements. Let us see if two cycles are enough to give us twelve elements.

In [0]:

Group( C(1,2,3), C(1,2,4) )

In [0]:

len(_)

Since this gives us 12 elements, this is A₄. Eight of the twelve elements are 3-cycles. Do you recognize the other 4 elements?

Cayley's Theorem

In the last section, we used the circle graph to illustrate a given permutation. The circle graphs produced had the property that every point on the circle had exactly one arrow which points to it. In Chapter 3 we mentioned that such a graph was one-to-one and onto. Where else have we seen circle graphs with this property?

Although we have seen circle graphs that are one-to-one and onto in several places, many of them were in Chapter 3 when we were working with cosets. To illustrate, the following command loads the quaternionic group Q discovered in the last chapter.

In [0]:

Q = InitQuaternions(); Q

Recall the multiplication table for Q is given by:

In [0]:

MultTable(Q)

We can know look at the circle graph of LeftMult(x) and RightMult(x) for different elements x in Q.

In [0]:

CircleGraph(Q, LeftMult(i) )

In [0]:

CircleGraph(Q, RightMult(i) )

Look carefully. These two circle graphs are not the same, even though they are very similar. Notice that these circle graphs are one-to-one and onto, just as the graphs of a permutation. Could we view these circle graphs as permutations in S₈? Suppose we numbered the elements of the group, starting at the top and working clockwise. That is, we would assign

1)	1
2)	i
3)	j
4)	k
5)	−1
6)	−i
7)	−j
8)	−k

We can then create graphs of permutations that simulate the two graphs we see above.

In [0]:

CircleGraph([1,2,3,4,5,6,7,8], C(1,2,5,6)*C(3,8,7,4) )

In [0]:

CircleGraph([1,2,3,4,5,6,7,8], C(1,2,5,6)*C(3,4,7,8) )

EXPERIMENT:
Replace the i in the two circle graphs on Q with other elements of Q, such as j, -1, and k. Can you find the permutations in S₈ which produce the same circle graphs? Remember that there will be two permutations for each element of Q: one that simulates LeftMult(x), and one that simulates RightMult(x). Are there any elements for which the graphs for LeftMult(x) and RightMult(x) are the same?

We see from this experiment that we each element of Q will correspond to two elements of S₈, one that simulates LeftMult(x), which we will call ƒ(x), and one that simulates RightMult(x), called ϕ(x). Here is a table of these permutations:

x	ƒ(x) LeftMult(x)	ϕ(x) RightMult(x)
1	( )	( )
i	(1 2 5 6)(3 8 7 4)	(1 2 5 6)(3 4 7 8)
j	(1 3 5 7)(2 4 6 8)	(1 3 5 7)(2 8 6 4)
k	(1 4 5 8)(2 7 6 3)	(1 4 5 8)(2 3 6 7)
−1	(1 5)(2 6)(3 7)(4 8)	(1 5)(2 6)(3 7)(4 8)
−i	(1 6 5 2)(3 4 7 8)	(1 6 5 2)(3 8 7 4)
−j	(1 7 5 3)(2 8 6 4)	(1 7 5 3)(2 4 6 8)
−k	(1 8 5 4)(2 3 6 7)	(1 8 5 4)(2 7 6 3)

By labling the permutations by ƒ(x) and ϕ(x), we emphisize that these two functions map elements of Q to elements of S₈. So here's the natural question: Are either of these homomorphisms?

EXAMPLE:
Use Sage to see if either of the two functions f or ϕ are homomorphisms.

Let's begin by testing ƒ. Normally, in defining a homomorphism, we first determine the domain group and the target group. But in this case the target group is S₈, which has 40320 elements. Rather than having Sage construct all of the elements of this group, which would take an unreasonable amount of time, we can find the range of the homomorphism by determining which group is generated by ƒ(i) and ƒ(j).

In [0]:

Q = InitQuaternions(); Q

In [0]:

T = Group(C(1,2,5,6)*C(3,8,7,4), C(1,3,5,7)*C(2,4,6,8)); T

Now we can try to create the homomorphism.

In [0]:

F = Homomorph(Q, T)

In [0]:

HomoDef(F, i, C(1,2,5,6)*C(3,8,7,4) )
HomoDef(F, j, C(1,3,5,7)*C(2,4,6,8) )
HomoDef(F, k, C(1,4,5,8)*C(2,7,6,3) )

In [0]:

FinishHomo(F)

So this is not a homomorphism. What about ϕ?

EXPERIMENT:
See if ϕ is a homomorphism using the above table. If it seems to produce a homomorphism, use GraphHomo to verify that it is one-to-one and onto.

So apparently, ϕ(x) is a homomorphism from Q to S₈. In fact, it is clear that this is one-to-one, so ϕ(x) is an isomorphism from Q onto a subgroup of S₈. Will RightMult produce an isomorphism for any group? The answer is yes, and the proof reveals an important property of permutation groups. You should be able to use the RightMult function to prove the following theorem:

THEOREM 5.2:Cayley's Theorem
Every finite group of order n is isomorphic to a subgroup of S_n.

Click here for the proof.

Although this theorem shows that all finite groups can be considered as a subgroup of a symmetric group, the theorem can also apply to infinite groups as well. Of course we then must consider infinite symmetric groups, whose elements would be permutations on an infinite collection of objects. We might have a difficult time expressing some of the permutations! For example, if we had a library of an infinite number of books, we could not begin to express how one could rearrange the books. Some of the permutations could be expressed as one-to-one and onto functions. However, most of the permutations in an infinite symmetric group are not expressable using a finite number of words or symbols. Problems 10 through 12 of §5.2 reveal some of the unusual properties of infinite symmetric groups. Fortunately, we will mainly work with finite symmetric groups.

Although Cayley's theorem (5.2) shows that any finite group G is a subgroup of S_n, where n is the size of the group G, we often can find a smaller symmetric group that contains an isomorphic copy of G.

EXAMPLE:
Consider the group D₄, introduced in the last chapter, for which [removed]a⁴ = b² = e, and b·a = a³·b. Consider the effects of RightMult on the set of cosets, using a non-normal subgroup.

In [0]:

InitGroup("e")
AddGroupVar("a", "b")
Define(a^4, e)
Define(b^2, e)
Define(b*a, a^3*b)
D4 = ListGroup()
D4

Let us consider a non-normal subgroup of D₄,

In [0]:

H = Group(b); H

We saw in Cayley's theorem (5.2) that RightMult applied to the elements ofthe group derived a homomorphism. What if we applied RightMult to the cosets of the subgroup? Recall that RightMult(g) can be thought as a function p_g(x) = g·x, that is, it multiplies the argument of the function to the right of g. If we apply this function to a left coset of H, we have p_g(x H) = g·x H, which yields another left coset. (Right cosets won't work here, since p_g(H x) = g·H x, which is neither a left nor right coset.) Let us first create a list of left cosets.

In [0]:

L = LftCoset(D4, H); L

What happens if we multiply each of the cosets by a fixed element of the group, say a?

In [0]:

CircleGraph(L, RightMult(a) )

We see that each coset is mapped to another coset. Once again, we have a one-to-one and onto mapping, which we can treat as a permutation. Let us first number the right cosets of H.

1 )	{ e, b }
2 )	{ a, a·b }
3 )	{ a², a²·b }
4 )	{ a³, a³·b }

Then the circle graph shows that left multiplication by a is equivalent to the permutation (1 2 3 4). If we try this with the element b instead,

In [0]:

CircleGraph(L, RightMult(b) )

the circle graph shows that right multiplication by b is equivalent to the permutation (2 4).

EXPERIMENT:
Try replacing the elements a and b with other elements of the group. Do the circle graphs produce permutations?

Since we have a permutation for each element of the group, the natural question is whether we have a homomorphism between the group D₄ and the permutation group. Sage can check for us.

In [0]:

S4 = Group(C(1,2), C(1,2,3), C(1,2,3,4) ); S4

In [0]:

F = Homomorph(D4, S4)
HomoDef(F, a, C(1,2,3,4) )
HomoDef(F, b, C(2,4) )

In [0]:

FinishHomo(F)

So we indeed have a homomorhism, just as in Cayley's theorem. What is the kernel of this homomorphism?

In [0]:

Kernel(F)

This proves that D₄ is isomorphic to a subgroup of S₄. Note that this is a much stronger result than Cayley's theorem (5.2), which only says that D₄ is isomorphic to a subgroup of the larger group S₈.

We can now see the subgroup of S₄ isomorphic to D₄.

In [0]:

Image(F, D4)

In [0]:

MultTable(_)

The multiplication table reveals a non-abelian group with 5 elements of order 2, so this is indeed isomorphic to D₄. We can generalize this procedure to produce the following result:

THEOREM 5.3: Generalized Cayley's Theorem
Let G be a finite group of order n, and H a subgroup of order m. Then there is a homomophism from G to S_k, with k = n/m, and whose kernel is a subgroup of H.

Click here for the proof.

We see one application of this proposition in the case of D₄. Since H was a subgroup of order 2 which was not normal, the only normal subgroup of G that is contained in H is the trivial subgroup. Thus, the homomorphism is an isomorphism, and we find a copy of D₄ inside of S₄ instead of having to look in the larger group S₈. This idea can be applied whenever we can find a subgroup of G that does not contain any nontrivial normal subgroups of G.

But there is another important ramification from this proposition. We can prove the existence of a normal subgroup of a group, knowing only the order of the group!

COROLLARY 5.2
Let G be a finite group, and H any subgroup of G. Then H contains a subgroup N, which is a normal subgroup of G, such that |G| divides (|G|/|H|)! · |N|.

Click here for the proof.

Here is an example of how we can prove the existence of a nontrivial normal subgroup, using just the order of the group. Suppose we have a group G of order 108. Suppose that G has a subgroup of order 27. (We will find in §7.4 that all groups of order 108 must have a subgroup of order 27.) Using |G|=108 and |H|=27, we find that G must contain a normal subgroup N such that

108 divides (108/27)! ·|N|=24·|N|.

But this means that |N| must be a multiple of 9. Since N is a subgroup of H, which has order 27, we see that N is of order 9 or 27. Hence, we have proven that G contains a normal subgroup of either order 9 or 27. This will go a long way in finding the possible group structures of G, using only the size of the group G.

Numbering the Permutations

We have seen that from Cayley's theorem that any group can be represented as the subgroup of a symmetric group. In turn, most of the permutations in the symmetric group can be written succinctly as a product of disjoint cycles. So naturally, we can express any group in terms of cycles.

For example, we saw using Cayley theorem a copy of the quaternionic group Q as a subgroup of S₈. It was generated by the elements

ϕ(i) = (1 2 5 6)(3 4 7 8)
ϕ(j) = (1 3 5 7)(2 8 6 4).

In fact, the entire group is given by

In [0]:

Q = Group( C(1,2,4,6)*C(3,5,7,8) , C(1,3,4,7)*C(2,8,6,5) ); Q

To compare notation, let us convert these elements to permutaions.

In [0]:

[ CycleToPerm(x) for x in Q ]

Which method is best? For small groups, using cycles would be a good choice, because the results are easy to read. But for larger groups (say over 100 elements, and yes, we will be working with groups that large in the next chapter) having Sage write out all of the elements in terms of cycles would be time consuming and messy. It would be nice to have a succinct way to describe each permutation using some kind of abbreviation.

The clue for seeing how such an abbreviation is possible is to look again at the group S₄, using permutation notation.

In [0]:

S4 = Group( P(2,1), P(2,3,1), P(2,3,4,1) ); S4

Notice that Sage sorts the elements, first listing the identity, then the transposition which exchanges 1 and 2, then the permutations which change only the first three elements, and finally the permutations which move the fourth element. But if we look closely we can find even more patterns. For example, the last six elements are the six elements which map 4 into 1. Can you see any other patterns?

Sage uses a predefined order to list all of the permutations. As a result, we can number the permutations as follows:

1^st permutation =	P( )
2^nd permutation =	P(2, 1)
3^rd permutation =	P(1, 3, 2)
4^th permutation =	P(3, 1, 2)
5^th permutation =	P(2, 3, 1)
6^th permutation =	P(3, 2, 1)
7^th permutation =	P(1, 2, 4, 3)
………	………
24^th permutation =	P(4, 3, 2, 1)

In this list the first 2 elements give the group S₂, the first 6 give S₃, and the first 24 elements give S₄. This pattern can be extended to higher order permutations, so that the first n! permutations gives the group S_n.

The advantage of sorting the permutations in this way is that Sage can quickly find the n^th permutation without having to find any of the previous permutations. For example, to find out what the 2000th permutation would be on this list, type

In [0]:

NthPerm(2000)

Sage can also determine where a given permutation is on the list of permutations. The command PermToInt( P(………) ) converts a permutation to a number

In [0]:

PermToInt(P(4,1,7,6,3,2,5))

We now have found a way of abbreviating permutations. Rather than spelling out where each element is mapped, we can give a single number that describes where the permutation is on the list of permutations. This will be called the integer representation of the permutation. Although this representation hides most of the information about the permutation, Sage can quickly recover all of the information needed to do group operations.

For example, suppose we want to multiply the 3^rd permutation with the 21^st. We could enter the command

In [0]:

NthPerm(3) * NthPerm(21)

We could convert this back to a number as follows:

In [0]:

PermToInt( NthPerm(3) * NthPerm(21) )

So the 3^rd permutation times the 21^st permutation gives the 23^rd permutation. If we multiplied in the other order, we would have

In [0]:

PermToInt( NthPerm(21) * NthPerm(3) )

So the 21^st permutation times the 3^rd permutation gives the 19^th permutation.

EXPERIMENT:
Try entering in different numbers in place of 21 and 3, to see what happens.

Sage provides an abbreviation to the permutations. By setting the variable DisplayPermInt to true, permutations will be displayed as their integer counterpart.

In [0]:

DisplayPermInt = true

In [0]:

P(4,1,7,6,3,2,5)

Now many of Sage's operations can be done with integer abreviation of the elements. For example, we found that the quaternionic group Q was isomorphic to a subgroup of S₈, generated by the elements

(1 2 5 6)(3 4 7 8) and (1 3 5 7)(2 8 6 4).

We first convert these cycles to permutations, which will display as integers.

In [0]:

CycleToPerm( C(1,2,5,6)*C(3,4,7,8) )

In [0]:

CycleToPerm( C(1,3,5,7)*C(2,8,6,4) )

So we find that the quaternionic group contains the 25827^th and 14805^th permutations. Now we can form the group using these two permutaions as generators.

In [0]:

Q = Group(NthPerm(25827), NthPerm(14805)); Q

So the entire group can be given on a single line in a way which expresses the entire structure of the group. We can see the multiplication table of the group

In [0]:

MultTable(Q)

and see that the group is isomorphic to Q. This integer representation is succint enough to form such a table, and has many other advantages over cyclic permutations, especially when we are working with large subgroups of the symmetric groups. Not only is it much easier to identify two elements as being the same, but also the elements do not take up as much room to display.

We can return to the standard notation for permutations by setting DisplayPermInt to false.

In [0]:

DisplayPermInt = false

In [0]:

MultTable(Q)

This multiplication table is harder to read. Thus, it is worthwhile to introduce the new representation.

There are simple algorithms to convert from the permutation representation to the integer representation and back without a computer. We begin by presenting a method of converting from a permutation to a integer.

EXAMPLE:

Demonstrate without Sage that P(4, 1, 7, 6, 3, 2, 5) is the 2000^th permutation.

For each number in the permutation, we count how many numbers further left are larger than that number. For example, the 4 has no numbers further left, so the count would be 0. The 3, however, has three numbers to the left of it which are larger, namely 4, 7, and 6. Here are the results of these counts.

P(4, 1, 7, 6, 3, 2, 5)
0 1 0 1 3 4 2

Next, we multiply each of these counts by (n − 1)!, and add the products together, and finally add 1. Thus,

0 · 0! + 1 · 1! + 0 · 2! + 1 · 3! + 3 · 4! + 4 · 5! + 2 · 6! + 1 = 2000.

A similar algorithm reverses the procedure, and determines the n^th permutation.

EXAMPLE:
Determine the 4000^th permutation without Sage.

We begin by subtracting 1, then using the division algorithm to successively divide by 2, 3, 4, etc., until the quotient is 0.

3999 = 2 ·	1999 + 1
1999 = 3 ·	666 + 1
666 = 4 ·	166 + 2
166 = 5 ·	33 + 1
33 = 6 ·	5 + 3
5 = 7 ·	0 + 5

Since the last division was by n = 7, the permutation is in S₇. We will use the remainders to determine the permutation, starting from the last remainder, and working towards the first. We start with a list of numbers from 1 to n:

{1, 2, 3, 4, 5, 6, 7}

For each remainder m, we consider the (m + 1)^st largest number in the list which has not been crossed out. Since the last remainder is 5, we take the 6^th largest number, which is 2. This eliminates 2 from the list.

3999 = 2 ·	1999 + 1
1999 = 3 ·	666 + 1
666 = 4 ·	166 + 2
166 = 5 ·	33 + 1
33 = 6 ·	5 + 3
5 = 7 ·	0 + 5	⟹ 2

{1, 2, 3, 4, 5, 6, 7}

Here is the result after processing two more remainders.

3999 = 2 ·	1999 + 1
1999 = 3 ·	666 + 1
666 = 4 ·	166 + 2
166 = 5 ·	33 + 1	⟹ 6
33 = 6 ·	5 + 3	⟹ 4
5 = 7 ·	0 + 5	⟹ 2

{1, 2, 3, 4, 5, 6, 7}

The next remainder is 2, so we take the 3^rd largest number which is not crossed out, which is 3. Continuing, we get the following.

3999 = 2 ·	1999 + 1	⟹ 1
1999 = 3 ·	666 + 1	⟹ 5
666 = 4 ·	166 + 2	⟹ 3
166 = 5 ·	33 + 1	⟹ 6
33 = 6 ·	5 + 3	⟹ 4
5 = 7 ·	0 + 5	⟹ 2

{1, 2, 3, 4, 5, 6, 7}

The only number not crossed out is 7, which becomes the first number in the permutation. The rest of the permutation can be read from the new numbers from top to bottom, producing P(7, 1, 5, 3, 6, 4, 2).

EXPERIMENT:
Use the method of the previous example to verify that P(7, 1, 5, 3, 6, 4, 2) is indeed the 4000^th permutation.

The simple algorithms for converting permutations to integers and back make this association more natural. It also explains why Mathematica is able to convert permutations so quickly.

Proofs:

Proof of Lemma 5.1:

Let us say that x fixes the integer i if x(i) = i. We will use induction on the number of integers not left fixed by x, denoted by m. Because x is not the identity, there is at least one integer not fixed by x. In fact, m must be at least 2, for the first integer must have somewhere to go.

If m = 2, then only two numbers i₁ and i₂ are moved. Since these are the only two integers not fixed, x must be a 2-cycle (i₁ i₂).

We now will assume by induction that the lemma is true whenever the number of integers not left fixed by x is fewer than m. Let i₁ be one integer that is not fixed, and let i₂ = x(i₁). Then x(i₂) cannot be i₂ for x is one-to-one, and if x(i₂) is not i₁, we define i₃ = x(i₂). Likewise, x(i₃) cannot be either i₂ or i₃, since x is one-to-one. If x(i₃) is not i₁, we define i₄ = x(i₃).

Eventually this process must stop, for there are only m elements that are not fixed by x. Thus, there must be some value k such that x(i_k) = i₁. Define the permutation y to be the k-cycle (i₁ i₂ i₃ … i_k).
Then x·y^-1 fixes all of the integers fixed by x, along with i₁, i₂, i₃, … i_k. By induction, since there are fewer integers not fixed by x·y^-1 then by x, x·y^-1 can be espressed by a series of nontrivial disjoint cycles c₁·c₂·c₃·…·c_t. Moreover, the integers appearing in c₁·c₂·c₃·…·c_t are just those that are not fixed by x·y^-1. Thus, c₁, c₂, c₃, …, c_t are disjoint from y. Finally, we have

x = y·c₁·c₂·c₃·…·c_t.

Therefore, x can be written as a product of disjoint nontrivial cycles. By induction, every permutation besides the identity can be written as a product of nontrivial disjoint cycles.

For the uniqueness, suppose that a permutation x has two ways of being written is terms of nontrivial disjoint cycles:

x = c₁·c₂·c₃·…·c_r = d₁·d₂·d₃·…·d_s.

For any integer i₁ not fixed by x, one and only one cycle must contain i₁. Suppose that cycle is c_j = (i₁, i₂, i₃, … i_q). But by the way we constructed the cycles above, this cycle must also be one of the d_k's. Thus, each cycle c_j is equal to d_k for some k. By symmetry, each d_k is equal to c_j for some j. Thus, the two ways of writing x in terms of nontrivial disjoint cycles are merely rearrangements of the cycles.

Return to text

Proof of Lemma 5.2:

We need to show that every element of S_n can be written as a product of transpositions. The identity element can be written as [removed](1 2)(1 2), so we let x be a permutation that is not the identity. By Lemma 5.1, we can express x as a product of nontrivial disjoint cycles:

x = (i₁ i₂ i₃ … i_r)·(j₁ j₂ … j_s)·(k₁ k₂ … k_t)·….

Now, consider the product of transpositions

(i₁ i₂)·(i₂ i₃)· ⋯ ·(i_r−1 i_r)·(j₁ j₂)·(j₂ j₃)· ⋯ ·(j_s−1 j_s)·(k₁ k₂)· ⋯ ·(k_t−1 k_t)· ⋯ .

Note that this product is equal to x. (Recall that we are working from right to left.) Therefore, we have expressed every element of S_n as a product of transpositions.

Return to text

Proof of Lemma 5.3:

Since S₂ only contains one transposition, (1 2), raising this to an odd power will not be the identity element, so the lemma is true for the case n = 2. So by induction we can assume that the lemma is true for S_n₋₁. Suppose that there is an odd number of transpositions producing the identity in S_n. Then we can find such a product that uses the fewest number of transpositions, say k transpositions, with k odd. At least one transposition will involve moving n, since the lemma is true for S_n₋₁. Suppose that the m^th transposition is the last one that moves n. If m = 1, then only the first transposition moves n, so the product cannot be the identity. We will now use induction on m. That is, we will assume that no product of k transpositions can be the identity for a smaller m. But then the (m − 1)^st and m^th transpositions are one of the four possibilities

(n x)(n x), (n x)(n y), (x y)(n x), or (y x)(n x)

for some x, y, and z. In the first case, the two transpositions cancel, so we can form a product using a fewer number of transpositions. In the other three cases, we can replase the pair with another pair,

(n x)(n y) = (n y)(x y); (x y)(n x) = (n y)(x y); (y z)(n x) = (n x)(y z);

for which m is smaller. Thus, there is no odd product of transpositions in S_n equaling the identity.

Return to text

Proof of Theorem 5.1:

By Lemma 5.2, every element of S_n can be written as a product of transpositions, so σ(x) is well defined. Obviously this maps S_n to {−1, 1}, so we only need to establish that this is a homomorphism. Suppose that

σ(x·y) ≠ σ(x)·σ(y).

Then N(x·y) − (N(x) + N(y)) would be an odd number. Since N(x^-1) = N(x), we would also have N(x·y) + (N(y^-1) + N(x^-1)) being an odd number. But then we would have three sets of transpositions, totaling an odd number, which when strung together produce x·y·y^-1·x^-1 = ( ). This contradicts Lemma 5.3, so in fact σ(x·y) = σ(x)·σ(y) for all x and y in S_n.

Return to text

Proof of Corollary 5.1:

Clearly A_n is a normal subgroup of S_n, since A_n is the kernel of the signature homomorphism. Also if n > 1, then S_n contains at least one transposition whose signature would be −1. Thus, the image of the homomorphism is {1, −1}. This group is isomorphic to Z₂. Then by the first isomorphism theorem (4.1), S_n/A_n is isomorphic to Z₂.

Return to text

Proof of Proposition 5.1:

Since every 3-cycle is a product of two transpositions, every 3-cycle is in A_n. Thus, it is sufficient to show that every element in A_n can be expressed in terms of 3-cycles. We have already seen that any element can be expressed as a product of an even number of transpositions. Suppose we group these in pairs as follows:

x = [(i₁ j₁)·(k₁ l₁)] · [(i₂ j₂)·(k₂ l₂)] · … · [(i_r j_r)·(k_r l_r)].

If we could convert each pair of transpositions into 3-cycles, we would have the permutation x expressed as a product of 3-cycles. There are three cases to consider:

Case 1: The integers i_m, j_m, k_m, and l_m are all distinct. In this case,

(i_m j_m)·(k_m l_m) = (i_m k_m l_m)·(i_m j_m l_m).

Case 2: Three of the four integers i_m, j_m, k_m, and l_m are distinct. The four combinations that would produce this situation are

i_m = k_m, i_m = l_m, j_m = k_m, or j_m = l_m

However, these four possibilities are essentially the same, so we only have to check one of these four combinations: i_m = k_m. Then we have

(i_m j_m)·(i_m l_m) = (i_m l_m j_m).

Case 3: Only two of the four integers i_m, j_m, k_m, and l_m are distinct. Then we must either have i_m = k_m and j_m = l_m, or i_m = l_m and j_m = k_m. In either case, we have

(i_m j_m)·(k_m l_m) = ( ) = (1 2 3)·(1 3 2).

In all three cases, we were able to express a pair of transpositions in terms of a product of one or two 3-cycles. Therefore, the permutation x can be written as a product of 3-cycles.

Return to text

Proof of Theorem 5.2:

Let G be a group of order n. For each g in G, define the mapping

p_g : G → G by p_g(x) = g·x.

For a given g, if p_g(x) = p_g(y), then g·x = g·y, so x = y. Hence, p_g is a one-to-one mapping. Since G is a finite group, we can use to pigeonhole principle to show that p_g is also onto, and hence is a permutation of the elements of G.

We now can consider the mapping ϕ from G to the symmetric group S_|_G_| on the elements of G, given by

ϕ(g) = p_g.

Now, consider two elements ϕ(g) and ϕ(h). The product of these is the mapping

x → (p_g·p_h)(x) = p_g(p_h(x)) = p_g(h·x) = g·(h·x) = (g·h)·x.

Since this is the same as ϕ(g·h), ϕ is a homomorphism.

The element g will be in the kernel of the homomorphism ϕ only if p_g(x) is the identity permutation. This means that g·x = x for all elements x in G. Thus, the kernel consists just of the identity element of G, and hence ϕ is an isomorphism. Therefore, G is isomorphic to a subgroup of S_|_G_|.

Return to text

Proof of Theorem 5.3:

Let Q be the set of left cosets G/H. For each g in G, define the mapping

p_g : Q → Q by p_g(x H) = g·x H.

Note that this is well defined, since if x H = y H, then g·x H = g·y H.

For a given g, if p_g(x H) = p_g(y H), then g·x H = g·y H, so x H = y H. Hence, p_g is a one-to-one mapping. Since Q is a finite set, by the pigeonhole principle, p_g must also be onto, and hence is a permutation of the elements of Q.

We now can consider the mapping ϕ from G to the symmetric group S_|_Q_| on the elements of Q, given by

ϕ(g) = p_g.

Now, consider two elements ϕ(g) and ϕ(h). The product of these is the mapping

x H → (p_g·p_h)(x H) = p_g(p_h(x H)) = p_g(h·x H) = g·(h·x H) = (g·h)·x H.

Since this is the same as ϕ(g·h), ϕ is a homomorphism.

Finally, we must show that the kernel of ϕ is a subgroup of H. The element g will be in the kernel of the homomorphism ϕ only if p_g(x H) is the identity permutation. This means that g·x H = x H for all right cosets x H in Q. In particular, the left coset e·H = H is in Q, so g·H = H. This can only happen if g is in H. Thus, the kernel is a subgroup of H. We have found a homomorphism ϕ from the group G to the group S_|_Q_|, whose kernel is a subgroup of H.

Return to text

Proof of Corollary 5.2:

By the generized Cayley's theorem (5.3), there is a homomorphism ϕ from G to S_k, where k = |G|/|H|. Furthermore, the kernel is a subgroup of H. If we let N be the kernel, and let I be the image of the homomorphism, we have by the first isomorphism theorem (4.1) that

G/N ≈ I.

In particular, |G|/|N| = |I|, and |I| is a factor of |S_k| = k!. This means that |G| is a factor of k!· |N|.

Return to text

Sage Problems

For Problems 17 through 20: Determine how the following permutations can be expressed in terms of the book rearrangements First, Last, Left, Right, and Rev.

§5.1 #17)

⎛	1	2	3	4	⎞
⎝	1	3	2	4	⎠

§5.1 #18)

⎛	1	2	3	4	⎞
⎝	4	2	3	1	⎠

§5.1 #19)

⎛	1	2	3	4	⎞
⎝	3	1	4	2	⎠

§5.1 #20)

⎛	1	2	3	4	⎞
⎝	2	4	1	3	⎠

§5.2 #18)
Use Sage to find a pair of 3-cycles whose product is a 3-cycle. Can there be a product of two 4-cycles that yields a 4-cycle?

§5.2 #19)
The cycle structure of a permutation is the number of 2-cycles, 3-cycles, etc. it contains when written as a product of disjoint cycles. For example, (1 2 3)(4 5) and (3 4 5)(1 2) have the same cycle structure. Consider the elements

In [0]:

a = C(1, 2, 3); a

In [0]:

b = C(1, 4, 2, 5, 6, 7); b

Predict the cycle structure of a², a³, b², b³, and b⁶. Check your answers with Sage.

§5.2 #20)
Calculate a·b from Problem 19. Predict the cycle structure of (a·b)², (a·b)³, and (a·b)⁴, and verify your predictions with Sage.

§5.2 #21)
Calculate a·b·a^-1 from Problem 19. Notice that it has the same cycle structure as b. Try this with other random permutations. Does a·b·a^-1 always have the same cycle structure as b? How do Problems 16 and 17 explain what is happening?

§5.3 #20)
Use Cayley's theorem (5.2) to find a subgroup of S₁₂ that is isomorphic to Z₂₁^*.

§5.3 #21)
Use Cayley's theorem (5.2) to find a subgroup of S₁₂ that is isomorphic to the following group:

In [0]:

InitGroup("e")
AddGroupVar("a", "b")
Define(a^3, e)
Define(b^4, e)
Define(b*a, a^2*b)
G = ListGroup(); G

§5.3 #22)
Use the generalized Cayley's theorem (5.3) to find a subgroup of S₈ that is isomorphic to the following group:

In [0]:

InitGroup("e")
AddGroupVar("a", "b")
Define(a^2, e)
Define(b^8, e)
Define(b*a, a*b^5)
G = ListGroup(); G

Hint: Find a subgroup of order 2 that is not normal.

§5.4 #19)
Find the elements of A₄ converted to the integer representation. Is there a pattern as to which positive integers correspond to the even permutations, and which correspond to odd? Does the pattern continue to A₅?

§5.4 #20)
Use Sage to find all elements of S₇ whose square is P(3,5,1,7,6,2,4).
(Hint: Use a "for" loop to test all of the elements of S₇):

In [0]:

for i in range(5040):
   if NthPerm(i)^2 == P(3,5,1,7,6,2,4):
       print(NthPerm(i))

§5.4 #21)
Use Sage to find all elements of S₆ whose cube is P(3,5,6,1,2,4). (See the hint for Problem 20.)

Symmetric Groups

Cycles

Cayley's Theorem

Numbering the Permutations

Proofs:

Sage Problems

Product

Resources

Company

⎛	1	2	3	4	⎞	·	⎛	1	2	3	4	⎞	=	⎛	1	2	3	4	⎞
⎝	2	3	4	1	⎠	·	⎝	1	2	4	3	⎠	=	⎝	2	3	1	4	⎠

⎛	1	2	3	4	⎞	·	⎛	1	2	3	4	⎞	=	⎛	1	2	3	4	⎞
⎝	1	2	4	3	⎠	·	⎝	2	3	4	1	⎠	=	⎝	2	4	3	1	⎠

⎛	1	2	3	4	⎞	·	⎛	1	2	3	4	⎞	=	⎛	1	2	3	4	⎞
⎝	2	3	4	1	⎠	·	⎝	1	2	4	3	⎠	=	⎝	2	3	1	4	⎠

⎛	1	2	3	4	⎞	·	⎛	1	2	3	4	⎞	=	⎛	1	2	3	4	⎞
⎝	1	2	4	3	⎠	·	⎝	2	3	4	1	⎠	=	⎝	2	4	3	1	⎠

⎛	1	2	3	4	⎞	·	⎛	1	2	3	4	⎞	=	⎛	1	2	3	4	⎞
⎝	2	3	4	1	⎠	·	⎝	1	2	4	3	⎠	=	⎝	2	3	1	4	⎠

⎛	1	2	3	4	⎞	·	⎛	1	2	3	4	⎞	=	⎛	1	2	3	4	⎞
⎝	1	2	4	3	⎠	·	⎝	2	3	4	1	⎠	=	⎝	2	4	3	1	⎠