Lesson 24: Cool Groups pt. 1—Permutations

We’ve spent the last two lessons setting up the abstract formalism of groups and group theory, by letting the addition of integers motivate our digression into the clouds. Now, if you’re a fan of abstraction for its own sake, then perhaps you see no issues with our constructions and enjoy them for what they are. However, if you’re a more pragmatic soul, you may be wishing to see why all of this is necessary. Why can’t we just talk about adding things the way we’re used to, and not have to go into all this group nonsense?

Well, as we saw even with the simple notion of counting, abstraction is a very powerful tool indeed. We saw in lesson 8 (and beyond) that by defining counting to be “finding a bijective function between the set you’re trying to count and a set of the form $\{1, 2, 3, ..., N\}$ ”, we were actually able to make an immense amount of progress in understanding infinity more deeply. Thus, by abstracting away what we mean by counting, we were able to “count” things that we had no way of counting before.

A similar thing can be said about groups and group theory. By abstracting away what we mean by “adding” or “multiplying”, we can actually say much more powerful statements than we could before we resorted to this abstraction. In particular, we can use the machinery of group theory to talk about mathematical structures that have nothing to do with numbers and our ability to add or multiply them. And as proof of this, we’ll spend the next couple of lessons exploring groups that are very different from “addition of integers”. This will hopefully give the reader at least the slightest taste of what group theory is all about, and how flexible and powerful it is. Groups are, however, one of the most pervasive objects in all of mathematics, arising in many different forms and guises. Thus, it is absolutely impossible to fully appreciate the many facets of an abstract group (people spend their lives trying to do so). However, with these few examples, we can start to get a sense of things.

The first group (which isn’t related to adding or multiplying numbers) that we’ll discuss goes by a couple different names: the permutation group, or the symmetric group. We’ll find that this group is one such that $ab$ does not necessarily always equal $ba$ , and is therefore very different than any group we’ve studied so far. This group is also an extremely fundamental one, as it rears its head all over the place in pure and applied mathematics. It also happens to be, in my opinion at least, a very gorgeous group. But I’ll spare you any love letters that I have for this group, and instead just dive right in to what it’s all about.

Consider a (finite) set with $N$ elements. The group that we’ll be considering is the group of “shuffles” of these $N$ elements. Namely, we view “the act of shuffling these elements around” as a single element of a set, and it will turn out that the set whose elements are “all possible such shuffles” will have the structure of a group. In this lesson we’ll only consider a set with a specific number of elements, so that the general case will become more clear for future lessons.

Consider a set $S$ with 4 elements—any set at all. A permutation of this set is a bijective function $f:S\rightarrow S$ . A bijective function can, and should, be viewed as a “shuffling” of the elements of the set, in exactly the way one would shuffle a deck of cards. Namely, when one shuffles a deck of cards, it is never the case that cards just disappear into thin air, or that cards magically appear out of nowhere. It is only the case that cards are rearranged. The abstract mathematical object that reflects all of these ideas is precisely a bijective function, since a bijective function from a set to itself maps each element to some other element in a perfectly one-to-one way. In other words, a bijective function does not lose any of the original information, it just merely rearranges that information.

For example, suppose our 4-element set were given by a collection of colored dots, and suppose moreover that we put these colored dots into their own numbered compartments as shown in figure 1 (these dots can represent anything (horses, numbers, the number of championship rings that Kobe has more than Lebron, etc.), and so we don’t lose any generality at all with this representation).

figure 1: a 4-element set

Then any bijective function from our set to itself can equally well be expressed as a set of instructions specifying which compartment to send each dot to. I.e., one bijective function $S\rightarrow S$ can be written $1\rightarrow 2, 2\rightarrow 1, 3\rightarrow 3, 4\rightarrow 4$ , which just means “send the element in compartment 1 to compartment 2, send the element in compartment 2 to compartment 1, and leave compartments 3 and 4 alone”. This can be viewed either as a function that maps the pink dot to the brown one, the brown dot to the pink one, the blue dot to itself, and the green dot to itself. This is clearly bijective. Equivalently, this can be viewed as merely “swapping” the contents of compartments 1 and 2, thus giving the layout in figure 2 (assuming we started in the configuration of figure 1). We should choose to use the perspective of actually moving the dots around (i.e., actually swapping them) because that will make things more apparent.

