Lesson 25: Cool Groups Pt. 2—Get Your Hair Did

As usual (at least for oddly titled lessons), let me begin by explaining why the title is what it is. In the previous lesson we introduced permutation groups, and in this lesson we’ll continue to study them. Thus, in this lesson we’ll be talking about permutations, which we can call “perms”, which we can then view as a reference to hairstyling, and then we can give a shout out to the 90’s and recall how Missy Elliott told us to “get our hair did” (after telling us to get our nails done and get a pedicure). So there you have it—there’s our title. Try to contain your laughter.

Anyway, let’s remind ourselves what we’ve done with permutations so far, so that in this lesson we can formalize things a bit, make things more precise, and give some different perspectives on what we’re really doing. We’ll also find out precisely how big permutation groups are, in terms of the number of things we’re permuting.

Recall that in order to discuss a group of permutations of, say, $N$ elements, we first need to consider a set of $N$ elements. This set of $N$ elements can be any set at all, but we need to keep in mind that this set has very little to do with the permutation group itself.

Remember that in order to discuss a group, we first need a set. I.e., a group is nothing but a set with some special features (a special function (“multiplication”), a special element (the identity), and inverses). The set that we have for the group of permutations is the set of bijective functions from the set of $N$ elements to itself. In other words, the elements of our group are “shuffles” of the set of $N$ elements. This is why the set of $N$ elements has little to do with the group—the set is just there to give us something to shuffle.

Recall also that we gave this set an abstract multiplication by defining the product of two shuffles to be the shuffle that first “does the first shuffle” and then “does the second shuffle”. Thus we have a map that takes two shuffles as input, and produces a single shuffle as output, which is precisely what we need for a group. We noted in the previous lesson that this multiplication is associative, that there is an identity element (the shuffle that doesn’t move anything at all), and that there are inverses (the “reverse” of some shuffle, putting every element back to where it was before).

We can, and should, think of these shuffles as follows. First suppose that we have $N$ boxes, numbered $1$ to $N$ , and suppose we have initially put each of our $N$ elements into one of the $N$ boxes (so that every box is full and no box has more than one element in it). Then, any bijective function from this set to itself can just as well be viewed as a reassignment of our elements to different boxes, so long as we always have all of the boxes filled and so long as no box has more than one element in it. Note that all I’m describing here is what we did in the previous lesson, but with $N$ boxes and elements as opposed to precisely $4$ of them.

But what is the point of all of this nonsense with boxes and shuffles? We can, after all, just think abstractly about “bijective functions from a set to itself”, and that would all be well and good. The problem with this plan of attack, however, is that it is very difficult to actually calculate things. In order to actually calculate (which is something we’ll eventually want to do, as this is mathematics), we need to develop a notation that both captures the ideas that we have in our minds, while being (at least somewhat) easy to manipulate on pen and paper. So let’s now take what we’ve done in the previous lesson and in the preceding paragraphs to develop this notation in a very general setting.

Let’s call our $N$ element set S, and suppose we want to consider the bijective function from $S$ to $S$ that “sends” the element in the $i^{th}$ box to the $j^{th}$ box, and the element in the $j^{th}$ box to the element in the $i^{th}$ box (so that we’re really just “swapping” these two elements). We’re also assuming here that $i$ and $j$ are both numbers (possibly the same number) greater than or equal to $1$ and less than or equal to $N$ , so that they do indeed correspond to our $N$ boxes. We can write this function as $(ij)$ (I used bold here to remind us that the elements of the group that we’re describing here are themselves (bijective) functions). We read these parenthetical expressions from left to right, and then cycle back through to the beginning. Thus we start at some number in the parentheses (probably the left most number) and move the contents of that number’s box to the box corresponding to the next number on the right. Then, when we’re at the end of the parentheses, we move that box’s contents to the box corresponding to the number back at the beginning of the parentheses.

Therefore, the expression $(ij)$ means $i\rightarrow j\rightarrow i$ , which is read as “take the contents of the $i^{th}$ box to the $j^{th}$ box, and take the contents in the $j^{th}$ to the $i^{th}$ box. Similarly, an expression like $(ijk)$ means $i\rightarrow j \rightarrow k\rightarrow i$ . I.e., $(4, 2, 7)$ means “take the contents of box 4 to box 2, the contents of box 2 to box 7, and the contents of box 7 to box 4”. Note how we cycle back through the end of the parentheses, and that this means that it doesn’t matter where we “start” our parentheses. I.e., $(i, j, k)$ is the same shuffle as $(j, k, i)$ , since in both cases “ $i$ goes to $j$ , $j$ goes to $k$ , and $k$ goes to $i$ ”. Thus we have $(i, j, k)=(j, k, i)=(k, i, j)$ , but it is not the case that $(i, j, k)=(i, k, j)$ , since the contents of the $i^{th}$ box are sent to different boxes in these two perms (assuming $j\neq k$ ).

