I don’t have too much to say about permutations, but there are two points that I have often found myself needing to get straight in supervisions. In fact, make that three. Here they are. [Added later: I have just finished the post, and it ended up being longer than I expected.]
1. The first is a confusion that some people have about what a permutation of actually is. What could possibly be the trouble, you might ask? Well, let's take the permutation that in cycle notation is written . My guess is that a non-negligible percentage of people reading this have worried about whether this permutation means that you cycle round the elements 1, 2 and 4 of the set or the elements in the places 1, 2 and 4.
Before I go any further, let me say precisely what each of these alternatives means. To make sense of the first idea, we imagine placing the numbers in a line. Then if we want to apply the permutation , we simply replace the number 1 by 2, the number 2 by 4, and the number 4 by 1. If we now want to apply the permutation , say, we look for the numbers 4 and 5 (wherever they might be) and swap them. Also, if we started with the numbers in their usual order — that is, running from 1 to — and want to know what the composition of all the permutations we’ve done so far is, we simply say that 1 maps to whatever is now in the first place, 2 maps to whatever is in the second place, and so on all the way up to .
Let me illustrate this with and those two permutations. I start with the numbers arranged as follows: 1 2 3 4 5 6. After doing the permutation the numbers are arranged as 2 4 3 1 5 6. Now if I do the permutation I have to swap 4 and 5, so I do so and obtain the arrangement 2 5 3 1 4 6. This is the permutation that sends 1 to 2, 2 to 5, 3 to 3, 4 to 1, 5 to 4 and 6 to 6. In cycle notation it is . (If you can’t see that quickly, then read on.)
Now let’s see what would have happened if instead of switching the numbers indicated, we had switched the numbers in the places indicated. We start with 1 2 3 4 5 6, and “apply ” to obtain 4 1 3 2 5 6. What I’ve done is move 1 to 2′s old place, 2 to 4′s old place, and 4 to 1′s old place. Now we interpret the second permutation as switching the numbers in the places 4 and 5, so we obtain this arrangement: 4 1 3 5 2 6. In cycle notation, this is the permutation , which is the inverse of the answer in the first interpretation. As we shall see, that is not a coincidence. (I ought to add that I’ve slightly cheated here: the cycle notation is if we interpret the cycle in the correct way, but if we interpret it in the moving-numbers-in-places way then we would argue that the cycle notation of this permutation is in fact . However, it is correct that the two permutations are inverses of each other.)
So which is the right interpretation of what a permutation means? It is the first. Here are several reasons that that not only is the case but clearly must have been the case.
First, suppose we decided that we wanted to permute not the numbers from 1 to but the elements of some other set. One simple example might be a different set of numbers, such as . Now we see that the permutation makes perfectly good sense if we think of switching numbers around, and no sense at all if we think of switching numbers in places around.
A second reason is that a permutation is defined as a bijection of a set. When we take a set, we don’t have to arrange its elements in a line. If we did have to, it would be an ordered set that we were talking about. So the switching-numbers interpretation makes sense for the set even if those numbers are scattered around in space, or put down in a funny order, or just not in any kind of “space” at all.
Is that the end of the story? I think it isn’t enough just to say, “If you thought permutations were about where the numbers are, then you were wrong: go away and learn the definition properly.” That isn’t terrible advice, but somehow it’s a bit unfriendly, and misses an opportunity to talk about some interesting mathematics. Here are two questions that are worth discussing.
(i) What is it that causes this particular confusion?
(ii) Is there any interesting relationship between the two ways of thinking about permutations? After all, even if the second one isn’t correct, it still makes sense.
I’ll tackle (ii) first. To begin with, I’d like to try to describe the “moving objects in certain places” idea in a mathematically precise way. To do that, let us define an ordering of the set to be an ordered -tuple that consists of the numbers 1 to in some order. For example, the orderings of the set are . (A little exercise if you feel so inclined: what would be an economical way of describing the order in which I wrote those six orderings, and then generalizing it to orderings of larger sets of integers?)
Now, given a permutation of the set we want to interpret it as something that moves objects that are sitting in certain places. We can do that as follows. I’ll give an example and then say in general what I’m doing.
Let’s take and let’s take the permutation . I want to think of it as the function that takes an ordering of the set and moves whatever is in the first place to the third place, whatever is in the third place to the fourth place, and whatever is in the fourth place to the first place. So for example, if I apply my permutation to the ordering I get the ordering . If I apply it to the ordering I get the ordering . And so on.
What’s going on in general? Well, an ordering of the set takes the form for some bijection from to itself. But hang on, bijections from to itself are just permutations. So let’s write for a typical ordering instead.
Now let’s take a permutation and use it in the objects-in-certain-places sense. That is, for each I take the object in the th place and move it to the object in the th place. That is, I move (which is currently in the th place) to the place .
If I do that, then what object ends up in the first place? I need to find such that , and then the object in question is for that . Well, the with is . It follows that in my notation for orderings, the object in the first place is going to be . That argument obviously works for all numbers, so the eventual ordering is .
In other words, if I want to apply in a moving-places way to an ordering defined by a permutation, I need to multiply that permutation on the right by to get the permutation that defines the new ordering.
Let’s check that for the example we had earlier. There we started with the ordering and used the permutation to switch certain places around. The result was the ordering . What have we got in the first place here? We have 4, which is not the image of 1 under the permutation but the image of 1 under the inverse of the permutation , exactly as we wanted.
Next, we used the permutation to switch the numbers in places 4 and 5. That gave us the ordering . What appears in the fifth place here? It should be the inverse of applied to the inverse of applied to the number 5. OK, take 5 and apply the inverse of . It gives us 4. Now take 4 and apply the inverse of . That gives us 2. Do we have 2 in the fifth place? Yes we do.
The main thing to take out of this is that if you start with the “identity ordering” and use a permutation to switch objects in certain places rather than the objects themselves, what you are actually doing is applying the inverse of the permutation . But you have to be a little careful here. If you then apply a permutation in the moving-places sense, the objects are no longer in their original positions. What that means is that the permutation we end up applying after the two operations is not (which means do first and then ) but rather .
However, this isn’t too surprising. It tells us that if we do the operation associated with and then the operation associated with , we end up doing the operation associated with . (Later, when you have covered group actions, I will be able to explain all this much more concisely.)
I don’t feel confident that I’ve found the neatest and clearest explanation of the relationship, even if I don’t allow myself to talk about group actions, but if you are still not clear in your mind how the two ways of getting permutations to do things are related, then I recommend spending some time trying to work it out for yourself. But you may also find what I’m about to say about question (i) helpful too, which is that there is a very good reason that people find themselves wondering whether the moving-objects-between-places viewpoint is the right one.
One of the things you will be told soon, if you haven’t been told it already, is that the permuation group , which consists of all permutations of the set , is isomorphic to the symmetry group of an equilateral triangle. Here’s the rough reason for that. If you take an equilateral triangle and number its three vertices 1, 2 and 3, then any symmetry swaps those three vertices around, and conversely any of the six ways of swapping those three vertices around can be achieved by means of a symmetry. (For example, if we reflect in the line that goes through vertex 1 and the centre of the triangle, then we end up swapping vertices 2 and 3.)
Let’s try to be more precise about this. The symmetries of an equilateral triangle are three reflections and three rotations (counting the identity map as a rotation through an angle of zero). Which permutation of the set should correspond to which symmetry? For example, if the triangle has a horizontal base, which permutation corresponds to a reflection through a vertical line that cuts the triangle in half?
To answer this we should think about what that reflection does to the vertices, and to think about that we should probably number the vertices. Perhaps the vertex at the top could be number 1, the bottom left one could be number 2 and the bottom right one could be number 3. So reflecting in a vertical line through the top vertex looks as though it ought to correspond to the permutation .
How about a rotation through 120 degrees anticlockwise? That takes vertex 1 to vertex 2, vertex 2 to vertex 3 and vertex 3 to vertex 1. Does that mean that the corresponding permutation is ? Let’s suppose it does. If we do that rotation first, then how do we reflect in a vertical line? Now the vertex 3 is at the top, so does that mean that reflection in a vertical line has suddenly become the permutation instead of ?
We’re starting to get into a muddle, and the muddle is precisely the one I’ve been talking about. If we think of the symmetries of a triangle as things like “reflect in a vertical line through the top vertex” then what we care about is not what the number of that vertex happens to be, but the place at the top. So we can’t think of “reflect in a vertical line through the top vertex” as mapping vertex number 2 to vertex number 3 and vertex number 3 to vertex number 2.
So is it correct that the symmetry group of a triangle is isomorphic to the permutation group of the set ? Yes it is, but the isomorphism isn’t quite what you think. First you have to number the possible positions of the vertices as 1, 2 and 3, and then a permutation such as corresponds to the map that sends the vertex in position 1 to the vertex in position 3, the vertex in position 3 to the vertex in position 2, and the vertex in position 2 to the vertex in position 1. What it doesn’t correspond to is the map that takes the vertex labelled 1 to the vertex labelled 3, etc.
This is actually the same phenomenon as one you will have come across at school. If you have a graph of a function and you want to translate it to the right by , it’s natural to think that what you ought to do is take the graph of the function . However, this is wrong: you need to take the graph of the function . Why? Well, if you want the values taken by the function to move to the right, you want the value of the new function at to be the value of at . Similarly, if you want to rotate the labels of the vertices of a triangle through 120 degrees anticlockwise, then you want the new label at a vertex to be the old label at the vertex 120 degrees clockwise from it.
What is the take-home message from all this? The main one is that if you are ever confused by the notion of a permutation, then simply replace the phrase “permutation of ” by “bijection from to “. If you do that, then you won’t be tempted to think that the statement means that you are moving the object in place to place . But a secondary message is that we often do move objects according to where they are rather than what they are, and as long as you are careful you can represent this with permutations as well.
2. The second point I wanted to make was one that applies much more generally than just to permutations. It’s that there is an important distinction between proofs that tell you that something can be done, and proofs that tell you how to do it. In your lectures, you were told about the cycle notation for permutations. So a fact that you should now be aware of is this.
However, the only proofs I can think of of this fact tell you more: they explain how to work out what those disjoint cycles are. And while that means that your lecturer is pretty well guaranteed to have told you how to work out the cycle representation of a permutation, I think it’s worth emphasizing just how easy this algorithm is to apply.
To illustrate this, let me give two examples. The first involves arithmetic mod 15. I’m not sure whether you’ve got on to this in Numbers and Sets, but if you haven’t, it’s not a problem. All you have to understand to follow what I’m about to say is that I am going to define a function from to itself by taking to be the result of multiplying by 7 and taking the remainder on division by 15. For example, to work out we multiply by 7 to get 56, and since we find that .
For reasons that will soon be explained to you if they haven’t already, is a bijection, or we could if we like call it a permutation. I chose it because it is not defined as a product of disjoint cycles, so if we want to show that it is a product of disjoint cycles, then we have to work something out.
Here’s how to do it. Start with 0. Since , we end up with a cycle of length 1, which in cycle notation one doesn’t usually bother to write down. So that’s dealt with one cycle. Now let’s take the smallest number we haven’t yet dealt with, which is 1. Multiplying that by 7 gives us 7, which is smaller than 15, so . That tells us we’ve got a cycle of length greater than 1, so let’s start writing it out: . Next we work out , which is 4, since , which means that we can write out more of the cycle, obtaining . Continuing, we find that and . Once we’ve got back to 1, we have finished the cycle. Since 13 is a two-digit number, let me put in commas for the sake of clarity: we end up writing the cycle . (This means that 1 goes to 7 goes to 4 goes to 13 goes to 1.)
The smallest number we haven’t yet dealt with is 2, so off we go. A moment’s thought tells us that our numbers will be twice the numbers in the previous cycle, except that twice 13 will be 11 after we have taken the remainder on division by 15. So we get the cycle . Next we deal with 3. Multiplying the first cycle by 3 (and taking remainders if necessary) gives us . Now the smallest number we haven’t dealt with is 5. If we multiply everything in the first cycle by 5, we get . That looks a bit odd, perhaps: it demonstrates the fact that the cancellation law is not valid for multiplication by 5 mod 15. For the purposes of the cycle representation it tells us that 5 is part of a 1-cycle for this permutation, and the same will apply to 10. Therefore, the cycle representation of the entire permutation is .
The second example is a product of three cycles that are not disjoint. Suppose I give you the permutation and ask you to write it in cycle notation. That requires disjoint cycles, so we have to do something. With a bit of experience, you can simply write down the answer with no working at all. Let me do so, and then I’ll say what I did. The answer is . How did I get that? I simply followed the procedure above: I started by seeing what 1 went to, then what that went to, and so on. When I completed the first cycle, I found that 3 was the smallest number I hadn’t yet discussed, so I saw what that went to, then what that went to, etc. The result was the product of three disjoint cycles above.
How did I see what the various numbers went to? The one thing to remember here is that the cycles represent functions and if you are given a composition of functions then you start from the right. So if we want to know what 3 goes to when we do the permutation we first look at the rightmost bracket, which sends 3 to 4. Then we look at the middle bracket, which sends 4 to 6, and finally we look at the first bracket, which doesn’t do anything to 6. That tells us that the above permutation sends 3 to 6. It is easy to do that kind of calculation in one’s head, which is why it is easy to write down the disjoint cycle representation of a permutation when it is given in another form.
3. The third point I wanted to discuss was conjugating permutations. I plan to have a post about conjugation later, but basically conjugation is to do with expressions like , which come up all over the place in mathematics. (Why? That is what I want to explain in the post on conjugation.)
We sometimes like to conjugate permutations, so it is useful to know how to work out what is when and are given permutations. What’s more, the answer is very easy.
Let me illustrate it with an example that is half abstract and half concrete. I’d like to ask what the cycle representation is of the permutation . In other words, I’m setting and I’m not telling you what is.
To work this out, we apply the same method yet again, but with a slight twist. This time I don’t find it all that easy to say what 1 goes to. However, I do find it easy to say what goes to. Working from the right, we first apply , which takes to 1. Next we apply , which takes 1 to 3. And finally we apply , which takes to . So goes to . What does go to? Exactly the same argument shows that it goes to , and a clear pattern emerges: if sends to , then sends to . (Just try it: goes to , which goes to , which goes to .) That tells us that to get the cycle representation of , we just take the cycle representation of and do to everything. In our example we start with the permutation and the end result is the permutation .
Now let me make the example completely concrete by taking to be the 4-cycle . The rule above tells us that we take the cycle representation and change 1 to 2, 2 to 3, 3 to 4 and 4 to 1. That is,
which we might prefer to write as .
An important general fact that this rule tells us is that the cycle type of a permutation is unaffected by conjugation. (The cycle type means the information about how many cycles there are of each length.) That tells me, for example, that there is no with the property that . On the other hand, if I want to find a permutation such that , there is no problem. All I need is some permutation that will take 1 to 3 and 2 to 4. A permutation that will do the job is . Another is . Why this is useful to know will become clear only later in the course.