figure 2

We simply note that all of this can be phrased in the language of bijective functions to give us faith that all of this language of “swapping” and “shuffling” does indeed have a rigorous mathematical foundation (in terms of bijective functions). It is just that this rigorous foundation is unnecessarily complicated, and we don’t lose anything by just considering “shuffles”. Thus, let us consider this action of swapping the contents of compartments 1 and 2 as an abstract element in its own right, and let us denote this action (for obvious reasons) by $(1, 2)$ , which means “send the element in compartment 1 to compartment 2, and that in compartment 2 to compartment 1” (the analogous notation will be used below, where the list within the parentheses $(i, j, k, ..., m)$ says “send the element in compartment $i$ to compartment $j$ , that in compartment $j$ to compartment $k$ , and so on, until we get to compartment $m$ , when we send its contents back to compartment $i$ (i.e., we cycle through the end of the parentheses)).

But there are other permutations that we can consider. For example, we can consider the action $1\rightarrow 2, 2\rightarrow 3, 3\rightarrow 1, 4\rightarrow 4$ , which takes the element in compartment 1 to that in compartment 2, the element in 2 to 3, and the element in 3 to 1, while leaving the element in compartment 4 alone. This gives the layout in figure 3 (assuming we started in the configuration of figure 1).

figure 3

Let us denote this action by $(1, 2, 3)$ , which is meant to represent “send 1 to 2, 2 to 3, and 3 to 1”, so that we “cycle through” the end of the parenthesis and send the corresponding element to the compartment listed in the front of the parentheses. Similarly, the action that swaps the elements in compartments 3 and 4 while leaving those in 1 and 2 alone can be denoted by $(3, 4)$ , and the action that sends 1 to 2, 2 to 4, and 4 to 1, while leaving 3 alone, can be denoted by $(1, 2, 4)$ . We can also have the action that cycles all of them to the next compartment, meaning it sends 1 to 2, 2 to 3, 3 to 4, and 4 to 1, and this will be denoted by $(1, 2, 3, 4)$ . Assuming we started in figure 1, the action of the permutation $(1, 2, 3, 4)$ gives the layout of figure 4 (note that if we started in a different configuration, the final configuration would be different, since these instructions mean “take whatever is in compartment X and send it to compartment Y”). Hopefully the pattern is becoming clear. Finally, we denote the action of not doing anything at all by $e$ .

figure 4

We can now consider the set of permutations of 4 elements. Note that this set has much more than 4 elements, which should be clear because there are much more than 4 distinct ways to shuffle 4 elements. We’ll calculate just how many elements there are in this set later, and for now we’ll focus on the structure of this set. I claim that we can turn this set into a group, in a very straightforward way. Let us say that the abstract group multiplication is simply composition of actions, meaning that to combine “action 1” with “action 2”, we simply “do action 1 first,” and then “do action 2”. That sounds simple enough. Thus, to multiply the element $(1,2)$ with $(2,3)$ , we simply first swap 1 and 2 while keeping 3 and 4 fixed (which is moving from figure 1 to figure 2) and then swap 2 and 3 while keeping 1 and 4 fixed (which is moving from figure 2 to figure 5). The combined action then has been to take the element in compartment 1 to compartment 3 (by moving it to 2 along the way), to take the element in compartment 2 to compartment 1 (because after the first action the first compartment was not touched), and to take the element in compartment 3 to compartment 2.

figure 5

Thus the product of $(1,2)$ and $(2, 3)$ , denoted by $(2,3)\cdot (1,2)$ , is simply $(1, 3, 2)$ (where we recall that this “parentheses notation” is short for “take the element in that number compartment to the compartment corresponding to the number in the slot to the right, and when we hit the end of the parentheses we cycle back to the beginning of the parentheses”) (note also that we put the actions in chronological order in terms of which “happens first”, with the first action appearing farthest on the right). Thus, if we started in figure 1 and applied $(1, 3, 2)$ , we’d find ourselves in figure 5.

