# The Unapologetic Mathematician

## 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

## 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

## 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

## 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

## 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

## 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

## 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

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

## 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

## 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