The Unapologetic Mathematician

Examples of Specht Modules

Let’s look at a few examples of Specht modules.

First, let $\lambda=(n)$. The only polytabloid is

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

on which $S_n$ acts trivially. And so $S^\lambda$ is a one-dimensional space with the trivial group action. This is the only possibility anyway, since $S^\lambda\subseteq M^\lambda$, and we’ve seen that $M^\lambda$ is itself a one-dimensional vector space with the trivial action of $S_n$.

Next, consider $\lambda=(1^n)$ — with $n$ parts each of size $1$. This time we again have one polytabloid. We fix the Young tableau

$\displaystyle t=\begin{array}{c}1\\2\\\vdots\\n\end{array}$

Since every entry is in the same column, the column-stabilizer $C_t$ is all of $S_n$. And so we calculate the polytabloid

$\displaystyle e_t=\sum\limits_{\sigma\in S_n}\mathrm{sgn}(\sigma)\sigma\{t\}$

We use our relations to calculate

\displaystyle\begin{aligned}\pi e_t&=\sum\limits_{\sigma\in S_n}\mathrm{sgn}(\sigma)\pi\sigma\{t\}\\&=\sum\limits_{\tau\in S_n}\mathrm{sgn}(\pi^{-1}\tau)\tau\{t\}\\&=\sum\limits_{\tau\in S_n}\mathrm{sgn}(\pi^{-1})\mathrm{sgn}(\tau)\tau\{t\}\\&=\mathrm{sgn}(\pi^{-1})\sum\limits_{\tau\in S_n}\mathrm{sgn}(\tau)\tau\{t\}\\&=\mathrm{sgn}(\pi)e_t\end{aligned}

We conclude that $S^\lambda\subseteq M^\lambda$ is a one-dimensional space with the signum representation of $S_n$. Unlike our previous example, there is a huge difference between $S^\lambda$ and $M^\lambda$; we’ve seen that $M^\lambda$ is actually the left regular representation, which has dimension $n!$.

Finally, if $\lambda(n-1,1)$, then we can take a tableau and write a tabloid

$\displaystyle\left\{\begin{array}{ccc}i&\dots&j\\k&&\end{array}\right\}=\mathbf{k}$

where the notation we’re using on the right is well-defined since each tabloid is uniquely identified by the single entry in the second row. Now, the polytabloid in this case is $e_t=\mathbf{k}-\mathbf{i}$, since the only column rearrangement is to swap $i$ and $k$. It’s straightforward to see that these polytabloids span the subspace of $M^\lambda$ where the coefficients add up to zero:

$\displaystyle c_1\mathbf{1}+\dots+c_n\mathbf{n}\in S^\lambda\quad\Leftrightarrow\quad\sum\limits_{i=1}^nc_i=0$

As a basis, we can pick $\{\mathbf{2}-\mathbf{1},\mathbf{3}-\mathbf{1},\dots,\mathbf{n}-\mathbf{1}\}$. We recognize this pattern from when we calculated the invariant subspaces of the defining representation of $S_3$. And indeed, $M^\lambda$ is the defining representation of $S_n$, which contains $S^\lambda$ as the analogous submodule to what we called $V^\perp$ before.

December 28, 2010

Specht Modules

Now we have everything in place to define the representations we’re interested in. For any partition $\lambda$, the Specht module $S^\lambda$ is the submodule of the Young tabloid module $M^\lambda$ spanned by the polytabloids $e_t$ where $t$ runs over the Young tableaux $t$ of shape $\lambda$.

To see that the subspace spanned by the polytabloids is a submodule, we must see that it’s invariant under the action of $S_n$. We can use our relations to check this. Indeed, if $e_t$ is a polytabloid, then $\pi e_t=e_{\pi t}$ is another polytabloid, so the subspace spanned by the polytabloids is invariant under the action of $S_n$.

The most important fact about the Specht modules is that they’re cyclic. That is, we can generate one just by starting with a single vector and hitting it with all the elements in the group algebra $\mathbb{C}[S_n]$. Not all of the resulting vectors will be different, but among them we’ll get the whole Specht module. The term “cyclic” comes from group theory, where the cyclic groups are those from modular arithmetic, like $\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$. Many integers give the same residue class modulo $n$, but every residue class comes from some integer.

Anyway, in the case of Specht modules, we will show that the action of $S_n$ can take one vector and give a whole basis for $S^\lambda$. Then any vector in the Specht module can be written as a sum of basis vectors, and thus as the action of some algebra element from $\mathbb{C}[S_n]$ on our starting vector. But which starting vector will we choose? Well, any polytabloid will do. Indeed, if $e_s$ and $e_t$ are polytabloids, then there is some (not unique!) permutation $\pi$ so that $t=\pi s$. But then $e_t=e_{\pi s}=\pi e_s$, and so $e_t$ is in the $S_n$-orbit of $e_s$. Thus starting with $e_s$ we can get to every vector in $S^\lambda$ by the action of $\mathbb{C}[S_n]$.

