# The Unapologetic Mathematician

## Consequences of the Submodule Theorem

We have a number of immediate consequences of the submodule theorem. First, and most important, the Specht modules form a complete list of irreducible modules for the symmetric group $S_n$. We know that they’re irreducible, and that there’s one of them for each partition $\lambda\vdash n$, which is the number of modules we’re looking for. But we need to show that the Specht modules corresponding to distinct partitions are themselves distinct. For this, we’ll use a lemma.

If $\theta\in\mathrm{hom}_{S_n}(S^\lambda,M^\mu)$ is a nonzero intertwinor, then $\lambda\trianglerighteq\mu$. Further, if $\lambda=\mu$, then $\theta$ must be multiplication by a scalar. Indeed, since $\theta\neq0$ there must be some polytabloid $e_t$ with $\theta(e_t)\neq0$. We decompose $M^\lambda=S^\lambda\oplus{S^\lambda}^\perp$, and extent $\theta$ to all of $M^\lambda$ by sending every vector in ${S^\lambda}^\perp$ to $0$. That is:

\displaystyle\begin{aligned}0&\neq\theta(e_t)\\&=\theta(\kappa_t\{t\})\\&=\kappa_t\theta(\{t\})\\&=\kappa_t\left(\sum\limits_ic_i\{s_i\}\right)\\&=\sum_ic_i\kappa_t(\{s_i\})\end{aligned}

where the $s_i$ are $\mu$-tableaux. Now, the $\kappa_t(\{s_i\})$ can’t all be zero, so we must have at least one $\mu$-tableau $s^\mu$ so that $\kappa_t\{s\}\neq0$. But then our corollary of the sign lemma tells us that $\lambda\trianglerighteq\mu$, as we asserted!

Further, if $\lambda=\mu$, then our other corollary shows us that $\theta(e_t)=ce_t$ for some scalar $c$. We can thus calculate

\displaystyle\begin{aligned}\theta(e_{\pi t})&=\theta(\pi e_t)\\&=\pi\theta(e_t)\\&=\pi ce_t\\&=ce_{\pi t}\end{aligned}

and so $\theta$ multiplies every vector by $c$.

As a consequence, the $S^\mu$ must be distinct for distinct permutations, since if $S^\lambda=S^\mu\subseteq M^\mu$ then there is a nonzero homomorphism $S^\lambda\to M^\mu$, and thus $\lambda\trianglerighteq\mu$. But the same argument shows that $\mu\trianglerighteq\lambda$, and thus $\lambda=\mu$.

More particularly, we have a decomposition

$\displaystyle M^\mu=\bigoplus\limits_{\lambda\trianglerighteq\mu}m_{\lambda\mu}S^\lambda$

where the diagonal multiplicities are $m_{\lambda\lambda}=1$. The rest of these multiplicities will eventually have a nice interpretation.

January 4, 2011

## The Submodule Theorem

Sorry for the delay.

Let $U\subseteq M^\mu$ be a submodule of one of the Young tabloid modules. Then I say that either $U$ contains the Specht module $S^\mu\subseteq M^\mu$, or it is contained in the orthogonal complement ${S^\mu}^\perp\subseteq M^\mu$. In particular, each Specht module $S^\mu$ is irreducible, since any nontrivial submodule $U\subseteq S^\mu$ cannot be contained in the orthogonal complement, and so it must also contain — and thus be equal to — $S^\mu$.

To see this, let $u\in U\subseteq M^\mu$ be any vector, and let $t^\mu$ be a $\mu$-tableau. Our last result showed us that $\kappa_tu=ce_t$ for some $c\in\mathbb{C}$. First, we’ll assume that there is some pair of $u$ and $t$ so that $c\neq0$. In this case, $e_t=\frac{1}{c}\kappa_tu\in U$. Since $e_t$ generates all of $S^\mu$ — the Specht modules are cyclic — we must have $S^\mu\subseteq U$.

On the other hand, what if there is no such pair of $u$ and $t$? That is, $\kappa_tu=0$ for all vectors $u\in U$ and $\mu$-tableaux $t$. We can calculate

\displaystyle\begin{aligned}\langle u,e_t\rangle&=\langle u,\kappa_t\{t\}\rangle\\&=\langle\kappa_tu,\{t\}\rangle\\&=\langle0,\{t\}\rangle\\&=0\end{aligned}

So each vector $u\in U$ is orthogonal to each polytabloid $e_t$. Since the polytabloids span $S^\mu$, we must have $U\subseteq{S^\mu}^\perp$.

January 4, 2011

## Corollaries of the Sign Lemma

The results we showed last time have a few immediate consequences we will have use of.

First, let $t^\lambda$ and $s^\mu$ are two Young tableaux of shapes $\lambda$ and $\mu$, respectively, where $\lambda\vdash n$ and $\mu\vdash n$. If $\kappa_t\{s\}\neq0$ — where $\kappa_t$ is the group algebra element we’ve defined — then $\lambda$ dominates $\mu$.

