Again, we pick some canonical Young tableau of shape so that every other tableau can be written uniquely as for some . That is, the set of all Young tabloids is the orbit of the canonical one. By general properties of group actions we know that there is a bijection between the orbit and the index of the stabilizer of in . That is, we must count the number of permutations with row-equivalent to .
It doesn’t really matter which we pick; any two tableaux in the same orbit — and they’re all in the same single orbit — have isomorphic stabilizers. But like we mentioned last time the usual choice lists the numbers from to on the first row, from to on the second row, and so on. We write for the stabilizer of this choice, and this is the subgroup of we will use. Notice that this is exactly the same subgroup we described earlier.
Anyway, now we know that Young tabloids correspond to cosets of ; if for some , then
So we can count these cosets in the usual way:
How big is ? Well, we know that
Since it will come up so often, we will write this product of factorials as for short. We can then write and thus we calculate for the number of cosets of in . And so this is also the number of Young tabloids of shape , and also the dimension of .
Now, along the way we saw that the Young tabloid corresponds to the coset . It should be clear that the action of on the Young tabloids is exactly the same as the coset action corresponding to . And thus the permutation module must be isomorphic to the induced representation .
Let’s try to calculate the characters of the Young tabloid modules we’ve constructed. Since these come from actions of on various sets, we have our usual shortcut to calculate their characters: count fixed points.
So, let’s write for the character of the representation corresponding to the partition . For a permutation , the character value is the number of Young tabloids such that . This might be a little difficult to count on its face, but let’s analyze it a little more closely.
First of all, pick a canonical Young tableau . The easiest one just lists the numbers from to in order from left to right on rows from top to bottom of the tableau, like
but it really doesn’t matter which one we choose. The important thing is that any other tableau has the form for some unique . Now our fixed-point condition reads , or . But as runs over , the conjugate runs over the conjugacy class of . What’s more, it runs evenly over the conjugacy class — exactly values of give each element in . So what we need to count is how many elements give a tableau that is row-equivalent to . We multiply this by to get , right?
Well, no, because now we’ve overcounted. We’ve counted the number of tableaux with . But we want the number of tabloids with this property. For example, let’s try to count : there’s only one element in , and it leaves fixed. Our rule above would have us multiply this by to get , but there are not always tabloids of shape !
The story is evidently more complicated than we might have hoped. Instead of letting above range over all of , we could try letting it only range over a transversal for the subgroup of that preserves the rows of . But then there’s no obvious reason to assume that the conjugates of should be evenly distributed over , which complicates our counting. We’ll have to come back to this later.
First, let . This is a pretty trivial “partition”, consisting of one piece of length . The Ferrers diagram of looks like
Any Young tableau thus contains all numbers on the single row, so they’re all row-equivalent. There is only one Young tabloid:
We conclude that is a one-dimensional vector space with the trivial action of .
Next, let — another simple partition with parts of length each. The Ferrers diagram looks like
Now in every Young tableau each number is on a different line, so no two tableaux are row-equivalent. They each give rise to their own Young tabloid, such as
These tabloids correspond to permutations; a generic one looks like
The action of on these tabloids is basically the same as left-multiplication on the underlying set . And so we find the left regular representation.
Finally, consider the partition . This time the Ferrers diagram looks like
and a sample Young tabloid looks like
Any Young tabloid of shape is uniquely specified by the single entry on the second row. Any permutation shuffles them around exactly like it does these entries, and so is isomorphic to the defining representation.
So, let be a partition, and consider the collection of Young tableaux of shape . I say that the symmetric group acts on this set. Indeed, given a tableau with entries , and given a permutation , we define a new tableau by giving its entries:
For example, we can calculate
It should be clear that has an entry if and only if does, and so has the same shape as does. Further, each number from to shows up exactly once as an entry in just as in , and so really is a Young tableau of shape .
Since any tableau can be sent to any other by a judicious choice of permutation, this action is transitive. In fact, since there is exactly one permutation that works, the action is simply transitive.
Now, this action descends to an action on the set of Young tabloids of shape . That is, we can define . The important thing here is to verify that the action is well-defined. But the action of the permutation doesn’t care about the positions of the numbers within the tableau, so rearranging them has no effect. For example, we can check that
Swapping the two numbers in the first row of the tableau before applying the permutation gives the same result as first applying the permutation and then swapping the entries in the first row. Similarly, rearranging the entries in any row of any Young tableau commutes with the action of . And so the action on Young tabloids is well-defined.
Given any two Young tabloids and of shape , we have representative Young tableaux and . There is a unique such that , and so we have
Therefore the action on Young tabloids is transitive. It’s not simply transitive, though, since any permutation that only shuffles entries on the same row of a tableax leaves the tabloid the same.
Close cousins to Young tableaux, Young tabloids give us another set on which our symmetric group will act.
We say that two Young tableaux are “row-equivalent” if they contain the same entries in the same rows. That is, if we start with a Young tableau and shuffle the entries in each row — but never send an entry from one row to another row — then the resulting tableau is row-equivalent to the one we started with. Any two row-equivalent tableaux are related in this way.
We define a Young tabloid to be a row-equivalence class of Young tableaux, and we write it by writing down any tableau in the class, but with horizontal bars through it. As an example, there are three Young tabloids of shape :
If we have written the tableau abstractly as , then the corresponding tabloid is — the equivalence class of .
We want to come up with some nice sets for our symmetric group to act on. Our first step in this direction is to define a “Young tableau”.
If is a partition of , we define a Young tableau of shape to be an array of numbers. We start with the Ferrers diagram of the partition , and we replace the dots with the numbers to in any order. Clearly, there are Young tableaux of shape if .
For example, if , the Ferrers diagram is
We see that , and so there are Young tableaux of shape . They are
We write for the entry in the place. For example, the last tableau above has , , and .
We also call a Young tableau of shape a “-tableau”, and we write . We can write a generic -tableau as .
We’ve discussed partitions before, but they’re about to become very significant. Let be a sequence of positive integers with . We write
If we say is a partition of , and we write . A partition, then, is a way of breaking a positive integer into a bunch of smaller positive integers, and sorting them in (the unique) decreasing order.
We visualize partitions with Ferrers diagrams. The best way to explain this is with an example: if , the Ferrers diagram of is
The diagram consists of left-justified rows, one for each part in the partition , and arranged from top to bottom in decreasing order. We can also draw the Ferrers diagram as boxes
The dangling vertical lines aren’t supposed to be there, but I’m having a hell of a time getting WordPress’ processor to recognize an \hfill command so I can place \vline elements at the edges of columns. This should work but.. well, see for yourself:
So, if anyone knows how to make this look like the above diagram, but without the dangling vertical lines, I’d appreciate the help.
Anyway, in both of those ugly, ugly Ferrers diagrams, the is placed in the position; we see this by counting down two boxes and across three boxes. We will have plenty of call to identify which positions in a Ferrers diagram are which in the future.
We’ve been talking a lot about the general theory of finite group representations. But our goal is to talk about symmetric groups in particular. Now, we’ve seen that the character table of a finite group is square, meaning there are as many irreducible representations of a group as there are conjugacy classes . But we’ve also noted that there’s no reason to believe that these have any sort of natural correspondence.
But for the symmetric group , there’s something we can say. We know that conjugacy classes in symmetric groups correspond to cycle types. Cycles correspond to integer partitions of . And from a partition we will build a representation.
For a first step, let be a partition, with . We can use this to come up with a subgroup . Given a set we will write for the group of permutations of that set. For example permutes the first positive integers, and permutes the next of them. We can put a bunch of these groups together to build
Elements of permute the same set as , and so , but only in certain discrete chunks. Numbers in each block can be shuffled arbitrarily among each other, but the different blocks are never mixed. Really, all that matters is that the chunks have sizes through , but choosing them like this is a nicely concrete way to do it.
So, now we can define the -module by inducing the trivial representation from the subgroup to all of . Now, the are not all irreducible, but we will see how to identify a particular irreducible submodule of each one, and the will all be distinct. Since they correspond to partitions , there are exactly as many of them as there are conjugacy classes in , and so they must be all the irreducible -modules, up to isomorphism.
We really should see an example of inducing a representation. One example we’ll find extremely useful is when we start with the trivial representation.
So, let be a group and be a subgroup. Since this will be coming up a bunch, let’s just start writing for the trivial representation that sends each element of to the matrix . We want to consider the induced representation .
Well, we have a matrix representation, so we look at the induced matrix representation. We have to pick a transversal for the subgroup in . Then we have the induced matrix in block form:
In this case, each “block” is just a number, and it’s either or , depending on whether is in or not. But if , then latex g(t_jH)=(t_iH)$. That is, this is exactly the coset representation of corresponding to . And so all of these coset representations arise as induced representations.
Our proof of Frobenius reciprocity shows that induction is a left-adjoint to restriction. In fact, we could use this to define induction in the first place; show that restriction functor must have a left adjoint and let that be induction. The downside is that we wouldn’t get an explicit construction for free like we have.
One interesting thing about this approach, though, is that we can also show that restriction must have a right adjoint, which we might call “coinduction”. But it turns out that induction and coinduction are naturally isomorphic! That is, we can show that
Indeed, we can use the duality on hom spaces and apply it to yesterday’s Frobenius adjunction:
Sometimes when two functors are both left and right adjoints of each other, we say that they are a “Frobenius pair”.
Now let’s take this relation and apply our “decategorifying” correspondence that passes from representations down to characters. If the representation has character and has character , then hom-spaces become inner products, and (natural) isomorphisms become equalities. We find:
which is our “fake” Frobenius reciprocity relation.