If we’re considering a shuffle that leaves certain boxes untouched, then we simply leave those out of the expression. Thus, the shuffle of “not doing anything” (which is the identity element of this group) is usually not written at all, but if we wanted to we could write it as $e$ . We could also write it as $(ii)$ or $(jjjj)$ (since these don’t actually move anything), but these would be pretty bad ways to write it.

We can have arbitrarily long parenthetical strings, like $(i, j, k, l, m, n)$ , or more concretely, like $(5, 17, 12, 4, 6, 1)$ (assuming there are at least 17 boxes, of course). Note that we cannot have the same number appear twice in one parenthetical expression, like $(5, 2, 6, 1, 5, 7)$ , because this sends the contents of box 5 to both box 2 and box 7 (and it sends the contents of both box 1 and box 7 to box 5), which is not a bijective function.

We also need to note that even though permutations such as $(1, 2)$ and $(4, 2, 5)$ are perfectly good permutations in their own right, it is not always the case that a permutation can be expressed as a single parenthetical expression. For example, we can consider the permutation $(1, 2)(3, 4)$ which swaps the contents of boxes 1 and 2, as well as the contents of boxes 3 and 4. This is a very different permutation than $(1, 2, 3, 4)$ , which cycles the contents of the boxes through the first 4 boxes. We therefore need to address how we read expressions with multiple parenthetical expressions.

The convention that we use in this case is to read the parenthetical expression on the right as “happening first”. Thus, the statement $(1, 2)(3, 4)$ means that we first swap the contents of 3 and 4, and then swap the contents of 1 and 2. Now, in this case, it doesn’t matter in which order we read the permutations because the two permutations don’t “talk to each other”, in that the boxes that they’re concerned with do not overlap. However, order does matter when we consider, for example, $(1, 3, 4)$ and $(4, 5, 2)$ (we saw a very similar example of this in the previous lesson). I.e., $(1, 3, 4)(4, 5, 2)\neq (4, 5, 2)(1, 3, 4)$ (when we remember that on both sides of the equation we’re “doing the permutation on the right first”). This is because $(4, 5, 2)(1, 3, 4)=(1, 3, 5, 2, 4)$ (note that “3 goes to 4” in the perm on the right, then “4 goes to 5” in the perm on the left, so that “3 goes to 5” in total), whereas $(1, 3, 4)(4, 5, 2)=(1, 3, 4, 5, 2)$ (where I used the fact that $(i, j, k, l, m)=(j, k, l, m, i)=(k, l, m, i, j)$ , and so on, because we can “cycle through” the end of the parentheses).

Now, most of what we’ve done so far has been a review of the previous lesson, only in the more general setting of dealing with permutations of $N$ elements rather than of only $4$ . This has largely been manifested in replacing concrete expressions like $(1, 4)$ with more abstract, general ones likes $(i, j)$ . Composition (multiplication) of permutations and inverses goes through in the exact same way as in the previous lesson. I.e., if I have some string of permutations that I want to find the inverse of, I simply first reverse the order (left to right) of the parenthetical expressions themselves, and then I reverse the order of the numbers in each individual parenthetical expression. Thus, the inverse of $(i, j, k)(l,m)(n,o,p,q)$ is $(q, p, o, n)(m,l)(k,j,i)$ , because if I compose these two strings of permutations (in either order), I’ll get the identity permutation. I’ll do one case, and you can do the other. Namely, if I put the former on the left and the latter on the right, I have

$(i, j, k)(l, m)(n, o, p, q)(q,p,o,n)(m,l)(k,j,i)$ .

Now, since our multiplication is associative, I can start in the middle and notice that $(n, o, p, q)(q,p,o,n)$ is the identity permutation. Then I’m left with

$(i, j, k)(l,m)(m,l)(k, j, i)$ ,

which, after again starting in the middle, proves to be the identity element. I’ll leave it to the reader to check that this still works when we put the former on the right and the latter on the left, although this may be clear from the above.

We’re now done developing the notation that we need to handle any permutation group (i.e., any group of permutations of any (finite) number of elements). Each permutation can be written as a chain of parenthetical expressions such that no number shows up twice in the total expression. The reason for this is that if we have an expression like $(i, j, k)(l,m,i,n)$ , then we can always simplify it to make it so that the “ $i$ ” only shows up once. I.e., $(i, j,k)(l,m,i,n)=(i,n,l,m, j,k)$ (since “m goes to i, then i goes to j, so m goes to j”). Thus, once we’ve fully simplified things and gotten rid of duplicates, each permutation can be written as a chain of parenthetical expressions (some of which only involve one parenthetical expression) such that each number shows up at most once in the total expression. We multiply permutations together by “composing” them, which means doing one after the other, and we can calculate these out by writing the parenthetical expressions down and “following each number through” the entire expression. In this way, we get a fully simplified expression, and thus a new permutation. We’ve therefore found the calculation-friendly notation that we were after with permutations.

