Permutation Groups

Let's look at S₁. Its only element is the permutation

          | 1 |
          | 1 |

•	e
e	e

Here e is the permutation that changes element 1 to element 1. It's the only permutation possible and it's group under the operation followed by is a trivial one-element group. In fact, there is (up to isomorphism) only one group with one element. Thus we've found the structure of all one-element groups. (Big deal!)

With two elements there are two (2!) possible permutations

          | 1 2 |             | 1 2 |
          | 1 2 | = e         | 2 1 | = a

•	e	a
e	e	a
a	a	e

This group has the identity e and a non-identity element a. A little reflection on the need for (1) an identity and (2) the cancellation rule and we realize that this table represents all groups of two elements. Thus we've "found" the structure of all groups of order 1 and 2. (Big deal!)

With three elements things begin to become a bit more interesting. S₃ has 3! = 6 elements. They are

         | 1 2 3 |         | 1 2 3 |         | 1 2 3 |
         | 1 2 3 | = e     | 2 3 1 | = a     | 3 1 2 | = b

         | 1 2 3 |         | 1 2 3 |         | 1 2 3 |
         | 1 3 2 | = X     | 3 2 1 | = Y     | 2 1 3 | = Z

A Short Digression Concerning Notation

mean that permutation a is performed first and then permutation b is performed? Or does it mean that b is performed first and then a? Since we read English from left to right there is a strong reason to use the left-most element (in this case, a) as the one performed first. Thus we would read a • b as a followed by b. However in mathematics the notation for operators and functions usually works differently. If f and g are two functions and I want g to act first and then have f act on the result of g's action then the usual notation for this is

Thus the element which operates first (g) is written to the right of the element (f) which operates last. We must therefore be clear in our notation. Since both the leftmost-first and the rightmost-first notations are used in mathematical literature we'll have to decide which we'll use here. By a coin flip it has been determined that we will use the "followed by" notation where the leftmost operation is performed first. Thus a • b will be read as a followed by b; that is, a is performed first followed by performing b.

With this convention decided upon together with the convention for Cayley tables that left element in the operation is in the column to the left of the table and the right element is in the row along the top of the table we get the following table for S₃

•	e	a	b	X	Y	Z
e	.	.	.	.	.	.
a	.	.	.	Y	.	.
b	.	.	.	.	.	.
X	.	Z	.	.	b	.
Y	.	.	.	.	.	.
Z	.	.	.	.	.	.

I've filled in the elements a • X and X • a as well as X • Y (which equals b) in the table. As an exercise the student should work out what goes in the other 33 cells of the table. The solution is given below (no peeking)

.

.

.

.

Well have you finished filling in the table yet?

If not then go back and do it. If so then continue on and check your answers.

.

.

.

.

•	e	a	b	X	Y	Z
e	e	a	b	X	Y	Z
a	a	b	e	Y	Z	X
b	b	e	a	Z	X	Y
X	X	Z	Y	e	b	a
Y	Y	X	Z	a	e	b
Z	Z	Y	X	b	a	e

Does this table look familiar? It's exactly the same table as we gave for the Symmetry Group of the Equilateral Triangle. The two groups are isomorphic. This becomes clear when we realize that any symmetry movement of the equilateral triangle simply permutes the three vertices of the triangle.

[Exercise: Write out the Caley tables for S₄ and S₅.]

[Just kidding! S₄ would have 576 entries in its Cayley table and S₅ would have 14,400 entries.]

The Symmetric Group on n objects, S_n consists of all permutations on the n objects. If we limit ourselves to even permutations then we get an object called The Alternating Group on n Objects. From the name you can guess that the set of even permutations of n objects forms a group under the "followed by" operation. In fact this is true. The fact that e the identity permutation is even and that the product of two even permutations is an even permutation as well as the fact that the inverse of an even permutation is an even permutation makes the Alternating Group on n Objects a subgroup of S_n.