December 27, 2010

Permutations and Polytabloids

We’ve defined a bunch of objects related to polytabloids. Let’s see how they relate to permutations.

First of all, I say that

$\displaystyle R_{\pi t}=\pi R_t\pi^{-1}$

Indeed, what does it mean to say that $\sigma\in R_{\pi t}$? It means that $\sigma$ preserves the rows of the tableau $\pi t$. And therefore it acts trivially on the tabloid $\{\pi t\}$. That is: $\sigma\{\pi t\}=\{\pi t\}$. But of course we know that $\{\pi t\}=\pi\{t\}$, and thus we rewrite $\sigma\pi\{t\}=\pi\{t\}$, or equivalently $\pi^{-1}\sigma\pi\{t\}=\{t\}$. This means that $\pi^{-1}\sigma\pi\in R_t$, and thus $\sigma\in\pi R_t\pi^{-1}$, as asserted.

Similarly, we can show that $C_{\pi t}=\pi C_t\pi^{-1}$. This is slightly more complicated, since the action of the column-stabilizer on a Young tabloid isn’t as straightforward as the action of the row-stabilizer. But for the moment we can imagine a column-oriented analogue of Young tabloids that lets the same proof go through. From here it should be clear that $\kappa_{\pi t}=\pi\kappa_t\pi^{-1}$.

Finally, I say that the polytabloid $e_{\pi t}$ is the same as the polytabloid $\pi e_t$. Indeed, we compute

$\displaystyle e_{\pi t}=\kappa_{\pi t}\{\pi t\}=\pi\kappa_t\pi^{-1}\pi\{t\}=\pi\kappa_t\{t\}=\pi e_t$

December 24, 2010

Polytabloids

Given any collection $H\subseteq S_n$ of permutations, we define two group algebra elements.

\displaystyle\begin{aligned}H^+&=\sum\limits_{\pi\in H}\pi\\H^-&=\sum\limits_{\pi\in H}\mathrm{sgn}(\pi)\pi\end{aligned}

Notice that $H$ doesn’t have to be a subgroup, though it often will be. One particular case that we’ll be interested in is

$\displaystyle\kappa_t=C_t^-=\sum\limits_{\pi\in C_t}\mathrm{sgn}(\pi)\pi$

where $C_t$ is the column-stabilizer of a Young tableau $t$. If $t$ has columns $C_1,\dots,C_k$, then $C_t=S_{C_1}\times\dots\times S_{C_k}$. Letting $\pi$ run over $C_t$ is the same as letting $\pi_i$ run over $S_{C_i}$ for each $i$ from $1$ to $k$. That is,

\displaystyle\begin{aligned}\kappa_t&=\sum\limits_{\pi_1\in S_{C_1}}\dots\sum\limits_{\pi_k\in S_{C_k}}\mathrm{sgn}(\pi_1\dots\pi_k)\pi_1\dots\pi_k\\&=\sum\limits_{\pi_1\in S_{C_1}}\dots\sum\limits_{\pi_k\in S_{C_k}}\mathrm{sgn}(\pi_1)\dots\mathrm{sgn}(\pi_k)\pi_1\dots\pi_k\\&=\left(\sum\limits_{\pi_1\in S_{C_1}}\mathrm{sgn}(\pi_1)\pi_1\right)\dots\left(\sum\limits_{\pi_k\in S_{C_k}}\mathrm{sgn}(\pi_k)\pi_k\right)\end{aligned}

so we have a nice factorization of this element.

Now if $t$ is a tableau, we define the associated “polytabloid”

$\displaystyle e_t=\kappa_t\{t\}$

Now, as written this doesn’t really make sense. But it does if we move from just considering Young tabloids to considering the vector space of formal linear combinations of Young tabloids. This means we use Young tabloids like basis vectors and just “add” and “scalar multiply” them as if those operations made sense.

As an example, consider the tableau

$\displaystyle t=\begin{array}{ccc}4&1&2\\3&5&\end{array}$

Our factorization lets us write

$\displaystyle\kappa_t=\left(e-(3\,4)\right)\left(e-(1\,5)\right)$

And so we calculate

