Permutation groups

UPDATE: Since I noticed later that the convention that makes things simplest in group actions is to compose permutations right-to-left, I’ve gone back and tweaked that here.

Today I want to go into an example of a group in a lot more detail. It looks pretty long, so I’ll just put the whole thing behind the jump

A permutation is just a rearrangement. You have some number of things in a row, then the permutation picks them up and shuffles them about. We can write this down by making a table listing first what place in line an object has before the permutation, and then what place it has after.
|1 2 3 4|
|2 1 4 3|
This one — call it — picks up whatever is in slot 1 and puts it into slot 2. Whatever was in slot 2 goes to slot 1. Similarly it swaps the contents of slots 3 and 4.
|1 2 3 4|
|4 2 1 3|
This one — call it — leaves slot 2 alone and cycles the contents of the other three slots: 1 goes to 4 goes to 3 goes to 1.

In each of these, we determine where it puts the contents of a given slot by finding that slot in the top row and reading off the number below it. We can use this method to put together two rearrangements to make a third. For example, if we first do and then do we see that sends what’s in slot 1 to slot 2, which leaves alone. Check the rest of the slots to verify that this composition, which I’ll write as , is expressed as
|1 2 3 4|
|2 4 3 1|
while if we compose in the other order the result is
|1 2 3 4|
|3 1 2 4|
so the order of composition definitely makes a difference. As a side note, some authors write group composition the other way around, so what I call they call and vice versa. It doesn’t really matter in the long run; the important thing is to pick a convention and stick with it. [Actually, originally I had written these the other way around, thinking it would be clearer to read left-to-right. If this convention seems confusing, think of it like function composition: is like .]

Now, that notation above really wastes a lot of space. The whole first line is completely redundant, for instance, and in this medium I can’t write them inline. Here’s another way to write down a permutation: I look at and start with slot 1, writing

Now I see that slot 1 is sent to slot 2, so I write that down

I see that 2 is sent back to 1, which puts me back where I started. I’ll close off this loop and start over with 3.

Now 3 is sent to 4, which goes back to 3, closing off this loop too. Since I’ve used all four slots, I’m done. The expression is

We read one of these from left to right, each slot moving to the next in line, and the one before a closing paren looping around to the beginning again. As another example, becomes . Slot 1 goes to 4 goes to 3 goes back to 1, and slot 2 is left alone. In fact from here we’ll just assume that any slot that doesn’t show up is left alone, so we write as . It’s important to note that the parens here do not denote the same thing as they do in arithmetic, telling which operations to do first. These parens mark out the cycles in the permutation.

We can even use this notation for compositions, reading the permutations from right to left. The composition becomes . Reading this from the right, the first cycle sends 1 to 4, which the second sends to 3 and the third leaves alone. The first cycle sends 3 to 1, and the third sends that to 2. Now 2 makes it all the way through to the third cycle. This produces and 4 must be sent to itself, as it’s the only slot left. The composition in the opposite order gives . See if you can get this result.

Now, every example up until this point has been working with permutations on 4 slots. I’ve shown how to compose such permutations, doing one after the other. Doing nothing also counts as a permutation, and it’s the identity permutation we need. Finally, it should be clear that any permutation can be undone, leaving things as they were before. This means that these permutations form a group which we call for the “symmetric group on 4 elements”. If the permutations shuffled around five things we’d get the group , and so on for any number we can make the group .

These groups have all sorts of nice properties. For one thing, it’s easy to find their size. First we have choices of where to send 1, then we have choices of where to send 2 (since it can’t be sent to the same place we just sent 1), and so on until we only have one choice left where to send . We multiply all these numbers together to get the total number of choices: . We say “ factorial” for this product of all the numbers from 1 to , writing it .

Here’s another neat thing: any permutation can be written as a composition of cycles of length 2. Obviously it can be written in terms of cycles, since that’s the second notation we gave. What I’m saying is that you can break long cycles down into just swaps. For 3-cycles and 4-cycles verify these expressions


and see if you can recognize the general rule.

There are many ways to write a given permutation in terms of swaps, but one thing is always true: the number of swaps needed is either always even or always odd, and we call permutations “even” or “odd” according to which case they fall into, called the “parity” of the permutation. I’m not going to prove this fact here, though it’s not hard to find a proof. This fact turns out to be amazingly significant in all sorts of unexpected ways.

Again I’ll close with a few problems to play with

• The identity permutation is even
• An -cycle is even if is an odd number, and vice versa
• How does the parity of relate to the parities of and ?
• How does the parity of relate to that of ?
• Fill in the details showing that is a group. That is, show that composition is associative, that the identity permutation really behaves like an identity, and that every permutation has an inverse.