Okay, I’m done with measure theory (for now, at least), and not a moment too soon. It’s been good for me to work through all this stuff again, and I hope it’s provided a good resource, but my traffic has really taken a hit, at least as measured by daily page views. I think maybe everybody else hates analysis too?
So let’s go in a completely different direction! I want to talk about the representation theory of permutation groups. Now at least on the surface you might not think there’s a lot to say, but it’s a surprisingly detailed subject. And since every finite group can be embedded in a permutation group — its action on itself by left multiplication permutes its own elements — and many natural symmetries come in the form of permutations, it’s a very useful subject as well.
But as a niche it doesn’t get taught very much. Even the most direct application I know (the representation theory of classical groups) usually avoids getting into the details of this topic. And so it’s likely that many if not most readers haven’t really seen much of it. Along the way we’ll learn a certain amount about the representation theory of more general finite groups, so if you don’t know much about it yet, don’t worry! I’ll try to link back to more general background information where appropriate — and please ask me to fill in points that I seem to skim over — but the coverage should be pretty self-contained. The great thing about this is that you don’t have to have read anything else I’ve written, and you don’t have to be a particularly expert mathematician to follow along! And of course neither do your friends and acquaintances, so this is the perfect chance to pass the word along. Don’t be shy about telling other people to join in!
There’s also going to be a fair amount of focus on the combinatorics involved in the representation theory, and there are some really amazingly beautiful patterns. But we’ll also see some very explicit descriptions of how to actually count these things. If I feel up to it, I may try to actually implement some of the algorithms we see and talk about that over at my new programming weblog The Unapologetic Programmer. Oh yeah: if you haven’t heard yet, I’ve got a new weblog about programming, so all of you into software design should be heading over there and adding it to your RSS reader. And since my work there is a lot more casual, you should tell your other programmer friends about it too!
So enough shameless self-promotion; let’s get down to business.
Okay, here’s a classic bit of combinatorics that I’m almost surprised I never mentioned before: how to count permutations and combinations.
Back when I defined permutation groups, I gave a quick argument about how to count their orders. That is, how many elements are in the group . If we’re permuting the set of numbers through , first we have to choose where to send . There are possible choices of how to do this. Then we have to choose where to send , which can be anywhere but the place we sent . Thus there are choices of how to do this. And so on we go, making choices of where to send , choices of where to send . And so in total we have permutations.
Notice that what we’ve really done there is picked out an ordering on the set . More specifically, we’ve picked an ordering of the whole set. But what if we want to pick out only an ordered subset? That is, what if we want to pick out an ordered list of numbers from the set with no repetitions? Well, since there’s only one order type for each finite cardinal number, let’s just pick one as the model for our ordered list. Specifically, we’ll use the numbers from to , in their usual order.
Now we’ll take an injective function from to . The image subset will be our list, and we carry over the order from onto it. But now we can reuse the same argument as above! First we have choices where to send , and then choices where to send , and so on until we have choices of where to send . So there are such ordered subsets of length . This gets called the number of permutations with elements, and written as , or or . Notice that when this reduces to the factorial as above.
There’s an easy way to express this number in notation we already know. First we can multiply all the numbers from to , and then we can divide out the ones from to . That is, . What does this mean? Well, the up top means that we’re ordering all the elements of our set. But then since we only care about the first we don’t care about the order on the last elements. What’s hiding here is that the group is secretly acting on the set of all permutations of our set by rearranging the last elements of the permutation. What’s more, it acts freely — with no fixed points — so every orbit has the same size: . But since we only care about the first places in the permutation, we’re really interested in the number of orbits. That is, the total number of permutations divided by the size of each orbit: . And this is the formula we came up with before.
This is a general principle in combinatorics. It’s often possible to see the set you’re trying to count as a larger set modulo the free action of some group. Then the cardinality of the set you’re interested in is the cardinality of the larger set divided by the order of the group.
To see this in action, what if we don’t care about the order of our subset? That is, we just want to pick out elements with no repetitions and no care about what order they come in. Well, first we can pick out an ordered set of elements. Then we can use the group to rearrange them. Any rearrangement is just as good as any other, and the group acts freely on the set of permutations. That is, the number of unordered subsets is the number of ordered subsets — — divided by the order of the group — . This number of unordered subsets we call the number of “combinations” of an element set with elements. This is often written as , or , or , or , and they all are given by the formula .