The Unapologetic Mathematician

Mathematics for the interested outsider

Dimensions of Young Tabloid Modules

Last time our efforts to calculate the characters of the modules M^\lambda were stymied. But at least we can calculate their dimensions. The dimension of M^\lambda is the number of Young tabloids of shape \lambda.

Again, we pick some canonical Young tableau Y of shape \lambda so that every other tableau t can be written uniquely as t=\tau Y for some \tau\in S_n. That is, the set of all Young tabloids \{t\} is the orbit S_n\{Y\} 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 \{Y\} in S_n. That is, we must count the number of permutations \tau\in S_n with \tau Y row-equivalent to Y.

It doesn’t really matter which Y 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 1 to \lambda_1 on the first row, from \lambda_1+1 to \lambda_1+\lambda_2 on the second row, and so on. We write S_\lambda for the stabilizer of this choice, and this is the subgroup of S_n we will use. Notice that this is exactly the same subgroup we described earlier.

Anyway, now we know that Young tabloids \{\tau Y\} correspond to cosets of S_\lambda; if \tau'=\tau\pi for some \pi\in S_\lambda, then

\displaystyle\{\tau' Y\}=\{\tau\pi Y\}=\tau\{\pi Y\}=\tau\{Y\}=\{\tau Y\}

So we can count these cosets in the usual way:

\displaystyle[S_n:S_\lambda]=\lvert S_n\rvert/\lvert S_\lambda\rvert=n!/\lvert S_\lambda\rvert

How big is S_\lambda? Well, we know that

\displaystyle S_\lambda\cong S_{\lambda_1}\times\dots\times S_{\lambda_k}

and so

\displaystyle\lvert S_\lambda\rvert=\lvert S_{\lambda_1}\rvert\dots\lvert S_{\lambda_k}\rvert=\lambda_1!\dots\lambda_k!

Since it will come up so often, we will write this product of factorials as \lambda! for short. We can then write S_\lambda=\lambda! and thus we calculate n!/\lambda! for the number of cosets of S_\lambda in S_n. And so this is also the number of Young tabloids of shape \lambda, and also the dimension of M^\lambda.

Now, along the way we saw that the Young tabloid \{\tau Y\} corresponds to the coset \tau S_\lambda. It should be clear that the action of S_n on the Young tabloids is exactly the same as the coset action corresponding to S_\lambda. And thus the permutation module M^\lambda must be isomorphic to the induced representation 1\!\!\uparrow_{S_\lambda}^{S_n}.

December 16, 2010 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | Leave a Comment

Characters of Young Tabloid Modules (first pass)

Let’s try to calculate the characters of the Young tabloid modules M^\lambda we’ve constructed. Since these come from actions of S_n on various sets, we have our usual shortcut to calculate their characters: count fixed points.

So, let’s write \mu^\lambda for the character of the representation M^\lambda corresponding to the partition \lambda\vdash n. For a permutation \pi\in S_n, the character value \mu^\lambda(\pi) is the number of Young tabloids \{t\} such that \pi\{t\}=\{t\}. 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 Y. The easiest one just lists the numbers from 1 to n in order from left to right on rows from top to bottom of the tableau, like

\displaystyle\begin{array}{ccc}1&2&3\\4&5&6\\7&8&\\9&&\end{array}

but it really doesn’t matter which one we choose. The important thing is that any other tableau t has the form t=\tau Y for some unique \tau\in S_n. Now our fixed-point condition reads \pi\tau\{Y\}=\tau\{Y\}, or \tau^{-1}\pi\tau\{Y\}=\{Y\}. But as \tau runs over S_n, the conjugate \tau^{-1}\pi\tau runs over the conjugacy class K_\pi of \pi. What’s more, it runs evenly over the conjugacy class — exactly n!/\lvert K_\pi\rvert values of \tau give each element in K_\pi. So what we need to count is how many elements \sigma\in K_\pi give a tableau \sigma Y that is row-equivalent to Y. We multiply this by n!/\lvert K_\pi\rvert to get \mu^\lambda(\pi), right?

Well, no, because now we’ve overcounted. We’ve counted the number of tableaux \tau Y with \pi\{\tau Y\}=\{\tau Y\}. But we want the number of tabloids \{\tau Y\} with this property. For example, let’s try to count \mu^\lambda(e): there’s only one element in K_e, and it leaves Y fixed. Our rule above would have us multiply this 1 by n! to get n!=\mu^\lambda(e)=\dim(M^\lambda), but there are not always n! tabloids of shape \lambda!

The story is evidently more complicated than we might have hoped. Instead of letting \tau above range over all of S_n, we could try letting it only range over a transversal for the subgroup of S_n that preserves the rows of Y. But then there’s no obvious reason to assume that the conjugates of \pi should be evenly distributed over K_\pi, which complicates our counting. We’ll have to come back to this later.

December 15, 2010 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 1 Comment

Permutation Representations from Partitions

Now that we have an action of S_n on the Young tabloids of shape \lambda\vdash n, we can consider the permutation representation M^\lambda that corresponds to it. Let’s consider a few examples.

First, let \lambda=(n). This is a pretty trivial “partition”, consisting of one piece of length n. The Ferrers diagram of \lambda looks like

\displaystyle\begin{array}{cccc}\bullet&\bullet&\cdots&\bullet\end{array}

Any Young tableau thus contains all n numbers on the single row, so they’re all row-equivalent. There is only one Young tabloid:

\displaystyle\begin{array}{cccc}\cline{1-4}1&2&\cdots&n\\\cline{1-4}\end{array}

We conclude that M^{(n)} is a one-dimensional vector space with the trivial action of S_n.

Next, let \lambda=(1^n) — another simple partition with n parts of length 1 each. The Ferrers diagram looks like

\displaystyle\begin{array}{c}\bullet\\\bullet\\\vdots\\\bullet\end{array}

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

\displaystyle\begin{array}{c}\cline{1-1}1\\\cline{1-1}2\\\cline{1-1}\vdots\\\cline{1-1}n\\\cline{1-1}\end{array}

These tabloids correspond to permutations; a generic one looks like

\displaystyle\begin{array}{c}\cline{1-1}\pi(1)\\\cline{1-1}\pi(2)\\\cline{1-1}\vdots\\\cline{1-1}\pi(n)\\\cline{1-1}\end{array}

The action of S_n on these tabloids is basically the same as left-multiplication on the underlying set S_n. And so we find the left regular representation.

Finally, consider the partition \lambda=(n-1,1). This time the Ferrers diagram looks like

\displaystyle\begin{array}{cccc}\bullet&\bullet&\cdots&\bullet\\\bullet&&&\end{array}

and a sample Young tabloid looks like

\displaystyle\begin{array}{cccc}\cline{1-4}1&2&\cdots&n-1\\\cline{1-4}n&&&\\\cline{1-1}\end{array}

Any Young tabloid of shape \lambda is uniquely specified by the single entry on the second row. Any permutation shuffles them around exactly like it does these entries, and so M^{(n-1,1)} is isomorphic to the defining representation.

December 14, 2010 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 7 Comments

The Action on Tableaux and Tabloids

We’ve introduced Young tableaux and Young tabloids. We’ve also said that they carry symmetric group actions, but we never really said what they were.

So, let \lambda\vdash n be a partition, and consider the collection of Young tableaux of shape \lambda. I say that the symmetric group S_n acts on this set. Indeed, given a tableau t with entries t_{i,j}, and given a permutation \pi\in S_n, we define a new tableau \pi t by giving its entries:

\displaystyle(\pi t)_{i,j}=\pi(t_{i,j})

For example, we can calculate

\displaystyle (1\,2\,3)\begin{array}{cc}1&2\\3&\end{array}=\begin{array}{cc}2&3\\1&\end{array}

It should be clear that \pi t has an (i,j) entry if and only if t does, and so \pi t has the same shape as t does. Further, each number from 1 to n shows up exactly once as an entry in \pi t just as in t, and so \pi t really is a Young tableau of shape \lambda.

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 \lambda. That is, we can define \pi\{t\}=\{\pi t\}. The important thing here is to verify that the action is well-defined. But the action of the permutation \pi doesn’t care about the positions of the numbers within the tableau, so rearranging them has no effect. For example, we can check that

\displaystyle (1\,2\,3)\begin{array}{cc}2&1\\3&\end{array}=\begin{array}{cc}3&2\\1&\end{array}

Swapping the two numbers in the first row of the tableau before applying the permutation (1\,2\,3) 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 S_n. And so the action on Young tabloids is well-defined.

Given any two Young tabloids \{s\} and \{t\} of shape \lambda\vdash n, we have representative Young tableaux s and t. There is a unique \pi\in S_n such that \pi s=t, and so we have

\displaystyle\pi\{s\}=\{\pi s\}=\{t\}

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 t leaves the tabloid \{t\} the same.

December 13, 2010 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 2 Comments

Young Tabloids

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 (2,1):

\displaystyle\begin{aligned}\begin{array}{cc}\cline{1-2}1&2\\\cline{1-2}3&\\\cline{1-1}\end{array}&=\left\{\begin{array}{cc}1&2\\3&\end{array},\begin{array}{cc}2&1\\3&\end{array}\right\}\\\begin{array}{cc}\cline{1-2}1&3\\\cline{1-2}2&\\\cline{1-1}\end{array}&=\left\{\begin{array}{cc}1&3\\2&\end{array},\begin{array}{cc}3&1\\2&\end{array}\right\}\\\begin{array}{cc}\cline{1-2}2&3\\\cline{1-2}1&\\\cline{1-1}\end{array}&=\left\{\begin{array}{cc}2&3\\1&\end{array},\begin{array}{cc}3&2\\1&\end{array}\right\}\end{aligned}

If we have written the tableau abstractly as t, then the corresponding tabloid is \{t\} — the equivalence class of t.

December 11, 2010 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 10 Comments

Young Tableaux

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 \lambda\vdash n is a partition of n, we define a Young tableau of shape \lambda to be an array of numbers. We start with the Ferrers diagram of the partition \lambda, and we replace the dots with the numbers 1 to n in any order. Clearly, there are n! Young tableaux of shape \lambda if \lambda\vdash n.

For example, if \lambda=(2,1), the Ferrers diagram is

\displaystyle\begin{array}{cc}\bullet&\bullet\\\bullet&\end{array}

We see that (2,1)\vdash3, and so there are 3!=6 Young tableaux of shape (2,1). They are

\displaystyle\begin{aligned}\begin{array}{cc}1&2\\3&\end{array}&,&\begin{array}{cc}1&3\\2&\end{array}&,&\begin{array}{cc}2&1\\3&\end{array}\\\begin{array}{cc}2&3\\1&\end{array}&,&\begin{array}{cc}3&1\\2&\end{array}&,&\begin{array}{cc}3&2\\1&\end{array}\end{aligned}

We write t_{i,j} for the entry in the (i,j) place. For example, the last tableau above has t_{1,1}=3, t_{1,2}=2, and t_{2,1}=1.

We also call a Young tableau t of shape \lambda a “\lambda-tableau”, and we write \mathrm{sh}(t)=\lambda. We can write a generic \lambda-tableau as t^\lambda.

December 9, 2010 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 13 Comments

Partitions and Ferrers Diagrams

We’ve discussed partitions before, but they’re about to become very significant. Let \lambda=(\lambda_1,\dots,\lambda_k) be a sequence of positive integers with \lambda_1\geq\dots\geq\lambda_k. We write

\displaystyle\lvert\lambda\rvert=\sum\limits_{i=1}^k\lambda_i

If \lvert\lambda\rvert=n we say \lambda is a partition of n, and we write \lambda\vdash n. A partition, then, is a way of breaking a positive integer n 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 \lambda=(3,3,2,1), the Ferrers diagram of \lambda is

\displaystyle\begin{array}{ccc}\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet\\\bullet&\bullet&\\\bullet&&\end{array}

The diagram consists of left-justified rows, one for each part in the partition \lambda, and arranged from top to bottom in decreasing order. We can also draw the Ferrers diagram as boxes

\displaystyle\begin{array}{|c|c|c|}\cline{1-3}\hphantom{X}&\hphantom{X}&\\\cline{1-3}&&X\\\cline{1-3}&&\\\cline{1-2}&&\\\cline{1-1}\end{array}

The dangling vertical lines aren’t supposed to be there, but I’m having a hell of a time getting WordPress’ \LaTeX 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:

\displaystyle\begin{array}{ccc}\cline{1-3}\vline\hfill\hphantom{X}\hfill\vline&\hphantom{X}\hfill\vline&\hfill\vline\\\cline{1-3}\vline\hfill\hfill\vline&\hfill\vline&X\hfill\vline\\\cline{1-3}\vline\hfill\hfill\vline&\hfill\vline&\\\cline{1-2}\vline\hfill\hfill\vline&&\\\cline{1-1}\end{array}

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 X is placed in the (2,3) 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.

December 8, 2010 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 10 Comments

The Road Forward

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 G as there are conjugacy classes K\subseteq G. 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 S_n, there’s something we can say. We know that conjugacy classes in symmetric groups correspond to cycle types. Cycles correspond to integer partitions of n. And from a partition we will build a representation.

For a first step, let n=\lambda_1+\lambda_2+\dots+\lambda_k be a partition, with \lambda_1\geq\lambda_2\geq\dots\geq\lambda_k. We can use this to come up with a subgroup S_\lambda\subseteq S_n. Given a set X we will write S_X for the group of permutations of that set. For example S_{\{1,\dots,\lambda_1\}} permutes the first \lambda_1 positive integers, and S_{\{\lambda_1+1,\dots,\lambda_2\}} permutes the next \lambda_2 of them. We can put a bunch of these groups together to build

\displaystyle S_\lambda=S_{\{1,\dots,\lambda_1\}}\times S_{\{\lambda_1+1,\dots,\lambda_2\}}\times\dots\times S_{\{\lambda_{k-1}+1,\dots,\lambda_k\}}

Elements of S_\lambda permute the same set as S_n, and so S_\lambda\subseteq S_n, 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 \lambda_1 through \lambda_k, but choosing them like this is a nicely concrete way to do it.

So, now we can define the S_n-module M^\lambda=1\!\!\uparrow_{S_\lambda}^{S_n} by inducing the trivial representation from the subgroup S_\lambda to all of S_n. Now, the M^\lambda are not all irreducible, but we will see how to identify a particular irreducible submodule S^\lambda\subseteq M^\lambda of each one, and the S^\lambda will all be distinct. Since they correspond to partitions \lambda, there are exactly as many of them as there are conjugacy classes in S_n, and so they must be all the irreducible S_n-modules, up to isomorphism.

December 7, 2010 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 1 Comment

Inducing the Trivial Representation

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 G be a group and H be a subgroup. Since this will be coming up a bunch, let’s just start writing 1 for the trivial representation that sends each element of H to the 1\times1 matrix \begin{pmatrix}1\end{pmatrix}. We want to consider the induced representation 1\!\!\uparrow_H^G.

Well, we have a matrix representation, so we look at the induced matrix representation. We have to pick a transversal \{t_i\} for the subgroup H in G. Then we have the induced matrix in block form:

\displaystyle1\!\!\uparrow_H^G(g)=\begin{pmatrix}1(t_1^{-1}gt_1)&1(t_1^{-1}gt_2)&\cdots&1(t_1^{-1}gt_n)\\1(t_2^{-1}gt_1)&1(t_2^{-1}gt_2)&\cdots&1(t_2^{-1}gt_n)\\\vdots&\vdots&\ddots&\vdots\\1(t_n^{-1}gt_1)&1(t_n^{-1}gt_2)&\cdots&1(t_n^{-1}gt_n)\end{pmatrix}

In this case, each “block” is just a number, and it’s either 1 or 0, depending on whether t_i^{-1}gt_j is in H or not. But if t_i^{-1}gt_j\in H, then t_i^{-1}gt_jH=H, and latex g(t_jH)=(t_iH)$. That is, this is exactly the coset representation of G corresponding to H. And so all of these coset representations arise as induced representations.

December 6, 2010 Posted by | Algebra, Group theory, Representation Theory | 1 Comment

Dual Frobenius Reciprocity

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

\displaystyle\hom_H(W\!\!\downarrow^G_H,V)\cong\hom_G(W,V\!\!\uparrow_H^G)

Indeed, we can use the duality on hom spaces and apply it to yesterday’s Frobenius adjunction:

\displaystyle\begin{aligned}\hom_H(W\!\!\downarrow^G_H,V)&\cong\hom_H(V,W\!\!\downarrow^G_H)^*\\&\cong\hom_G(V\!\!\uparrow_H^G,W)^*\\&\cong\hom_G(W,V\!\!\uparrow_H^G)\end{aligned}

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 V has character \chi and W has character \psi, then hom-spaces become inner products, and (natural) isomorphisms become equalities. We find:

\displaystyle\langle\psi\!\!\downarrow^G_H,\chi\rangle_H=\langle\psi,\chi\!\!\uparrow_H^G\rangle_G

which is our “fake” Frobenius reciprocity relation.

December 3, 2010 Posted by | Algebra, Group theory, Representation Theory | 2 Comments

« Previous Entries     Next Entries »

Follow

Get every new post delivered to your Inbox.

Join 261 other followers