Now that we have our multiplication, it should be clear what our identity element should be. Namely, it’s just our action $e$ , which is “not doing anything at all”. Clearly, if we make a permutation and then “don’t do anything at all”, it’s the same as just doing the permutation, and if we first “don’t do anything at all” and then do the permutation, it’s the same as just doing the permutation. Thus, we have that for any action $a$ , $e\cdot a= a\cdot e=a$ , where $a$ could be $(1, 2, 3)$ or $(2, 4, 1, 3)$ , or whatever.

So we’ve now shown that our set has a multiplication rule as well as an identity element, so it only remains to check that this multiplication rule is associative and that each element has an inverse, and we’ll have successfully shown that “the set of permutations of 4 elements” is a group.

In this case, associativity is so obvious that it’s almost difficult to show. To help things along, though, consider the following scenario. Suppose my list of “to do” today is 1) go to the grocery store, 2) do the laundry, and then 3) wash the dog, and suppose I have to follow my list in numerical order. I could easily rewrite my list in terms of two actions: 1) go to the grocery store then do the laundry, 2) wash the dog. BUT, I could also rewrite my list as 1) go to the grocery, 2) do the laundry then wash the dog. Clearly, in both cases the actions that I’m undertaking are exactly the same (including the order in which I do them), I’m just viewing them differently. It is painfully obvious that regardless of how I write my list, my day will transpire in the exact same way (assuming I actually follow my own list in both cases).

In the exact same way, associativity of our multiplication of permutations is painfully obvious. For suppose we perform three permutations $a_1, a_2, a_3,$ in a row, namely $a_3\cdot a_2 \cdot a_1$ . Then we have two ways of viewing the combined action of all three permutations. We can view it as first doing the combined action $(a_2\cdot a_1)$ , which is “first do $a_1$ then do $a_2$ ”, and then finally doing the action $a_3$ , which in total is written $a_3\cdot (a_2\cdot a_1)$ . Or, we could view this as first doing the action $a_1$ , and then doing the combined action $(a_3 \cdot a_2)$ , which again is just “first do $a_2$ , then do $a_3$ ”. This is then written $(a_3\cdot a_2)\cdot a_1$ . But it should be clear that both of these different perspectives give the same total action, because in each case we’re first doing $a_1$ , then $a_2$ , then $a_3$ . All we’re doing is arbitrarily choosing which two actions we want to view as a single action, but regardless of whether or not we view a pair of actions as a single action, we’re not altering the result of the actions themselves.

Although this is not necessarily a completely rigorous proof of associativity for our multiplication, hopefully the philosophy is clear enough, and the obviousness of it so immense, that you’ll forgive the lack of complete rigor.

Now all we need to show is that each permutation has an inverse, and this is a lot easier to do. Again, I won’t show it completely rigorously, but rather try to make the result so painfully clear that the reader can take on faith that one can sit down and figure out how to translate the proof into symbols that make it more formal.

Suppose we perform some permutation on our set of objects. To find an inverse, we need to find another permutation such that its action will now make it so that our objects are in the same position as they were before we performed the original permutation. But this is easy! All we need to do is look at the permutation that we performed and “back track”, sending each element back to where it came from. This is certainly a well-defined permutation. For example, suppose we perform $(4,1,2)$ . Then, its inverse needs to send 2 to 1, 1 to 4, and 4 to 2. I.e., we’re simply “reversing the order” of the parentheses. So the inverse of $(4, 1, 2)$ is simply $(2, 1, 4)$ . It is then clear that the inverse of the inverse is the original permutation, since if we reverse the order twice we’re just back to where we started. It is then clear that the inverse of any “swap” is just itself again. For consider the action $(1, 2)$ . Its inverse is $(2,1)$ , but since we end up “cycling through” the end of the parentheses, we can rewrite this as $(1,2)$ , which is nothing but the statement that “swapping 1 and 2” is the same as “swapping 2 and 1”, which is clearly true.