To see this, let $b$ and $c$ be two entries in the same row of $s$. They cannot be in the same column of $t$, since if they were then the swap $(b\,c)$ would be in the column-stabilizer $C_t$. Then we could conclude that $\kappa_t\{s\}=C_t^-\{s\}=0$, which we assumed not to be the case. But if no two entries from the same row of $s^\mu$ are in the same column of $t^\lambda$, the dominance lemma tells us that $\lambda\trianglerighteq\mu$.

Now if it turns out that $\lambda=\mu$ it’s not surprising that $\lambda\trianglerighteq\mu$. Luckily in that situation we can say something interesting:

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

Indeed, we must have $\{s\}=\pi\{t\}$ for some $\pi\in C_t$, basically by the same reasoning that led to the dominance lemma in the first place. Indeed, the thing that would obstruct finding such a $\pi$ is having two entries in some column of $t$ needing to go on the same row of $s$, which we know doesn’t happen. And so we calculate

\displaystyle\begin{aligned}\kappa_t\{s\}&=\kappa_t\pi\{t\}\\&=\mathrm{sgn}(\pi)\kappa_t\{t\}\\&=\pm e_t\end{aligned}

Now if $u\in M^\mu$ is any vector in the Specht module, and if $t^\mu$ is a tableau of shape $\mu$, then $\kappa_t u$ is some multiple of $e_t$. Indeed, we can write

$\displaystyle u=\sum\limits_ic_i\{s_i\}$

were the $s_i$ are $\mu$-tableaux. For each one of these, we have $\kappa_t\{s_i\}=\pm e_t$. Thus we find

$\displaystyle\kappa_tu=\sum\limits_i\pm c_ie_t$

which is a multiple of $e_t$, as asserted.

December 31, 2010

## The Sign Lemma

As we move towards proving the useful properties of Specht modules, we will find the following collection of results helpful. Through them all, let $H\subseteq S_n$ be a subgroup, and also consider the $S_n$-invariant inner product on $M^\lambda$ for which the distinct Young tabloids form an orthonormal basis.

First, if $\pi\in H$, then

$\displaystyle\pi H^-=H^-\pi=\mathrm{sgn}(\pi)H^-$

where $H^-$ is the alternating sum of the elements of $H$. The proof basically runs the same as when we showed that $\pi e_t=\mathrm{sgn}(\pi)e_t$ where $t$ has shape $(1^n)$.

Next, for any vectors $u,v\in M^\lambda$ we have

$\displaystyle\langle H^-u,v\rangle=\langle u,H^-v\rangle$

Indeed, we can calculate

\displaystyle\begin{aligned}\langle H^-u,v\rangle&=\sum\limits_{\pi\in H}\langle\mathrm{sgn}(\pi)\pi u,v\rangle\\&=\sum\limits_{\pi\in H}\langle u,\mathrm{sgn}(\pi)\pi^{-1}v\rangle\\&=\sum\limits_{\pi\in H}\langle u,\mathrm{sgn}(\pi^{-1})\pi^{-1}v\rangle\\&=\sum\limits_{\tau\in H}\langle u,\mathrm{sgn}(\tau)\tau v\rangle\\&=\langle u,H^-v\rangle\end{aligned}

where we have used the facts that $\mathrm{sgn}(\pi)=\mathrm{sgn}(\pi^{-1})$, and that as $\pi$ runs over a group, so does $\tau=\pi^{-1}$.

Next, if the swap $(b\,c)\in H$, then we have the factorization

$\displaystyle H^-=k(1-(b\,c))$

for some $k\in\mathbb{C}[S_n]$. To see this, consider the subgroup $K=\{1,(b\,c)\}\subseteq H$, and pick a transversal. That is, write $H$ as a disjoint union:

$\displaystyle H=\biguplus\limits_ik_iK$

but then we can write the alternating sum

\displaystyle\begin{aligned}H^-&=\sum\limits_{\pi\in H}\mathrm{sgn}(\pi)\pi\\&=\sum\limits_i\left(\mathrm{sgn}(k_i)k_i+\mathrm{sgn}(k_i(b\,c))k_i(b\,c)\right)\\&=\sum\limits_i\left(\mathrm{sgn}(k_i)k_i-\mathrm{sgn}(k_i)k_i(b\,c)\right)\\&=\sum\limits_i\mathrm{sgn}(k_i)k_i\left(1-(b\,c)\right)\\&=\left(\sum\limits_i\mathrm{sgn}(k_i)k_i\right)\left(1-(b\,c)\right)\end{aligned}

as we stated.

Finally, if $t$ is some tableau with $b$ and $c$ in the same row, and if the swap $(b\,c)\in H$, then

$\displaystyle H^-\{t\}=0$

Our hypothesis tells us that $(b\,c)\{t\}=\{t\}$. We can thus use the above factorization to write

\displaystyle\begin{aligned}H^-\{t\}&=k(1-(b\,c))\{t\}\\&=k\{t\}-k(b\,c)\{t\}\\&=k\{t\}-k\{t\}\\&=0\end{aligned}

December 29, 2010

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