It is important to note, though, that all of this notation and all of these conventions (viewing the rightmost expressions as “happening first”, etc.) are all simply notational conventions that we’ve arbitrarily chosen to reflect the abstract manipulation of permutations. I.e., these bijective functions exist “out there”, and we’re simply laying down the rules that we want to use to describe them when we’re forced to write them down on paper. We could have chosen different conventions (e.g. starting from the left of the total expression instead of the right) and our ways of manipulating these expressions would then also be changed, but the abstract truth into which we’re tapping is completely unconcerned with the conventions we decide on. It is simply a product of our human desire to write this stuff down and talk about it that makes us come up with notation, and it is then our job to make this notation as friendly as possible.

We’ll talk a lot more about permutations in later lessons, when we talk about subgroups, normal subgroups, quotient groups, and many other constructions. For now, let us simply answer the very straightforward question: How many permutations are there of $N$ elements? If we denote the permutation group of N elements as $S_N$ , then we’re really asking what the cardinality of $S_N$ is. Clearly, this will have to be in terms of $N$ , but let us first look at some examples and see if we can guess the answer.

If $N=1$ , then there is only one permutation, and that is “do nothing”. This is because there is one element and it just sits there in its own little lonely box. If $N=2$ , then there are 2 permutations: “do nothing” and “swap”. If $N=3$ , then then there are 6 permutations:

$e, (1, 2), (1, 3), (2, 3), (1, 2, 3), (1, 3,2)$

meaning that we can “do nothing”, we can “swap” (and there are three different kinds of swaps), or we can shuffle all of them (for which there are only two options). If $N=4$ then there are 24 permutations, and I won’t list them all. So what possible pattern can be hidden inside of $N=1\Rightarrow 1$ , $N=2 \Rightarrow 2$ , $N=3\Rightarrow 6$ , $N=4\Rightarrow 24$ , … ? It turns out that this pattern is one of a factorial. I.e., if there are $N$ elements to permute, then there are $N!$ (which is read as “N factorial”) permutations of them. Now, “ $N!$ ” is not a sign that we’re somehow very excited about $N$ , but rather just more shorthand for a number that is related to $N$ , namely, “ $N$ factorial”. This is actually a very easy concept, and I’ll define it via example right now:

$5!=5\times 4\times 3\times 2\times 1$

$6!=6\times 5\times 4\times 3\times 2\times 1$

$2!=2\times 1$

$1!=1$

and so on. We also define $0!=1$ for various reasons. I.e., “N factorial” is just “1 times 2 times 3 times 4…times N”. Now it turns out that there are “N factorial” different permutations of N elements.

To see this, suppose we pick any element in our N-element set. Any permutation of this set will send this element somewhere, and we must include the possibility that the permutation sends it right back to itself (i.e., leaves it alone). Thus, there are N possible places to move this first element. Now pick a different element. We can send this second element anywhere except the place we sent the first element, for if we sent it to where we sent the first element then the function would not be bijective. Thus, there are $N-1$ places to send this second element. Now take another (third) element. We can send it anywhere except where we sent the first element or the second element. Thus we have $N-2$ places to send it. We continue this logic until we pick the last distinct element, and for that element we’ll only have 1 place to send it, as it’s destiny is fully determined by where we sent the first $N-1$ elements. Thus, we’ll get $N\times N-1\times N-2\times ...\times 1=N!$ different permutations! (now this exclamation point means excitement) The reason we multiply these numbers together is that once I’ve made my first choice (of N locations to send the first element), my second choice is completely unconstrained except for my inability to send it to the same place as the first. Thus I can make any of the first N choices, and then any of the next $N-1$ choices, and so on, so that I must multiply these numbers to account for all of my options.

To recap, we’ve developed some nice notation for dealing with permutations. This notation has helped give us some intuition for what’s going on with these groups, as well as a concise way for calculating products of permutations. We also (and somewhat randomly) found that there are $N!$ elements in the group $S_N$ , i.e., that there are $N!$ ways to permute $N$ elements. In fact, this is one motivation for defining “zero factorial” to be 1 instead of, say, zero—there is one way to permute the 0-element set (the empty set), and that is “do nothing”.

We’ll now go on to explore dihedral groups, which is a very geometric group, and from there we’ll start to develop some more abstract group machinery. Since this lesson has proved to be lengthy, I’ll skip the exercises (at least for now). If you want to put pen to paper, though, then I’d encourage you to get more used to manipulating and calculating product of permutations, seeing how it matters which permutation we “do first”, and to try to find interesting relationships between swaps and bigger parenthetical expressions. It turns out that any permutation can be written as a product of (many) swaps. Can you see how? (If not, have no fear, we’ll get to discussing this eventually (and in not too long)).

Previous Lesson

On to Lesson 26