The Alternating Group on n Objects has the symbol A_n. And since we know that there are n! permutations (even and odd) in S_n then there must be exactly half that many in A_n. Or does that need to be proven? Hmmm . . .

Theorem: The order of A_n is half the order of S_n.

Proof: The way to prove this is to find a one-to-one correspondence between the even permutations and the odd permutations. Since the even and odd permutations combine to make S_n then if there are as many evens as odds the evens must be half of the whole.

The trick is to prepend the transposition (1, 2) to the beginning of an even permutation and thereby turn it into an odd permutation. If this gives a one to one correspondence between the even permutations and the odd permutations then we've done it.

But what about those odd permutations that don't "begin" with (1, 2)? Actually there are many different ways to write any permutation. Appending (1,2)(1,2) (which, by the way, is the identity permutation) to the front of a permutation (or even inserting it anywhere in the middle) will not change the permutation. Thus any permutation can be written with (1, 2) at its front.

This is the correspondence we seek. Appending (1, 2) to the beginning of any even permutation gives an odd permutation. Also, we may write any odd permutation beginning with (1, 2) so by removing the (1, 2) from the beginning gives an even permutation. Replacing (1, 2) at the beginning gives us back the odd permutation again. Thus we have found that every even permutation corresponds to exactly one odd permutation under this "transformation" of appending (1, 2) to the beginning and every odd permutation is corresponded to by exactly one even permutation by this method.

Using this Theorem we know now that there are exactly 3 (half of 3!) even permutations on 3 objects.

Why are permutations so important? Let's look at that question from another viewpoint. Let's define a group function. That is, a function whose domain is the elements of a group G and whose range is also the elements of G. Call this function f_a where a is an element of the group G. The action of this function is to multiply any element of G on the right by a. Thus for any elements x, y or z of G we have

For any other element, say b, of G we can also define f_b(x) = xb for all x in G. Now what are these functions? They are nothing other than permutations on the elements of G. To see this we only need notice that f_a(x) = f_a(y) means that xa = ya and by the cancellation law this means that x = y. Also for any element c of G, c = a(a^-1c). That is, there is some element of G (namely a^-1c) that f_a sends to c. Therefore for every element a of G the function f_a is one-to-one and onto--the exact definition of a permutation.

Now we can ask ourselves, "how do these functions behave under composition--under the operation followed by?" The answer is exactly like the elements of G under its group operation. To see this notice that for any element x of G

[Remember, f_a(f_b(x)) means that f_b acts on x first "followed by" f_a acting on the result of that. This is equivalent to f_b • f_a in our followed-by notation.] The repeated operation of the functions is equivalent to repeated multiplication on the right by the corresponding group element. The functions/permutations not only form a group under the operation of composition ("followed by") but that the group that they form is isomorphic to the original group G. This result is known as Cayley's Theorem:

Cayley's Theorem: Every Group is isomorphic to a group of permutations.

Cycle Notation

       | 1 2 3 4 5 |
       | 3 5 4 2 1 |

1 goes to 3 which goes to 4 which goes to 2 which goes to 5 which goes to 1 completing the cycle. In cyclic notation this would be written.

        (1 3 4 2 5)

Where each element is followed by the one whose place it goes to. The 5 at the end goes back to the 1 at the beginning of the cycle. Now consider the following permutation:

       | 1 2 3 4 5 6 7 8 |
       | 3 5 7 8 4 2 1 6 |

If we begin with 1 we note that 1 goes to 3 which goes to 7 which goes back to 1. Thus we have the cycle (1 3 7). Now we take one of the elements that isn't in the cycle just found, say, 2. 2 goes to 5 which goes to 4 which goes to 6 which goes back to 2. This gives the cycle

     (2 5 4 8 6)

Thus we have broken the permutation into two cycles, (1 3 7) and (2 5 4 8 6). There are a few things we should notice about this decomposition into cycles.

The cycles are disjoint.