Finally, consider a product of permutations, like $(1, 2, 4)\cdot (3, 2)$ . We know how to invert an individual permutation, but what about a product of them? Easy! All we do is first invert the order of the individual parentheses, and then invert the contents within each parentheses. Accordingly, the inverse of $(1, 2, 4)\cdot (3,2)$ is simply $(2, 3)\cdot (4, 2, 1)$ . To see this, consider their product:

$(1, 2, 4)\cdot (3, 2)\cdot (2, 3)\cdot (4, 2, 1)$ .

Since the product is associative, I don’t need to worry about how I “clump” these actions together. We then notice that in the middle we have the sequence of permutations “swap 2 and 3”, then “swap 2 and 3”, which might as well be the same as “don’t do anything at all”. In fact, we could have a whole chain of permutations before and after this pair of permutations, but since we’re just swapping and then swapping back, we can easily delete that pair from our list of permutations (i.e., replace that pair with the identity permutation, which is the action of “don’t do anything”). Thus we’re left with

$(1, 2, 4)\cdot (4, 2, 1)$ .

But this is also easily seen to be the identity permutation, since the first permutation (the one on the right) sends 4 to 2, and the second one sends 2 back to 4, so that 4 goes to 4. Similarly, 2 goes to 2 and 1 goes to 1. Thus, the product of these permutations is the identity permutation.

To finish checking that we’ve actually found the inverse permutation of our original permutation, we need to check that multiplying them in the opposite order still gives the identity. I.e., we need to check the following product:

$(2, 3)\cdot (4, 2, 1)\cdot (1, 2, 4)\cdot (3, 2)$ .

But the same logic works. Namely, look at the middle two permutations and see that it’s the identity (which we’ve already done), and then you’ll be left with the two “swaps” of 2 and 3, which combine to give the identity.

It may be clear, or it may be shown, or it may be taken on faith that this process of “reversing the order of the parenthetical expressions, and then reversing the order of the contents within each individual parenthetical expression” is an algorithm that always gives the inverse of a given permutation. This can be seen by noticing that if we do this, then multiply the two total permutations together, we can always “start in the middle and work our way out”, reducing each pair one at a time to the identity element.

Thus, we’ve found that each element has an inverse, and therefore that the set of permutations is in fact a group!

To finish this lesson off, let’s see that this group is non-commutative, meaning that there are elements $a,b$ such that $ab\neq ba$ , and thus emphasizing that this group is very different from that of the integers.

We saw above that the combined action of first doing $(1, 2)$ and then doing $(2, 3)$ was $(1, 3, 2)$ . I.e., $(2,3)\cdot (1, 2)=(1, 3, 2)$ . However, if we reverse the order of these actions, and instead first do $(2, 3)$ and then do $(1, 2)$ , we first send 2 to 3 and 3 to 2, and then send the contents of 2 to 1 and those of 1 to 2. But, the contents of 2 in the second swap are precisely the contents that started life out in 3 (because we’ve already swapped 3 and 2). Thus, 2 goes to 3, 3 goes to 1, and 1 goes to 2. So we have $(1, 2)\cdot (2, 3)=(1,2, 3)$ (remember that we can change the order of the numbers in the parentheses in a “cyclic way”, meaning we shift all of them to the right (or to the left) without swapping any of them, and the reason we can do this is that our notation “wraps back around” the end of the parentheses). But clearly $(1, 2, 3)\neq (1, 3,2)$ ! Thus we’ve found elements that don’t commute, meaning it matters in which way we combine them.

Some elements do commute, however. For example, $(1,2)$ and $(3, 4)$ do commute, meaning $(1, 2)\cdot (3,4)=(3,4)\cdot (1,2)$ , and this is because the individual permutations don’t know about each other. Namely, they don’t intermix, so we can “swap some elements over there” and “swap some elements over here” in any way we’d like, so long as there are no elements that are both “over there” and “over here”.

