Permutations

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 $\{1,2,\dots,n\}$ actually is. What could possibly be the trouble, you might ask? Well, let's take the permutation that in cycle notation is written $(124)$ . 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 $\{1,2,\dots,n\}$ 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 $(124)$ , 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 $(45)$ , 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 $n$ — 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 $n$ .

Let me illustrate this with $n=6$ and those two permutations. I start with the numbers arranged as follows: 1 2 3 4 5 6. After doing the permutation $(124)$ the numbers are arranged as 2 4 3 1 5 6. Now if I do the permutation $(45)$ 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 $(1254)$ . (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 $(124)$ ” 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 $(45)$ 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 $(1452)$ , 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 $(1452)$ 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 $(1254)$ . 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 $n$ but the elements of some other set. One simple example might be a different set of numbers, such as $\{1,3,5,7,9\}$ . Now we see that the permutation $(579)$ 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 $\{1,2,\dots,n\}$ 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 $\{1,2,\dots,n\}$ to be an ordered $n$ -tuple that consists of the numbers 1 to $n$ in some order. For example, the orderings of the set $\{1,2,3\}$ are $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$ . (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 $\pi$ of the set $\{1,2,\dots,n\}$ 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 $n=4$ and let’s take the permutation $(134)$ . I want to think of it as the function that takes an ordering of the set $\{1,2,3,4\}$ 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 $(134)$ to the ordering $(2,1,4,3)$ I get the ordering $(3,1,2,4)$ . If I apply it to the ordering $(3,2,4,1)$ I get the ordering $(1,2,3,4)$ . And so on.

What’s going on in general? Well, an ordering of the set $\{1,2,\dots,n\}$ takes the form $(f(1),f(2),\dots,f(n))$ for some bijection $f$ from $\{1,2,\dots,n\}$ to itself. But hang on, bijections from $\{1,2,\dots,n\}$ to itself are just permutations. So let’s write $(\sigma(1),\dots,\sigma(n))$ for a typical ordering instead.

Now let’s take a permutation $\pi$ and use it in the objects-in-certain-places sense. That is, for each $k$ I take the object in the $k$ th place and move it to the object in the $\pi(k)$ th place. That is, I move $\sigma(k)$ (which is currently in the $k$ th place) to the place $\pi(k)$ .

If I do that, then what object ends up in the first place? I need to find $k$ such that $\pi(k)=1$ , and then the object in question is $\sigma(k)$ for that $k$ . Well, the $k$ with $\pi(k)=1$ is $\pi^{-1}(1)$ . It follows that in my notation for orderings, the object in the first place is going to be $\sigma(\pi^{-1}(1))$ . That argument obviously works for all numbers, so the eventual ordering is $(\sigma(\pi^{-1}(1)),\sigma(\pi^{-1}(2)),\dots,\sigma(\pi^{-1}(n)))$ .

In other words, if I want to apply $\pi$ in a moving-places way to an ordering defined by a permutation, I need to multiply that permutation on the right by $\pi^{-1}$ 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 $(1,2,3,4,5,6)$ and used the permutation $(124)$ to switch certain places around. The result was the ordering $(4,1,3,2,5,6)$ . What have we got in the first place here? We have 4, which is not the image of 1 under the permutation $(124)$ but the image of 1 under the inverse of the permutation $(124)$ , exactly as we wanted.

Next, we used the permutation $(45)$ to switch the numbers in places 4 and 5. That gave us the ordering $(4,1,3,5,2,6)$ . What appears in the fifth place here? It should be the inverse of $(124)$ applied to the inverse of $(45)$ applied to the number 5. OK, take 5 and apply the inverse of $(45)$ . It gives us 4. Now take 4 and apply the inverse of $(124)$ . 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” $(1,2,\dots,n)$ and use a permutation $\sigma$ to switch objects in certain places rather than the objects themselves, what you are actually doing is applying the inverse $\sigma^{-1}$ of the permutation $\sigma$ . But you have to be a little careful here. If you then apply a permutation $\pi$ 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 $\pi^{-1}\sigma^{-1}$ (which means do $\sigma^{-1}$ first and then $\pi^{-1}$ ) but rather $\sigma^{-1}\pi^{-1}$ .

However, this isn’t too surprising. It tells us that if we do the operation associated with $\sigma$ and then the operation associated with $\pi$ , we end up doing the operation associated with $\pi\sigma$ . (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 $S_3$ , which consists of all permutations of the set $\{1,2,3\}$ , 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 $\{1,2,3\}$ 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 $(23)$ .

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 $(123)$ ? 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 $(12)$ instead of $(23)$ ?

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 $\{1,2,3\}$ ? 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 $(132)$ 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 $y=f(x)$ and you want to translate it to the right by $t$ , it’s natural to think that what you ought to do is take the graph of the function $y=f(x+t)$ . However, this is wrong: you need to take the graph of the function $y=f(x-t)$ . 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 $x$ to be the value of $f$ at $x-t$ . 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 $X$ ” by “bijection from $X$ to $X$ “. If you do that, then you won’t be tempted to think that the statement $\pi(n)=m$ means that you are moving the object in place $n$ to place $m$ . 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.

Every permutation of a finite set is a product of disjoint cycles.

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 $\pi$ from $\{0,1,2,\dots,14\}$ to itself by taking $\pi(x)$ to be the result of multiplying $x$ by 7 and taking the remainder on division by 15. For example, to work out $\pi(8)$ we multiply by 7 to get 56, and since $56=3\times 15+11$ we find that $\pi(8)=11$ .

For reasons that will soon be explained to you if they haven’t already, $\pi$ 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 $\pi(0)=0$ , 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 $\pi(1)=7$ . That tells us we’ve got a cycle of length greater than 1, so let’s start writing it out: $(17$ . Next we work out $\pi(7)$ , which is 4, since $7\times 7=45+4$ , which means that we can write out more of the cycle, obtaining $(174$ . Continuing, we find that $\pi(4)=13$ and $\pi(13)=1$ . 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 $(1,7,4,13)$ . (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 $(2,14,8,11)$ . Next we deal with 3. Multiplying the first cycle by 3 (and taking remainders if necessary) gives us $(3,6,12,9)$ . Now the smallest number we haven’t dealt with is 5. If we multiply everything in the first cycle by 5, we get $(5,5,5,5)$ . 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 $(1,7,4,13)(2,14,8,11)(3,6,12,9)$ .

The second example is a product of three cycles that are not disjoint. Suppose I give you the permutation $(1234)(2468)(347)$ 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 $(12)(368)(47)$ . 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 $(1234)(2468)(347)$ 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 $ABA^{-1}$ , 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 $\pi\sigma\pi^{-1}$ is when $\pi$ and $\sigma$ 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 $\pi(1356)(24)\pi^{-1}$ . In other words, I’m setting $\sigma=(1356)(24)$ and I’m not telling you what $\pi$ 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 $\pi(1)$ goes to. Working from the right, we first apply $\pi^{-1}$ , which takes $\pi(1)$ to 1. Next we apply $\sigma$ , which takes 1 to 3. And finally we apply $\pi$ , which takes $3$ to $\pi(3)$ . So $\pi(1)$ goes to $\pi(3)$ . What does $\pi(3)$ go to? Exactly the same argument shows that it goes to $\pi(5)$ , and a clear pattern emerges: if $\sigma$ sends $a$ to $b$ , then $\pi\sigma\pi^{-1}$ sends $\pi(a)$ to $\pi(b)$ . (Just try it: $\pi(a)$ goes to $a$ , which goes to $b$ , which goes to $\pi(b)$ .) That tells us that to get the cycle representation of $\pi\sigma\pi^{-1}$ , we just take the cycle representation of $\sigma$ and do $\pi$ to everything. In our example we start with the permutation $(1356)(24)$ and the end result is the permutation $(\pi(1)\pi(3)\pi(5)\pi(6))(\pi(2)\pi(4))$ .

Now let me make the example completely concrete by taking $\pi$ to be the 4-cycle $(1234)$ . The rule above tells us that we take the cycle representation $(1356)(24)$ and change 1 to 2, 2 to 3, 3 to 4 and 4 to 1. That is,

$(1234)(1356)(24)(1234)^{-1}=(2456)(31)$ ,

which we might prefer to write as $(2456)(13)$ .

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 $\pi$ with the property that $\pi(12)\pi^{-1}=(123)$ . On the other hand, if I want to find a permutation $\pi$ such that $\pi(12)\pi^{-1}=(34)$ , 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 $(13)(24)$ . Another is $(1324)$ . Why this is useful to know will become clear only later in the course.

This entry was posted on October 16, 2011 at 5:32 pm and is filed under Cambridge teaching, IA Groups. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

40 Responses to “Permutations”

Terence Tao Says:
October 17, 2011 at 12:16 am | Reply
I think the main reason permutation notation is so confusing is that mathematicians tend to interpret transformations as active transformations by default, whereas other disciplines (most notably physics) tend to assume transformations are passive by default instead. (And computer programmers are split down the middle, at least when it comes to graphical user interfaces. For instance, does the “+” button in your viewer zoom in or out? Does the “up arrow” move the text up, or the text down? Different graphical applications do different things in this regard.)

Further complicating the issue is that a significant minority of mathematics prefer groups to act on the right rather than on the left, and to make functions appear after their inputs, instead of before. This tends to flip the active/passive distinction. (For instance, permutations that are interpreted actively on the left, should be interpreted passively on the right.)

I discussed these issues a bit at

https://plus.google.com/114134834346472219368/posts/AWqcUGXVjcs

Unfortunately I don’t see a way out of the lack of consensus on default notations here, other than to be very clear when it comes to definitions.
John Sidles Says:
October 17, 2011 at 11:02 am | Reply
The multi-index tensor function “Transpose[]” in Mathematica explicitly acts (in Tim’s phrase) “to move objects according to where they are rather than what they are”, and yet even in this case reasonable people can differ regarding the natural result of “Transpose[aThreeTensor,{3,1,2}]”.

Hmmm … which index of “aThreeTensor” should end-up in position 3?
Dactyl Says:
October 17, 2011 at 1:43 pm | Reply
I respectfully disagree with this statement:

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.

But, I am a mere student, and I have always used the latter interpretation, so let me make my case if for no other reason than to let someone point at the knots in my thinking which I am currently blind to.

1)
You write:

First, suppose we decided that we wanted to permute not the numbers from 1 to n but the elements of some other set. One simple example might be a different set of numbers, such as \{1,3,5,7,9\}. Now we see that the permutation (579) 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.

But, then I can counter:

First, suppose we decided that we wanted to permute not the numbers from 1 to n but the elements of some other set. One simple example might be a different set of numbers, such as \{1,3,5,7,9\}. Now we see that the permutation (24) makes perfectly good sense if we think of switching numbers in places around, and no sense at all if we think of switching numbers around.

In fact, switching numbers in places around always make sense since we label places with numbers, whereas we could be thinking of applying (135) to (x,y,z,w,t,s).
What I am trying to get at is: it makes sense that the symbol we use to represent a function should be independent of the symbols we represent the elements that will be its input.

2)
You write:

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……

Let’s take n=4 and let’s take the permutation (134). I want to think of it as the function that takes an ordering of the set \{1,2,3,4\} 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 (134) to the ordering (2,1,4,3) I get the ordering (3,1,2,4). If I apply it to the ordering (3,2,4,1) I get the ordering (1,2,3,4). And so on….

Now, whatever be the various permutations of {1,2,3,4,5}, if we think of the permutation represented as a cycle in either of your two senses (as entry to entry or as place to place) as a matrix that takes input the vector which is a particular ordering, then the matrix remains the same wrt any ordering. And we find the matrix according to the ‘move objects in place i to place j’ rule applied to the identity matrix, where the objects in question are the rows, instead of the entry to entry interpretation since the entries in this case are not numbers but rows of numbers.
gowers Says:
October 17, 2011 at 3:52 pm | Reply
@Dactyl: There are many things I could say here. One is a different point I made in the post, which is that permutations are applied to sets. Since the set $\{1,3,5,7,9\}$ is the same as the set $\{5,1,3,9,7\}$ , if we adopt your idea of making $(24)$ stand for some permutation, I would suggest that it doesn’t make sense after all, because it depends on how you write out the set, rather than depending on the set itself.

As I argued in the post, the moving-places idea isn’t incoherent. It’s just that it definitely doesn’t correspond to the standard definition of a permutation as a bijection from a set to itself.

What I am trying to get at is: it makes sense that the symbol we use to represent a function should be independent of the symbols we represent the elements that will be its input.

What I would say here is that $\{1,3,5,7,9\}$ isn’t a different set of symbols representing the same objects as $\{1,2,3,4,5\}$ : it’s a completely different set.
Dactyl Says:
October 17, 2011 at 6:11 pm | Reply
@gowers:

I think I see where I’m going wrong — I am confusing ‘bijection of indices’ with ‘bijection of a set’. Thank you and sorry for the silliness. I really should quit maths (and thank god for the anonymity on the internet)
Gareth Says:
October 17, 2011 at 7:55 pm | Reply
I usually try to explain the difference between a permutation moving the elements ” and “moving the elements in the places” in terms of labelled balls in labelled buckets.

Suppose that we have balls labelled 1 to n, living in buckets labelled 1 to n. When we apply the cycle (123…n), we have two options, namely whether to apply it to the labels on the balls or the buckets.

(a) Replace ball 1 with ball 2, replace ball 2 with ball 3, …, replace ball n with ball 1. Equivalently, replace ball 1’s label with the label “2”, ball 2’s with “3”, …, and ball n’s with “1”. Afterwards, we see the order 2, 3, …, n, 1.

(b) Move the contents of bucket 1 to bucket 2, of bucket 2 to bucket 3, …, of bucket n to bucket 1. This is equivalent to replacing bucket 1’s label with the label “2”, bucket 2’s with “3”, …, and bucket n’s with “1”. Why? Because our operation resulted in the ball labelled 1 living in the bucket labelled 2, which could be achieved equally well by renaming the bucket. Afterwards, we see the order n, 1, 2, …, n-1.

The inverse behaviour then appears as a relative-point-of-view thing. In (a), we see a ball moving to the left – the ball labelled 2 moved from bucket 2 to bucket 1, for example. But from the ball’s point of view, the bucket underneath it moved off to the right – bucket 2 wandered off to go and contain ball 3 instead. This is the opposite behaviour seen in (b), where we see the ball move to the right.

To compare, let’s apply the permutation $f$ in both interpretations.

We start with:

$\begin{array}{ccccc} ball&1&2&3&\ldots\\ bucket&1&2&3&\ldots\end{array}$

Interpretation (a) gives:

$\begin{array}{ccccc} ball & f(1) & f(2) & f(3) & \ldots\\ bucket & 1 & 2 & 3 & \ldots\end{array}$

Interpretation (b) gives:

$\begin{array}{ccccc} ball & 1 & 2 & 3 & \ldots\\ bucket & f(1) & f(2) & f(3) & \ldots\end{array}$

Since all we care about is “which ball is in which bucket”, which could move things around to tidy up, keeping each ball in its current bucket – i.e., not an actual permutation. E.g., if we see “ball 1 in bucket 2” to the left of “ball 2 in bucket 3”, we could shuffle them and have “ball 2 in bucket 3” to the left of “ball 1 in bucket 2”. This isn’t a permutation of the balls-in-buckets, just a tidying up.

Rearranging interpretation (b)’s output gives:

$\begin{array}{ccccc} ball&f^{-1}(1)&f^{-1}(2)&f^{-1}(3)&\ldots\\ bucket&1&2&3&\ldots\end{array}$

So we see the inverse behaviour.

Let’s apply two permutations are see how they compose. Let’s do $f$ and then $g$ .

In (a)’s interpretation, we simply see

$\begin{array}{ccccc} ball&f(1)&f(2)&f(3)&\ldots\\ bucket&1&2&3&\ldots\end{array}$

and then

$\begin{array}{ccccc} ball&g(f(1))&g(f(2))&g(f(3))&\ldots\\ bucket&1&2&3&\ldots\end{array}$

And so the composition of $f$ then $g$ is $g \circ f$ . This feels nice.

In (b)’s interpretation, our actions are equivalent to permuting the
buckets. So let’s do a permutation $f$ and then a permutation $g$ . We see:

$\begin{array}{ccccc} ball&1&2&3&\ldots\\ bucket&g(f(1))&g(f(2))&g(f(3))&\ldots\end{array}$

As before, let’s “tidy up”, by viewing the whole lot in a different order – so again, not a permutation, just a tidying. First, let’s reorder everything using $g^{-1}$ :

$\begin{array}{ccccc} ball&g^{-1}(1)&g^{-1}(2)&g^{-1}(3)&\ldots\\ bucket&f(1)&f(2)&f(3)&\ldots\end{array}$

And then tidy using $f^{-1}$ too:

$\begin{array}{ccccc} ball&f^{-1}g^{-1}(1)&f^{-1}g^{-1}(2)&f^{-1}g^{-1}(3)&\ldots\\ bucket&1&2&3&\ldots\end{array}$

(This is probably a good way to look at it, as the buckets are likely to be heavy, so we’d probably prefer to move the balls.)

In other words, applying $f$ and then $g$ to the buckets gives the ordering of the balls obtained by $f^{-1} g^{-1}$ . That’s just weird!

[I hope that Latexing worked. First time, ooh…]
jonkatz Says:
October 17, 2011 at 9:20 pm | Reply
I think the confusion arises from altogether bad notation to begin with. (I looked back at the book I learned undergrad algebra from — Fraleigh’s book — and saw that there was no confusion there.)

A permutation $\sigma$ does act on sets; it acts on elements of a set. So the notation $(1 2 3) {1, 2, 3, 4}$ doesn’t really make sense (unless you want to overload notation and argue that what you really mean is to apply $(1 2 3)$ sequentially to each element of the (ordered) set ${1, 2, 3, 4}$, which I don’t think is what you meant).

Viewed in that way, it is clear that $\sigma(1)$ “permutes” the value 1, since there is no ordering to speak of.
Joseph Malkevitch Says:
October 17, 2011 at 10:18 pm | Reply
Very often it is of interest to enumerate a collection of permutations. When doing this it is nice to have a list of the permutations where in order to go from one permutation in the list to the next there is some simple “operation” one can do to get from permutation i in the list to permutation (i+1) in the list. One can also think of going from the last item in the list to the first item in the list by the same operation. This leads to the idea of a hamiltonian path or circuit in an appropriate graph. Often one gets new insights into the the nature of the collection of permutations by thinking about the issue in this way. The term Gray code originally referred to enumerating the binary digits (say of length n) in a list such that there was one digit change between the ith binary number in the list and the (i+1)st one. Finding the Gray code for binary digits of length n leads to constructing a hamiltonian path or circuit on the n-cube. The term finding a Gray code is now often used for other listings of combinatorial objects, such as for permutations. The graph one constructs in looking to see if there is a Gray code often is of separate interest. (See for example: http://en.wikipedia.org/wiki/Permutohedron ).
Jay Daigle Says:
October 17, 2011 at 11:34 pm | Reply
Dr Gowers: I think you left off at least one way of thinking about permutations. I’ve always read (124) as 1 and sending it wherever 2 is, then taking 2 and sending it to wherever 4 is, and sending 4 to wherever 1 started out. So the cycle notation effectively looks like $(1, \sigma(1), \sigma(\sigma(1)), \dots, \sigma^{-1}(1))$ . I think this is different from either of the ways you discussed–I write down the same thing as option 2, but I never think of objects as being in places at all.

Strangely, halfway through grad school this has never gotten me in trouble.
- gowers Says:
  October 18, 2011 at 12:04 am
  Let me check I understand what you’re saying. If we apply (124) to the numbers 1 2 3 4 5 6 under your scheme, then they would go to 4 1 3 2 5 6. Under the normal definition that is applying the permutation (142) (since 1 is replaced by 4, 4 is replaced by 2 and 2 is replaced by 1). In general, it seems that your interpretation of the cycle notation is the inverse of the usual interpretation. (The difference between what you do and the moving-places notion is that you compose your permutations in the opposite order from that.)
  
  I think that means that when you compose you get different answers. With the usual interpretation, for instance, (12)(23)=(123). With your interpretation, if we start with 1 2 3 and apply (23) then we get 1 3 2. If we then apply (12) we get 2 3 1. But if we apply (123) then we get 3 1 2. So according to your interpretation, (12)(23) ought to be (132). So I find it quite surprising that you haven’t got into trouble — or do you also write functions on the right (in which case the two differences would cancel each other out and you would get the same answers)?
- Jay Daigle Says:
  October 18, 2011 at 1:55 am
  Yes, that’s what I’m doing. Essentially, this makes it really easy to do multiplication; when I look at (12)(23) I say “Well, the 1 goes to the 2 and then to the 3, so I start by writing down “(13”. Then I say the 3 goes nowhere in the first permutation and then to 2, so I write down “(132”, and then check that the 2 goes to the 1 and then stays still so we get “(132)”.
  
  And yes, this is essentially using a right multiplication; I’ve never been called upon to write it out as a group action, though, so I’ve never really noticed that. I don’t really think of the symmetric group as acting on anything in particular unless I have to; I’m much happier thinking of it as an abstract multiplication rule. And I would never write either of “(123) {12345}” or “{12345}(123)” under basically any circumstances. Which is part of why I said mine was different conceptually from your second option, even though they wind up writing the same things down.
- gowers Says:
  October 18, 2011 at 8:04 am
  Your description of how you interpret the cycle notation doesn’t match how you multiply cycles. If the permutation (23) takes 2 and sends it to wherever 3 is, then if you do (12)(23) and interpret that as doing (12) first, you ought to be saying this: “I’ll send 1 to where 2 is first. Now when I do the second permutation I don’t touch 1, since I’m just swapping 2 and 3 around.” So at the end of the process 1 goes to where 2 is. So you should end up with (123).
  
  The method you’re actually using to multiply cycles together is the usual method (as described in the post above), except that you start from the left instead of from the right.
Mark Bennet Says:
October 18, 2011 at 9:56 pm | Reply
I do think there is a basic convention to negotiate about whether the leftmost operation is to be done first, or the rightmost one. I think it depends a bit whether you are an algebraist or an analyst (“which side you do your ideals” from an algebraic perspective) – I think people drift into what they are comfortable with, more than there being a universal convention. Or am I out of date???
Joseph Says:
October 18, 2011 at 10:40 pm | Reply
When I read your two options for how to interpret a permutation, I was fairly confident that the wrong one was the right one. You identify the reason I was confused, which is the relationship between permutations and actions of a group on sets.

I think permutations may be understood best without thinking about shuffling items in a line around at all. As you point out, sets don’t have to have an order but permutations still make sense.

The concept of a permutation as a bijection is quite straightforward, and for me the main difficulty is to explain how exactly groups like the symmetry group of the triangle and $S_3$ are isomorphic to each other.
J.P. McCarthy Says:
October 18, 2011 at 10:49 pm | Reply
I had always read $(12)$ as swapping the elements in the ‘places’ one and two. On first reading I read the entry as a discussion on notation — but on second reading I get the sense that you feel the ‘element moving’ perspective is the superior one and the distinction isn’t purely on the grounds of notation.

Apart from an undergraduate module on group theory (where I was much more comfortable with the general theory than concrete things like permutations), my main interaction with permutations was in a study of random walks on finite groups — in particular card shuffling.

In the random walk model of card shuffling, the deck always begins in some known order (represented by the identity element as we do random walks on groups via left- or right- multiplication). In reality the actual labels on the cards are irrelevant and I can simplify things slightly via

$f(A\heartsuit)=1$ , $f(2\heartsuit)=2$ , …, $f(K\clubsuit)=52$ ,

so the deck begins in the order $(1,2,\dots,n)$ . I think that in this context that the ‘position moving’ perspective is more natural as the deck is essentially the set of total orders you can put on the set $\{1,2,\dots,n\}$ ; and when we do an actual shuffle we don’t interchange the elements of the set $\{1,2,\dots,n\}$ , but rather their positions (i.e. swap $K\heartsuit$ and $K\diamondsuit$ is not a shuffle while swap the top and bottom cards is a shuffle — cf. Gareth’s comment above). When we shuffle we don’t look at the elements of the set. I absolutely agree that, given that we know the order of the deck, the shuffle could well be of the form $(K\heartsuit,K\diamondsuit)$ (in the ‘correct’ notation).

While I understand that it is critically desirable that the mathematics community have conventions when it comes to notation, I’m still not convinced that the ‘place moving’ perspective is plain wrong — indeed you’ve shown (which I hadn’t seen before) that the two are merely inverse.

Having said that I can’t quite see how to handle the card shuffling analysis through the ‘element moving’ perspective. For example, the random transposition shuffle can be implemented by sampling by the following probability measure $\nu\in M_p(S_{52})$ (where the notation is the “wrong” ‘position moving one’):

$\nu[e]=\frac{1}{n}$ ,
$\nu[(ij)]=\frac{2}{n^2}$ , $i\neq j$ .

I can see how to do this in the ‘element-moving’ perspective:

$\nu[e]=\frac{1}{52}$ ,
$\nu[(xy)]=\frac{2}{52^2}$ , $x$ and $y$ are two distinct card labels $\in\{A\heartsuit,\dots,K\clubsuit\}$

However the top-to-random is slightly less natural. In the ‘position moving’ picture:

$\nu[e]=\frac{1}{52}$ ,
$\nu[(1i)]=\frac{1}{52}$ .

I think it is harder to do this for ‘element moving’:
$\nu[e]=\frac{1}{52}$ ,
$\nu[(tx)]=\frac{1}{52}$ , where $t$ is the top card label and $x$ is another card label…

Of course your demonstration that the two perspectives are inverse means that we have to be able to do this even if it looks impossible! After a cup of tea I can see that we can because after $k$ shuffles that the card label $t$ is actually well defined — but this doesn’t feel as natural to me and I can get into problems with my random walk construction (which I don’t want to fix right now) as the product of iid distributed random variables taking values in $S_{52}$ .

Of course this could be a pathological example of where the ‘position changing’ perspective seems superior and in that case I’m glad someone is trying to clear up this occasionally troublesome issue.

PS: Really enjoying your posts that are written for the students of Cambridge.
- J.P. McCarthy Says:
  October 18, 2011 at 10:54 pm
  The $n$ s here should be $52$ s.
- Joseph Says:
  October 20, 2011 at 7:00 pm
  I believe it would be possible to represent shuffles based on position. Let $f: [52] \to X$ be an ordering of a set $X$ , for example a set of cards. Then given $g \in S([52])$ , $f \circ g$ is another such ordering.
  
  $S(52)$ acts on the set of orderings of $X$ by $g \cdot f = f \circ g^{-1}$ (for $g \in S(52)$ , $f$ an ordering of X. We can easily check that this action is well-defined: [ $(g_1g_2) \cdot f = f \circ (g_1g_2)^{-1} = f \circ g_2^{-1}g_1^{-1} = g_1 \cdot (f \circ g_2^{-1}) = g_1 \cdot ( g_2 \cdot f)$ .
- Joseph Says:
  October 21, 2011 at 9:00 pm
  I’ve spent some more time thinking about this, and in fact $(12)$ *does* swap the elements in places one and two. If a permutation represents a reordering of items placed in a line, then there is only one sensible choice for what that reordering is.
  
  The two possibilities mentioned in the main post for how to interpret a permutation are *both* correct, and not inverses of each other (with a small change in interpretation which I notice was actually mentioned in the post).
  
  The paragraph starting “Now let’s see what would have happened if…” interprets the cycle notation two different ways. When we “apply $(124)$ , this is interpreted as: move item in position 1 to position 2, that in position 2 to position 4, etc. After we’ve applied both permutations, we get “4 1 3 5 2 6” and it is claimed that this shows that the cycle notation is $(1 4 5 2)$ . However, what happens if we apply $(1 4 5 2)$ to the sequence “1 2 3 4 5 6”, using the “moving items in particular positions” interpretation? We do not get “4 1 3 5 2 6”. The right answer, $(1 2 5 4)$ does give this when interpreted the same way that the original permutations ( $(124)$ and ($(45)$) were interpreted.
  
  So what this shows is that it is perfectly valid and correct to compose permutations by applying each of them to a sequence in turn, and then working out what permutation would send the initial sequence to the final sequence.
J.P. McCarthy Says:
October 18, 2011 at 10:56 pm | Reply
Sorry don’t know what happens there: $n=52$ .
Doglas Says:
October 21, 2011 at 6:31 am | Reply
thank you for this interesting article on permutations.. have learnt a lot from this
Rob Kent Says:
October 21, 2011 at 1:31 pm | Reply
As a layman who would, before reading this blog entry, have interpreted the cycle notation in the same way as Jay Daigle suggests above (i.e. as applying to the elements rather than positions, but in the inverse cycle direction from the direction given by the standard interpretation/standard convention, could I offer a comment on the psychological/intuitive aspects of that, in particular in relation to what may be the mindset of a UK university fresher, and especially with regard to the use of the word “send”?

A fresher will have learnt about “permutations” in A-level not from a functional or group theory persepctive – as in your “bijection” point above, but merely in crude computational terms (i.e. “how many permutations are there…”), with real-life examples such as “arranging books in order on a shelf”. This, I think, could cause confusion when you use the word “sends” in the functional sense (as in the 6th line of your 4th paragraph). Consider a set of 4 different city guide books lined up on a shelf, in the order (Paris, Rome, Moscow, London), and a permuation which changes that order to (Rome, Moscow, London, Paris). I think a school leaver would naturally say that that permuation had “sent” the Paris guide “to London’s place” and would be very surprised to learn that it had been “sent” to Rome, in the functional sense that the permuation had replaced it with Rome.

Your very helpful explanation for why the notation has to refer to elements rather than positions does not address the confusion between the standard meaning and the interpretation of Jay Daigle, and I would suggest that confusion amongst new students might be mitigated by explaning that “send” is used (in the permutation context) in the functional sense and not in the sense used by people in everyday life.
Anon Says:
October 22, 2011 at 3:21 pm | Reply
This might be off-topic since post is about set permutations and not multisets.

But I´ve a doubt whose solution seems not obvious to me: which interpretation is correct, if any, position bijection or object bijection when applying set permutations on multisets. :

Under position bijection: 11123*(12)=11123 which is valid as multiset permutation.

Under object bijection: 11123*(12)=22213 which i´m not sure falls under the idea I have of permutation.

(Of course It is perfectly possible that I am misapplying the cycle notation of set permutation to multisets or both, in any way).

Before asking here I made a very superficial search about this. It seems that the situation is not clear for functions of multisets in general (from wikipedia article on multisets):

“However to replace set theory by “multiset theory” so as to have multisets directly into the foundations is not easy: a privileged role would still have to be given to (ordinary) sets when defining maps, as there is no clear notion of maps (functions) between multisets”
Joseph Says:
October 22, 2011 at 5:39 pm | Reply
I’ve been trying to think more about where the inverse comes from when applying a permutation $\sigma$ to a list of objects. If the order of objects is represented by $f:[n] \to X$ , then $\sigma \cdot f = f \circ \sigma^{-1}$ . However: if the order is represented by $f:X \to [n]$, then $\sigma \cdot f = \sigma \circ f$ – no inverses at all.

An analogy is made in the post with $f(x - t)$ being a shifting of the graph of $f(x)$ to the right. (It is maybe slightly clearer to start with $f(x)\gets x+t$ as a definition of the new, shifted function.) It is clear in this case that we had an idea of how to “move” the x-axis, which corresponded to the inverse “movement” of the values of the function. Therefore we can easily move the values of the function in any way we want by composing on the right of f the inverse of the permutation.

But: I would argue this is not exactly what we are doing when we compose to get $f \circ \sigma^{-1}$ . We do not start with a shuffle (i.e. a way of reordering a list of objects) and then apply the inverse of that shuffle. (In contrast, we knew exactly what $x \mapsto x + a$ does.) The shuffle which ends up being applied to the list of objects is the *primary* interpretation of a permutation as a shuffle. The inverse of that shuffle does mean something, but it is a derivative meaning. (Of course, what I’m saying about meanings being derived from each other is “metamathematical” in nature, but I think it does make a difference in how one thinks about it, which is important.)

What exactly is the meaning of the inverse shuffle (i.e. the inverse of the shuffle which is applied to the list of objects)? I do not think it is particularly important, but it might shed some light to answer the question anyway. I explain it as follows:

I have a mental image which shows the isomorphism between the group of permutations and the group of “shuffles”. On the left hand side there is a list of numbers $1 2 \dots n$ , on the right-hand side a list of $n$ objects, with the numbers $1 2 \dots n$ below them, serving as indices as Gareth explained.

Now what we do is apply permutations to the values on the left-hand side, and the indices on the right-hand side, and each time add a new row underneath showing the new values we have reached for both sides. After each shuffle we reorder the items on the right-hand side so that the indices count up from 1 to n again. So first there is a shuffle applied to the index row, and then a second shuffle to both rows. The second shuffle is actually the shuffle represented by the permutation, so the first shuffle is its inverse.

This shows that the inverse shuffle means: that shuffle which sends $1 2 \dots n$ to the list of images of those values under the permutation.

Suppose we apply a sequence $(\sigma_i) (1 \leq i \leq m)$ of shuffles. We aim to find the shuffle which gives us the bottom value on the left starting with $1 2 \dots n$ .

If we look at the table (with two rows) at the bottom of the right column, then if we apply the same shuffle to the top and bottom rows, we will represent the same permutation. If we find a series of shuffles which changes the top row to $1 2 \dots n$ , then the bottom (index) row must be the same as the bottom value on the left. We can easily do this by applying the inverses of the shuffles which were applied to the top row, which were $\sigma_1, \sigma_2, \dots, \sigma_m$ in the orginal order, and so $\sigma_m^{-1}, \dots, \sigma_2^{-1}, \sigma_1^{-1}$ in reverse. Thus $\sigma_1^{-1}\dots{}\sigma_m^{-1}$ is the shuffle which sends $1 2 \dots n$ to the list of images after all the permutations are applied (which I think we expected).

(This turned out longer than expected. Hopefully there aren't too many mistakes in the LaTeX.)
clairemathieu Says:
October 29, 2011 at 1:22 pm | Reply
“What is it that causes this particular confusion?”

I don’t like the elements-versus-places perspective. I find it confusing. I like to picture a permutation as a graph with n vertices labeled 1,2,…,n, and arcs such that each vertex has indegree and outdegree exactly 1. The vertices don’t have to be drawn on a line. They can be placed anywhere. The placement-on-a-line is a convention that becomes artificial as soon as we are dealing with a bijection of an unordered set such as {red, green, yellow, blue}. That is, a permutation is primarily a bijection between finite sets, and the fact that the underlying set is {1,2,..,n} and that it has the natural order 1<2<…2->4) rather than (124). The arrangement notation such as 2 5 3 4 1 6 has an implicit assumption, and I prefer to make it explicit, like this:
i 1 2 3 4 5 6
sigma(i) 2 5 3 4 1 6
It’s a little more cumbersome, but it removes ambiguities I think.

If your permutation was (red yellow blue), the cycle notation would still make sense (red -> yellow -> blue). The arrangement notation would make no sense because there is no natural order on colors, so you’d have to be explicit
i red green yellow blue
sigma(i) yellow green blue red

(My taste was formed by a course on bijective combinatorics taught by Xavier Viennot from the university of Bordeaux.)
clairemathieu Says:
October 29, 2011 at 1:25 pm | Reply
Correcting editing typo: “it has the natural order 1<2<…2->4) rather than (124). )”
clairemathieu Says:
October 29, 2011 at 1:27 pm | Reply
Attempt number 3 of correcting editing typo: “it has the natural order 1 less than 2 less than … less than n.

(Side note: for cycle notation, I would prefer ( 1 arrow 2 arrow 4 ) rather than (124).)”
Hans Wehr Says:
November 6, 2011 at 1:05 pm | Reply
It is true, of course, that if you talk about permutations as bijective actions on a set then the ‘elements-in-places’ approach makes no sense, as sets are unordered. However, if we are thinking about symmetry groups then permutations within a group are acting on one another, and not on sets, since every permutation can be written in the form $\begin{pmatrix} 1 & 2 & 3 & ... & n\\ \pi(1) & \pi(2) & \pi(3) & ... & \pi(n) \end{pmatrix}$ , where the ‘order’ is given by the preimages of each element under the permutation $\pi$ . So, if we wished to compose the two permutations $\left ( 124 \right )$ and $\left ( 45 \right )$ , then we could write them as $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 4 & 3 & .1 & 5 & 6 \end{pmatrix}$ and $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 2 & 3 & .5 & 4 & 6 \end{pmatrix}$ and then interpreting the composition of two permutations $\pi$ and $\sigma$ as being the permutation which takes $x$ to $\sigma\left ( \pi\left ( x \right ) \right )$ (which is more similar to the ‘elements in places’ approach, rather than being the permutation which takes $\pi ^{-1}\left ( x \right )$ (i.e. the preimage of $x$ under $\pi$ ) to $\sigma\left ( x \right )$ (which is more like the ‘elements’ approach, and which seems less natural). So the composition of these two permutations can be interpreted as $\left ( 234516 \right )$ without redefining a permutation so that it acts on an ordered set.
Group actions I « Gowers's Weblog Says:
November 6, 2011 at 3:42 pm | Reply
[…] There is one example that is a good one to have in your head, as it gives you a very good idea of what an action is. Let be the alternating group and let be a regular tetrahedron, and label its vertices 1, 2, 3 and 4. For each permutation in and each position of , we can find a rotation that permutes the vertices of according to . For example, to achieve the permutation we do a half turn about the line that joins the midpoints of the edges linking 1 to 2 and 3 to 4, and to achieve the permutation we do rotation through 120 degrees through the line that joins vertex 4 to the middle of the opposite face. (Note that these axes depend on the position of rather than being fixed. See the discussion in the post on permutations.) […]
Group actions III — what’s the point of them? « Gowers's Weblog Says:
November 25, 2011 at 6:16 pm | Reply
[…] all groups, acts on itself by conjugation. You may remember that I discussed towards the end of a post on permutations how to conjugate permutations. The quick thing to remember is that if you want to calculate the […]
Turing and entropy conductors (high bullshit alert) | Peter's ruminations Says:
November 13, 2013 at 10:26 pm | Reply
[…] https://gowers.wordpress.com/2011/10/16/permutations/ […]
Groups and Group Actions: Lecture 3 | Theorem of the week Says:
February 25, 2015 at 11:24 am | Reply
[…] are lots of interesting points in this blog post by Tim Gowers — but do be careful, he writes permutations on the left, whereas we write […]
Groups and Group Actions: Lecture 3 | Theorem of the week Says:
February 24, 2016 at 11:48 am | Reply
[…] are lots of interesting points in this blog post by Tim Gowers — but do be careful, he writes permutations on the left, whereas we write […]
John Lucas Says:
September 25, 2017 at 10:54 pm | Reply
“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 (1254).” This word ‘sends’ is confusing to me. It sounds like you are sending 1 to the 2 place , sending 2 to the 5th place, etc, i to get { 4,1,3,5,2,6}.

When in fact you are doing more like f(1) = 2, f(2) = 5..etc.

Is there a better word than sends, why do we use this word ‘sends’? Is it to be suggestive if we draw symmetries of a triangle or square where we are we are sending vertices to vertices.

Also what do you mean by
“means that you cycle round the elements 1, 2 and 4”
what direction do you cycle round
- Nalin Pithwa Says:
  September 19, 2020 at 5:38 am
  I think Dr. Gowers means clearly…if you draw the arrow diagram of the mapping with domain and codomain/range, an element in the domain is “mapped” or ‘send to” corresponding image in range/codomain. …Hope this helps…
John Lucas Says:
September 26, 2017 at 12:28 am | Reply
I think this video led to some of my confusion too.
John Lucas Says:
September 26, 2017 at 12:28 am | Reply
i meant this
John Lucas Says:
September 26, 2017 at 12:30 am | Reply
go to 7:50
- John Lucas Says:
  September 26, 2017 at 1:47 am
  and this at 7 minutes
Nick Says:
December 12, 2017 at 6:39 pm | Reply
Thank you so much Mr. Gowers! I have never seen this addressed anywhere else. This idea of interpretations of permutations has brought me sooo much confusion in the past, especially with dihedral groups.
Robin Andrews Says:
September 18, 2020 at 9:00 pm | Reply
It is great to see this issue explained so clearly. When I teach programming, I always stress the importance of being clear about whether we are thinking about an index or a value at a given index in a list/array. I wrote about it here: https://compucademy.net/a-key-distinction-for-better-understanding-of-computer-science-gcse-and-a-level/ Tracking this distinction with permutations can be tough, and it’s refreshing that you recognise the trouble student have and help to dispel the confusion rather than just insisting that one interpretation is correct.