They have no element in common. This is clear because once we find a cycle in a permutation we have found where every element in the cycle goes under the permutation. The "destination" of every element of the cycle is in the cycle. Also the elements that have things in the cycle as their destination are also in the cycle. Thus once we close out a cycle by bringing it back to its first element we have found everything that the permutation does to the elements of that cycle and that they are in that cycle. If an element of one cycle was in another cycle then there would be two (at least) elements that that element was mapped onto by the permutation.

So we can decompose any finite permutation into disjoint cycles. Just choose an element see where it goes and then see where that element goes and on until you close out the cycle. Now if there are any elements that are not in that cycle choose one of those and see where it goes etc. until you close out a second cycle. If there are any remaining elements that are not in either of those two cycles choose one of them and continue constructing cycles until you've exhausted all the elements of the permutation. This gives us the result that

Theorem: Every permutation can be decomposed into disjoint cycles.

When we combined permutations with the binary operation "followed by" we found that the order of the permutations mattered. Thus performing

     | 1 2 3 |
     | 2 3 1 |

     | 1 2 3 |
     | 2 1 3 |

was different that performing them in the reverse order. In cyclic notation this would be (1 2 3) followed by (1 2). Let's work out the final permutation from the cyclic notation. In (1 2 3) followed by (1 2) the first cycle takes 1 to 2 and the second cycle takes 2 to 1 so the result is that over all 1 goes to 1. The first cycle takes 2 to 3 and the second cycle does not operate on 3 so the overall effect is to take 2 to 3. finally the first cycle takes 3 to 1 and the second cycle takes 1 to 2 for the overall effect of taking 3 to 2. Thus the result of the combination of the two permutations is (2 3).

If we apply them in reverse order, (1 2) followed by (1 2 3) the result is (1 3) [work this out!]. The order of permutations matters. The group S₃ is not Abelian. However if two cycles are disjoint then they will commute. If the elements moved around by permutation a have no elements in common with those moved around by permutation b then which is performed first doesn't matter. Each cycle operates on different elements so their actions are independent of each other. They live in different worlds as it were. Thus performing a after performing b will have no affect on the elements permuted by a. Thus:

Theorem: Disjoint permutations commute.

So when we decompose a permutation into disjoint cycles the order of applying those cycles does not matter.

Now let's study the cycles themselves. The simplist cycle would be (1) which is the identity. Element 1 goes to 1 and the others are unaffected. This is just the identity permutation.

The next simplist is a cycle of length 2, (1 2) This is just a transposition. Next let's look at a three cycle: (1 2 3) This is equivalent to two transpositions: (1 2) followed by (1 3) [try it!]. Thus (1 2 3) is the product of two transpositions and is an even permutation. Let's consider a four cycle: (1 2 3 4) This is equivalent to (1 2) followed by (1 3) followed by (1 4) [try it!]. Thus it is the product of three transpositions and is therefore an odd permutation. Notice that to get from (1 2 3) to (1 2 3 4) we just had to perform one more permutation at the end, namely (1 4). Similarly to (1 2 3 4 5) = (1 2 3 4) followed by (1 5) [try it!]. Continuing on we see that (1 2 3 . . . n) followed by (1 n+1) gives (1 2 3 ... n n+1) [try it!]. Thus by mathematical induction we come to the conclusion that

Theorem: A cycle with an even number of elements is an odd permutation. and a cycle with an odd number of elements is an even permutation.

So once we have expressed a permutation as the product of disjoint cycles we can determine whether it is an even or odd permutation by noticing the number of cycles with an even number of elements. Since they contribute an odd number of transpositions to the permutation the total parity of transpositions, even or odd, will depend on the number of permutations with an even number of elements. We see that

Theorem: If a permutation is decomposed into disjoint cycles such that there is an odd number of cycles with an even number of elements then the permutation is odd. If there is an even number of cycles with an even number of elements then the permutation is even.

Rubik's Cube
Back to the Index

© 1998 by Arfur Dogfrey