This lesson has already proven to be a doozy, so I’ll end here. We’ll continue to explore permutations for another lesson though, as they’re extremely important, and a great warm-up for even cooler groups. The exercises below might require pen and paper, thus going against my promise at the beginning of these lessons (or elsewhere on the site). For that I’m sorry. If you’re truly allergic to pen and paper, feel free to skip the exercises (although they’ll help to get comfortable with the ideas discussed here). Or if you don’t like pen and paper, simply reading the exercises and my solutions would probably be sufficient to get a feel for what’s going on.

Exercises

1) Write down the permutation given by the product $(1, 2, 3)\cdot (2, 3, 4)$ .

2) What is the inverse of the permutation $(2, 3, 4)$ ? What about $(1, 2, 3, 4)$ ? What about $(1, 2, 4)\cdot (2, 3, 1)$ ?

3) Think about how this construction can be generalized to a set with arbitrarily many (but only finitely many) elements. (Okay, this isn’t really an exercise, but it’ll help to warm up for the next lessons).

Solutions to Exercises

Back to Interlude

Previous Lesson

On to Lesson 25

5 Responses to Lesson 24: Cool Groups pt. 1—Permutations

Anonymous says:

August 15, 2015 at 8:42 am

(•) So we have (1, 2)\cdot (2, 3)=(1,2, 3) (remember that we can change the order of the numbers in the parentheses in a “cyclic way”, meaning we shift all of them to the right (or to the left) without swapping any of them, and the reason we can do this is that our notation “wraps back around” the end of the parentheses). But clearly (1, 2, 3)\neq (1, 3,2)! Thus we’ve found elements that don’t commute, meaning it matters in which way we combine them.

When I applied the rule to multiply the inverse (i.e., (1, 2) • (2,3)), I got (2,1,3). Apparently you then shifted them (to the right, right? ha!) . But why? I mean, 2,1,3 is already different from 1,3,2 which is all that we need to prove that there is no commutativity? Thanks!!

- TrueBeautyOfMath says:
  
  August 18, 2015 at 6:22 pm
  
  Thanks for your question! Unfortunately I’m struggling to understand exactly what you’re asking. Namely, the permutations (1,3,2) and (2, 1, 3) are indeed the same permutation, since the latter can be obtained from the former by moving each number to the right (and cycling the 2 back to the front). Namely, (1, 3, 2) is shorthand notation for the instruction “move what’s in compartment 1 to compartment 3, move what was in compartment 3 to compartment 2, and move what was in compartment 2 to compartment 1”, and we also so that (2, 1, 3) give those same exact instructions. The point is, though, that (1,2).(2,3)=(2,3,1) but that (2, 3).(1,2)=(1, 3, 2), and since (2, 3, 1) is not the same permutation as (1, 3, 2), (just see what the instructions are for both) we have that the order in which we multiply (1, 2) and (2, 3) matters. Does this help at all? If not then do let me know!
  
  - Anonymous says:
    
    August 23, 2015 at 2:23 am
    
    Precisely… since 1,3,2 and 2,1,3 are the same permutation, why do you need to add the further step of moving the numbers of the former to the right if 2,1,3 is already different from 1,2,3?
    
    - TrueBeautyOfMath says:
      
      August 23, 2015 at 8:33 am
      
      Ah okay I see the confusion, and that’s a good question. The answer is that we don’t need to at all. You’re totally right: (2, 1, 3) is already different from (1, 2, 3), thus already proving a lack of commutativity. Additionally, (2, 1, 3) and (1, 3, 2) are simply different ways of writing down the exact same permutation—in short, they’re equal (as you know). Now, in my opinion it’s easier to see (literally, visually) that (1, 3, 2) is different from (1, 2, 3) simply because they both start with the same entry and then the 2 and the 3 are reversed, making it the most obvious (again, just in my opinion) that these two permutations are different. However, this last step is completely not required. Namely, if the fact that (2, 1, 3) and (1, 2, 3) are different is already completely obvious, then we can stop the proof of non-commutativity right there. The last step is just a matter of taste. Thanks for point that out! 🙂 Does that clarify it?
      
      - Anonymous says:
        
        August 23, 2015 at 11:47 pm
        
        absolutely!! thanks!