$\displaystyle e_t=\begin{array}{ccc}\cline{1-3}4&1&2\\\cline{1-3}3&5&\\\cline{1-2}\end{array}-\begin{array}{ccc}\cline{1-3}3&1&2\\\cline{1-3}4&5&\\\cline{1-2}\end{array}-\begin{array}{ccc}\cline{1-3}4&5&2\\\cline{1-3}3&1&\\\cline{1-2}\end{array}+\begin{array}{ccc}\cline{1-3}3&5&2\\\cline{1-3}4&1&\\\cline{1-2}\end{array}$

Now, the nice thing about $e_t$ is that if we hit it with any permutation $\pi\in C_t$, we get $\pi e_t=\mathrm{sgn}(\pi)e_t$.

December 23, 2010

Row- and Column-Stabilizers

Every Young tableau $t^\lambda$ with shape $\lambda\vdash n$ gives us two subgroups of $S_n$, the “row-stabilizer” $R_t$ and the “column-stabilizer” $C_t$. These are simple enough to define, but to write them succinctly takes a little added flexibility to our notation.

Given a set $X$, we’ll write $S_X$ for the group of permutations of that set. For instance, the permutations that only mix up the elements of the set $\{1,2,4\}$ make up $S_{\{1,2,4\}}$

Now, let’s say we have a tableau $t$ with rows $R_1,\dots,R_k$. Any permutation that just mixes up elements of $R_1$ leaves all but the first row alone when acting on $t$. Since it leaves every element on the row where it started, we say that it stabilizes the rows of $t$. These permutations form the subgroup $S_{R_1}$. Of course, there’s nothing special about $R_1$ here; the subgroups $S_{R_i}$ also stabilize the rows of $t$. And since entries from two different subgroups commute, we’re dealing with the direct product:

$\displaystyle R_t=S_{R_1}\times\dots\times S_{R_k}$

We say that $R_t$ is the row-stabilizer subgroup, since it consists of all the permutations that leave every entry in $t$ on the row where it started. Clearly, this is the stabilizer subgroup of the Young tabloid $\{t\}$.

The column-stabilizer is defined similarly. If $t$ has columns $C_1,\dots,C_l$, then we define the column-stabilizer subgroup

$\displaystyle C_t=S_{C_1}\times\dots\times S_{C_l}$

Now column-stabilizers do act nontrivially on the tabloid $\{t\}$. The interaction between rearranging rows and columns of tableaux will give us the representations of $S_n$ we’re looking for.

December 22, 2010

The Lexicographic Order on Partitions

The biggest problem with the dominance order is that it’s only a partial order. That is, there are some pairs of partitions $\lambda$ and $\mu$ so that neither $\lambda\trianglerighteq\mu$ nor $\mu\triangleright\lambda$. We sometimes need a total order, and that’s where the lexicographic order comes in.

The lexicographic order gets its name because it’s just like the way we put words in order in the dictionary. We compare the first parts of each partition. If they’re different we use their order, while if they’re the same we break ties with the tails of the partitions. More explicitly, $\lambda<\mu$ if for some $i$ we have $\lambda_j=\mu_j$ for all $j, and $\lambda_i<\mu_i$.

As an example, here’s the lexicographic order on the partitions of $6$:

\displaystyle\begin{aligned}(6)&>(5,1)\\&>(4,2)\\&>(4,1,1)\\&>(3,3)\\&>(3,2,1)\\&>(3,1,1,1)\\&>(2,2,2)\\&>(2,2,1,1)\\&>(2,1,1,1,1)\\&>(1,1,1,1,1,1)\end{aligned}

Now, comparing this order to the dominance order, we notice that they’re almost the same. Specifically, every time $\lambda\trianglerighteq\mu$, we find $\lambda>\mu$ as well.

If $\lambda=\mu$, then this is trivially true. But if $\lambda\neq\mu$ there must be at least one $i$ with $\lambda_i\neq\mu_i$. Let $i$ be the first such index. Now we find that

$\displaystyle\sum\limits_{j=1}^{i-1}\lambda_j=\sum\limits_{j=1}^{i-1}\mu_j$

and also

$\displaystyle\sum\limits_{j=1}^i\lambda_j>\sum\limits_{j=1}^i\mu_j$

This inequality must go in this direction since $\lambda\triangleright\mu$. We conclude that $\lambda_i>\mu_i$, and so $\lambda>\mu$ in the lexicographic order.

December 21, 2010

The Dominance Lemma

We will have use of the following technical result about the dominance order:

Let $t^\lambda$ and $s^\mu$ be Young tableaux of shape $\lambda$ and $\mu$, respectively. If for each row, all the entries on that row of $s^\mu$ are in different columns of $t^\lambda$, then $\lambda\trianglerighteq\mu$. Essentially, the idea is that since all the entries on a row in $s$ fit into different columns of $t$, the shape of $t$ must be wide enough to handle that row. Not only that, but it’s wide enough to handle all of the rows of that width at once.

More explicitly, we can rearrange the columns of $t$ so that all the entries in the first $i$ rows of $s$ fit into the first $i$ rows of $t$. This is actually an application of the pigeonhole principle: if we have a column in $t$ that contains $i+1$ elements from the first $i$ rows of $s$, then look at which row each one came from. Since $i+1>i$, we must have two entries in the column coming from the same row, which we assumed doesn’t happen.

Yes, this does change the tableau $t$, but our conclusion is about the shape of $t$, which remains the same.

So now we can figure $\lambda_1+\dots+\lambda_i$ as the number of entries in the first $i$ rows of $t^\lambda$. Since these contain all the entries from the first $i$ rows of $s^\mu$, it must be greater than or equal to that number. But that number is just as clearly $\mu_1+\dots+\mu_i$. Since this holds for all $i$, we conclude that $\lambda$ dominates $\mu$.

December 20, 2010

The Dominance Order on Partitions

Now we want to introduce a partial order on the collection of partitions called the “dominance order”. Given partitions $\lambda=(\lambda_1,\dots,\lambda_k)$ and $\mu=(\mu_1,\dots,\mu_l)$, we say that $\lambda$ “dominates” $\mu$ — and we write $\lambda\trianglerighteq\mu$ — if

$\displaystyle\lambda_1+\lambda_2+\dots+\lambda_i\geq\mu_1+\mu_2+\dots+\mu_i$

for all $i\geq1$.

We can interpret this by looking at their Ferrers diagrams. First look at the first rows of the diagrams. Are there more dots in the diagram for $\lambda$ than in that for $\mu$? If so, so far so good; move on to the second row. Now are there more dots in the first two rows for $\lambda$ than there are in the first two rows for $\mu$? If so, keep going. If ever there are more dots above the $i$th row in the Ferrers diagram of $\mu$ than there are in the Ferrers diagram for $\lambda$, then the condition fails. If ever we run out of rows in one diagram, we just say that any lower rows we need have length zero.

Let’s consider two partitions of $6$: $\lambda=(4,2)$ and $\mu=(3,2,1)$. They have the following Ferrers diagrams:

$\displaystyle\begin{array}{cccc}\bullet&\bullet&\bullet&\bullet\\\bullet&\bullet&&\end{array}\qquad\begin{array}{ccc}\bullet&\bullet&\bullet\\\bullet&\bullet&\\\bullet&&\end{array}$

In the first rows, $\lambda$ has four dots while $\mu$ has three, and $4\geq3$. Moving on, $\lambda$ has six dots in the first two rows while $\mu$ has five, and $6\geq5$. Finally, $\lambda$ has six dots (still!) in the first three rows while $\mu$ also has six, and $6\geq6$. Since the inequality holds for all positive $i$, we find that $\lambda$ dominates $\mu$.

As another example, let $\lambda=(3,3)$ and $\mu=(4,1,1)$:

$\displaystyle\begin{array}{ccc}\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet\end{array}\qquad\begin{array}{cccc}\bullet&\bullet&\bullet&\bullet\\\bullet&&&\\\bullet&&&\end{array}$

This time, the first rows have three and four dots, respectively — $\lambda_1\leq\mu_1$. We’re on our way to showing that $\lambda\trianglelefteq\mu$. But the first two rows have six dots and five dots, respectively — $\lambda_1+\lambda_2\geq\mu_1+\mu_2$. Since the inequality has flipped sides, neither one of these partitions can dominate the other. Dominance is evidently only a partial order, not a total order.

We can put all the partitions of $n$ into a structure called a “Hasse diagram”, which tells us at a glance which partitions dominate which. This is a graph with partitions at the verices. We draw an arrow from $\mu$ to $\lambda$ if $\lambda\trianglerighteq\mu$. For partitions of $6$, this looks like

$\displaystyle\begin{array}{ccccc}&&(6)&&\\&&\uparrow&&\\&&(5,1)&&\\&&\uparrow&&\\&&(4,2)&&\\&\nearrow&&\nwarrow&\\(3,3)&&&&(4,1,1)\\&\nwarrow&&\nearrow&\\&&(3,2,1)&&\\&\nearrow&&\nwarrow&\\(3,1,1,1)&&&&(2,2,2)\\&\nwarrow&&\nearrow&\\&&(2,2,1,1)&&\\&&\uparrow&&\\&&(2,1,1,1,1)&&\\&&\uparrow&&\\&&(1,1,1,1,1,1)&&\end{array}$

December 17, 2010

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