# The Unapologetic Mathematician

## Generalized Young Tableaux

And now we have another generalization of Young tableaux. These are the same, except now we allow repetitions of the entries.

Explicitly, a generalized Young tableau $T$ — we write them with capital letters — of shape $\lambda$ is an array obtained by replacing the points of the Ferrers diagram of $\lambda$ with positive integers. Any skipped or repeated numbers are fine. We say that the “content” of $T$ is the composition $\mu=(\mu_1,\dots,\mu_m)$ where $\mu_i$ is the number of $i$ entries in $T$.

As an example, we have the generalized Young tableau

$\displaystyle\begin{array}{ccc}4&1&4\\1&3&\end{array}$

of shape $(3,2)$ and content $(2,0,1,2)$.

Notice that if $\lambda\vdash n$, then $\mu\vdash n$ as well, since both count up the total number of places in the tableau. Given a partition $\lambda$ and a composition $\mu$, both decomposing the same number $n$, we define $T_{\lambda\mu}$ to be the collection of generalized Young tableaux of shape $\lambda$ and content $\mu$. All the tableaux we’ve considered up until now have content $(1,\dots,1)=(1^n)$.

Now, pick some fixed (ungeneralized) tableau $t$. We can use the same one we usually do, numbering the rows from $1$ to $n$ across each row and from top to bottom, but it doesn’t really matter which we use. For our examples we’ll pick

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

Using this “reference” tableau, we can rewrite any generalized tableau as a function; define $T(i)$ to be the entry of $T$ in the same place as $i$ is in $t$. That is, any generalized tableau looks like

$\displaystyle\begin{array}{ccc}T(1)&T(2)&T(3)\\T(4)&T(5)&\end{array}$

and in our particular example above we have $T(1)=T(3)=4$, $T(2)=T(4)=1$, and $T(5)=3$. Conversely, any such function assigning a positive integer to each number from $1$ to $n$ can be interpreted as a generalized Young tableau. Of course the particular correspondence depends on exactly which reference tableau we use, but there will always be some such correspondence between functions and generalized tableaux.

February 2, 2011

## The Branching Rule, Part 4

What? More!?

Well, we got the idea to look for the branching rule by trying to categorify a certain combinatorial relation. So let’s take the flip side of the branching rule and decategorify it to see what it says!

Strictly speaking, decategorification means passing from a category to its set of isomorphism classes. That is, in the case of our categories of $S_n$-modules we should go from the Specht module $S^\lambda$ to its character $\chi^\lambda$. And that is an interesting question, but since the original relation turned into the dimensions of the modules in the branching rule, let’s do the same thing in reverse.

So the flip side of the branching rule tells us how a Specht module decomposes after being induced up to the next larger symmetric group. That is:

$\displaystyle S^\lambda\!\!\uparrow_{S_n}^{S_{n+1}}\cong\bigoplus\limits_{\lambda^+}S^{\lambda^+}$

To “decategorify”, we take dimensions

\displaystyle\begin{aligned}\dim\left(S^\lambda\!\!\uparrow_{S_n}^{S_{n+1}}\right)&=\dim\left(\bigoplus\limits_{\lambda^+}S^{\lambda^+}\right)\\&=\sum\limits_{\lambda^+}\dim\left(S^{\lambda^+}\right)\\&=\sum\limits_{\lambda^+}f^{\lambda^+}\end{aligned}

As we see, the right hand side is obvious, but he left takes a little more work. We consult the definition of induction to find

$\displaystyle S^\lambda\!\!\uparrow_{S_n}^{S_{n+1}}=\mathbb{C}\left[S_{n+1}\right]\otimes_{S_n}S^\lambda$

Calculating its dimension is a little easier if we recall what induction looks like for matrix representations: the direct sum of a bunch of copies of $S^\lambda$, one for each element in a transversal of the subgroup. That is, there are

$\displaystyle\lvert S_{n+1}/S_n\rvert=\lvert S_{n+1}\rvert/\lvert S_n\rvert=\frac{(n+1)!}{n!}=n+1$

copies of $S^\lambda$ in the induced representation. We find our new relation:

$\displaystyle(n+1)f^\lambda=\sum\limits_{\lambda^+}f^{\lambda^+}$

That is, the sum of the numbers of standard tableaux of all the shapes we get by adding an outer corner to $\lambda$ is $n+1$ times the number of standard tableaux of shape $\lambda$.

This is actually a sort of surprising result, and there should be some sort of combinatorial proof of it. I’ll admit, though, that I don’t know of one offhand. If anyone can point me to a good one, I’d be glad to post it.

February 1, 2011

## The Branching Rule, Part 3

“Part 3”? Didn’t we just finish proving the branching rule? Well, yes, but there’s another part we haven’t mentioned yet. Not only does the branching rule tell us how representations of $S_n$ decompose when they’re restricted to $S_{n-1}$, it also tells us how representations of $S_{n-1}$ decompose when they’re induced to $S_n$.

Now that we have the first statement of the branching rule down, proving the other one is fairly straightforward: it’s a consequence of Frobenius reciprocity. Indeed, the branching rule tells us that

$\displaystyle\dim\left(\hom_{S_{n-1}}(S^\mu,S^\lambda\!\!\downarrow)\right)=\bigg\{\begin{array}{cl}1&\mu=\lambda^-\\{0}&\mathrm{otherwise}\end{array}$

That is, there is one copy of $S^\mu$ inside $S^\lambda$ (considered as an $S_{n-1}$-module) if $\mu$ comes from $\lambda$ by removing an inner corner, and there are no copies otherwise.

So let’s try to calculate the multiplicity of $S^\lambda$ in the induced module $S^\mu\!\!\uparrow$:

\displaystyle\begin{aligned}\hom_{S_n}(S^\lambda,S^\mu\!\!\uparrow)^*&\cong\hom_{S_n}(S^\mu\!\!\uparrow,S^\lambda)\\&\cong\hom_{S_{n-1}}(S^\mu,S^\lambda\!\!\downarrow)\end{aligned}

Taking dimensions, we find

\displaystyle\begin{aligned}\dim\left(\hom_{S_n}(S^\lambda,S^\mu\!\!\uparrow)\right)&=\dim\left(\hom_{S_{n-1}}(S^\mu,S^\lambda\!\!\downarrow)\right)\\&=\bigg\{\begin{array}{cl}1&\mu=\lambda^-\\{0}&\mathrm{otherwise}\end{array}\\&=\bigg\{\begin{array}{cl}1&\lambda=\mu^+\\{0}&\mathrm{otherwise}\end{array}\end{aligned}

since if $\mu$ comes from $\lambda$ by removing an inner corner, then $\lambda$ comes from $\mu$ by adding an outer corner.

We conclude that

$\displaystyle S^\mu\!\!\uparrow_{S_{n-1}}^{S_n}\cong\bigoplus\limits_{\mu^+}S^{\mu^+}$

which is the other half of the branching rule.

January 31, 2011

## The Branching Rule, Part 2

We pick up our proof of the branching rule. We have a partition $\lambda$ with inner corners in rows $r_1,\dots,r_k$. The partitions we get by removing each of the inner corner $r_i$ is $\lambda^i$. If the tableau $t$ (or the tabloid $\{t\}$ has its $n$ in row $i$, then $t^i$ (or $\{t^i\}$) is the result of removing that $n$.

We’re looking for a chain of subspaces

$\displaystyle0=V^{(0)}\subseteq V^{(1)}\subseteq\dots\subseteq V^{(k)}=S^\lambda$

such that $V^{(i)}/V^{(i-1)}=S^{\lambda^i}$ as $S_{n-1}$-modules. I say that we can define $V^{(i)}$ to be the subspace of $S^\lambda$ spanned by the standard polytabloids $e_t$ where the $n$ shows up in row $r_i$ or above in $t$.

For each $i$, define the map $\theta_i:M^\lambda\to M^{\lambda^i}$ by removing an $n$ in row $r_i$. That is, if $\{t\}\in$latex M^\lambda\$ has its $n$ in row $r_i$, set $\theta_i(\{t\})=\{t^i\}$; otherwise set $\theta_i(\{t\})=0$. These are all homomorphisms of $S_{n-1}$-modules, since the action of $S_{n-1}$ always leaves the $n$ in the same row, and so it commutes with removing an $n$ from row $r_i$.

Similarly, I say that $\theta_i(e_t)=e_{t^i}$ if $n$ is in row $r_i$ of $t$, and we get $\theta_i(e_t)=0$ if it’s in row $r_j$ with $j. Indeed if $n$ shows up above row $r_i$, then since it’s the bottommost entry in its column that column can have no entries at all in row $r_i$. Thus as we use $C_t$ to shuffle the columns, all of the tabloids that show up in $e_t=C_t^-\{t\}$ will be sent to zero by $\theta_i$. Similar considerations show that if $n$ is in row $r_i$, then of all the tabloids that show up in $e_t$, only those leaving $n$ in that row are not sent to zero by $\theta_i$. The permutations in $C_t$ leaving $n$ fixed are, of course, exactly those in $C_{t^i}^-$, and our assertion holds.

Now, since each standard polytabloid $e_{t^i}\in S^{\lambda^i}$ comes from some polytabloid $e_t\in M^{\lambda}$, we see they’re all in the image of $\theta_i$. Further, these $e_t$ all have their $n$s in row $r_i$, so they’re all in $V^{(i)}$. That is, $\theta_i(V^{(i)})=S^{\lambda^i}$. On the other hand, if $t$ has its $n$ above row $r_i$, then $\theta(e_t)=0$, and so $V^{(i-1)}\subseteq\mathrm{Ker}(\theta_i)$.

So now we’ve got a longer chain of subspaces:

$\displaystyle0=V^{(0)}\subseteq V^{(1)}\cap\mathrm{Ker}(\theta_1)\subseteq V^{(1)}\subseteq\dots\subseteq V^{(k)}\cap\mathrm{Ker}(\theta_k)\subseteq V^{(k)}=S^\lambda$

But we also know that

$\displaystyle\dim\left(\frac{V^{(i)}}{V^{(i)}\cap\mathrm{Ker}(\theta_i)}\right)=\dim(\theta_i(V^{(i)}))=\dim(S^{\lambda^i})=f^{\lambda^i}$

So the steps from $V^{(i)}\cap\mathrm{Ker}(\theta_i)$ to $V^{(i)}$ give us all the $f^{\lambda^i}$ as we add up dimensions. Comparing to the formula we’re categorifying, we see that this accounts for all of $f^\lambda=\dim(S^\lambda)$. And so there are no dimensions left for the steps from $V^{(i-1)}$ to $V^{(i)}\cap\mathrm{Ker}(\theta_i)$, and these containments must actually be equalities!

$\displaystyle V^{(i-1)}=V^{(i)}\cap\mathrm{Ker}(\theta_i)$

And thus

$\displaystyle \frac{V^{(i)}}{V^{(i-1)}}=\frac{V^{(i)}}{V^{(i)}\cap\mathrm{Ker}(\theta_i)}\cong S^{\lambda^i}$

as asserted. The branching rule then follows.

January 28, 2011

## The Branching Rule, Part 1

We want to “categorify” the relation we came up with last time:

$\displaystyle f^\lambda=\sum\limits_{\lambda^-}f^{\lambda^-}$

That is, we want to replace these numbers with objects of a category, replace the sum with a direct sum, and replace the equation with a natural isomorphism.

It should be clear that an obvious choice for the objects is to replace $f^\lambda$ with the Specht module $S^\lambda$, since we’ve seen that $f^\lambda=\dim(S^\lambda)$. But what category are they in? On the left side, $S^\lambda$ is an $S_n$-module, but on the right side all the $S^{\lambda^-}$ are $S_{n-1}$-modules. Our solution is to restrict $S^\lambda$, suggesting the isomorphism

$\displaystyle S^\lambda\downarrow^{S_n}_{S_{n-1}}\cong\bigoplus\limits_{\lambda^-}S^{\lambda^-}$

This tells us what happens to any of the Specht modules as we restrict it to a smaller symmetric group. As a side note, it doesn’t really matter which $S_{n-1}\subseteq S_n$ we use, since they’re all conjugate to each other inside $S_n$. So we’ll just use the one that permutes all the numbers but $n$.

Anyway, say the inner corners of $\lambda$ occur in the rows $r_1<\dots, and of course they must occur at the ends of these rows. For each one, we’ll write $\lambda^i$ for the partition that comes from removing that inner corner. Similarly, if $t$ is a standard tableau with $n$ in the $i$th row, we write $t^i$ for the (standard) tableau with $n$ removed. And the same goes for the standard tabloids $\{t\}$ and $\{t^i\}$.

Our method will be to find a tower of subspaces

$\displaystyle0=V^{(0)}\subseteq V^{(1)}\subseteq\dots\subseteq V^{(k)}=S^\lambda$

so that at each step we have $V^{(i)}/V^{(i-1)}\cong S^{\lambda^i}$ as $S_{n-1}$-modules. Then we can see that

$\displaystyle S^\lambda\downarrow^{S_n}_{S_{n-1}}=V^{(k)}\cong V^{(k-1)}\oplus(V^{(k)}/V^{(k-1)}\cong V^{(k-1)}\oplus S^{\lambda^k}$

And similarly we find $V^{(k-1)}\cong V^{(k-2)}\oplus S^{\lambda^{k-1}}$, and step by step we go until we find the proposed isomorphism. The construction itself will be presented next time.

January 27, 2011

## Inner and Outer Corners

The next thing we need to take note of it the idea of an “inner corner” and an “outer corner” of a Ferrers diagram, and thus of a partition.

An inner corner of a Ferrers diagram is a cell that, if it’s removed, the rest of the diagram is still the Ferrers diagram of a partition. It must be the rightmost cell in its row, and the bottommost cell in its column. Similarly, an outer corner is one that, if it’s added to the diagram, the result is still the Ferrers diagram of a partition. This is a little more subtle: it must be just to the right of the end of a row, and just below the bottom of a column.

As an example, consider the partition $(5,4,4,2)$, with Ferrers diagram

$\displaystyle\begin{array}{ccccc}\bullet&\bullet&\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet&\bullet&\\\bullet&\bullet&\bullet&\bullet&\\\bullet&\bullet&&&\end{array}$

We highlight the inner corners by shrinking them, and mark the outer corners with circles:

$\displaystyle\begin{array}{cccccc}\bullet&\bullet&\bullet&\bullet&\cdot&\circ\\\bullet&\bullet&\bullet&\bullet&\circ&\\\bullet&\bullet&\bullet&\cdot&&\\\bullet&\cdot&\circ&&&\\\circ&&&&&\end{array}$

That is, there are three ways we could remove a cell and still have the Ferrers diagram of a partition:

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

And there are four ways that we could add a cell and still have the Ferrers diagram of a partition:

$\displaystyle\begin{array}{cccccc}\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet&\bullet&&\\\bullet&\bullet&\bullet&\bullet&&\\\bullet&\bullet&&&&\end{array}\qquad\begin{array}{ccccc}\bullet&\bullet&\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet&\bullet&\\\bullet&\bullet&&&\end{array}\qquad\begin{array}{ccccc}\bullet&\bullet&\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet&\bullet&\\\bullet&\bullet&\bullet&\bullet&\\\bullet&\bullet&\bullet&&\end{array}\qquad\begin{array}{ccccc}\bullet&\bullet&\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet&\bullet&\\\bullet&\bullet&\bullet&\bullet&\\\bullet&\bullet&&&\\\bullet&&&&\end{array}$

If the first partition is $\lambda$, we write a generic partition that comes from removing a single inner corner by $\lambda^-$. Similarly, we write a generic partition that comes from adding a single outer corner by $\lambda^+$. In our case, if $\lambda=(5,4,4,2)$, then the three possible $\lambda^-$ partitions are $(4,4,4,2)$, $(5,4,3,2)$, and $(5,4,4,1)$, while the four possible $\lambda^+$ partitions are $(6,4,4,2)$, $(5,5,4,2)$, $(5,4,4,3)$, and $(5,4,4,2,1)$.

Now, as a quick use of this concept, think about how to fill a Ferrers diagram to make a standard Young tableau. It should be clear that since $n$ is the largest entry in the tableau, it must be in the rightmost cell of its row and the bottommost cell of its column in order for the tableau to be standard. Thus $n$ must occur in an inner corner. This means that we can describe any standard tableau by picking which inner corner contains $n$, removing that corner, and filling the rest with a standard tableau with $n-1$ entries. Thus, the number of standard $\lambda$-tableaux is the sum of all the standard $\lambda^-$-tableaux:

$\displaystyle f^\lambda=\sum\limits_{\lambda^-}f^{\lambda^-}$

January 26, 2011

## Young’s Natural Representation

Now that we have a canonical basis for our Specht modules composed of standard polytabloids it gives us a matrix representation of $S_n$ for each $\lambda\vdash n$. We really only need to come up with matrices for the swaps $(k\,k+1)$, for $1\leq k\leq n-1$, since these generate the whole symmetric group.

When we calculate the action of the swap on a polytabloid $e_t$ associated with a standard Young tableau $t$, there are three possibilities. Either $k$ and $k+1$ are in the same column of $t$, they’re in the same row of $t$, or they’re not in the same row or column of $t$.

The first case is easy. If $k$ and $k+1$ are in the same column of $t$, then $(k\,k+1)\in C_t$, and thus $(k\,k+1)e_t=-e_t$.

The third case isn’t much harder, although it’s subtler. I say that if $k$ and $k+1$ share neither a row nor a column, then $(k\,k+1)t$ is again standard. Indeed, swapping the two can’t introduce either a row or a column descent. The entries to the left of and above $k+1$ are all less than $k+1$, and none of them are $k$, so they’re all less than $k$ as well. Similarly, all the entries to the right of and below $k$ are greater than $k$, and none of them are $k+1$, so they’re all greater than $k+1$ as well.

Where things get complicated is when $k$ and $k+1$ share a row. But then they have to be next to each other, and the swap introduces a row descent between them. We can then use our Garnir elements to write this polytabloid in terms of standard ones.

Let’s work this out explicitly for the Specht module $S^{(2,1)}$, which should give us our well-known two-dimensional representation of $S_3$. The basis consists of the polytabloids associated to these two tableaux:

$\displaystyle\begin{array}{cc}1&2\\3&\end{array}\qquad\begin{array}{cc}1&3\\2&\end{array}$

We need to come up with matrices for the two swaps $(1\,2)$ and $(2\,3)$. And the second one is easy: it just swaps these two tableaux! Thus we get the matrix

$\displaystyle X^{(2,1)}\left((2\,3)\right)=\begin{pmatrix}0&1\\1&0\end{pmatrix}$

The action of $(1\,2)$ on the second standard tableau is similarly easy. Since $1$ and $2$ are in the same column, the swap acts by multiplying by $-1$. Thus we can write down a column of the matrix

$\displaystyle X^{(2,1)}\left((1\,2)\right)=\begin{pmatrix}?&0\\?&-1\end{pmatrix}$

As for the action on the first tableau, the swap induces a row descent. We use a Garnir element to straighten it out. With the same abuse of notation as last time, we write

$\displaystyle\begin{array}{cc}2&1\\3&\end{array}=\begin{array}{cc}1&2\\3&\end{array}-\begin{array}{cc}1&3\\2&\end{array}$

and so we can fill in the other column:

$\displaystyle X^{(2,1)}\left((1\,2)\right)=\begin{pmatrix}1&0\\-1&-1\end{pmatrix}$

From here we can write all the other matrices in the representation as products of these two.

January 26, 2011

## “Straightening” a Polytabloid

Let’s look at one example of “straightening” out a polytabloid to show it’s in the span of the standard polytabloids, using the Garnir elements.

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

Now, it’s slightly abusive to the notation, but we’ll just write a tableau $t$ and know that we actually mean the polytabloid $e_t$ in our linear combinations. Using this, we’ve seen that we can write

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

Now, by the way we’ve selected our Garnir elements, we know that none of these can have any column descents. And we also know that they can’t have a row descent in the same place $e_t$ did. Indeed, the only three that have a row descent all have it between the second and third entries of the first row. So now let’s look at

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

We can write down another table, just like before:

$\displaystyle\begin{array}{cccc}A'&B'&\pi&\pi u\\\hline\\\{4,5\}&\{3\}&e&\begin{array}{ccc}1&4&3\\2&5&\\6&&\end{array}\\\{3,5\}&\{4\}&(3\,4)&\begin{array}{ccc}1&3&4\\2&5&\\6&&\end{array}\\\{3,4\}&\{5\}&(3\,5\,4)&\begin{array}{ccc}1&3&5\\2&4&\\6&&\end{array}\end{array}$

which lets us write

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

Similarly we can write

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

and

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

Putting these all together, we conclude that

\displaystyle\begin{aligned}\begin{array}{ccc}1&2&3\\5&4&\\6&&\end{array}=&\begin{array}{ccc}1&2&3\\4&5&\\6&&\end{array}-\begin{array}{ccc}1&3&4\\2&5&\\6&&\end{array}+\begin{array}{ccc}1&3&5\\2&4&\\6&&\end{array}-\begin{array}{ccc}1&2&3\\4&6&\\5&&\end{array}\\+&\begin{array}{ccc}1&3&4\\2&6&\\5&&\end{array}-\begin{array}{ccc}1&3&6\\2&4&\\5&&\end{array}-\begin{array}{ccc}1&3&5\\2&6&\\4&&\end{array}+\begin{array}{ccc}1&3&6\\2&5&\\4&&\end{array}\end{aligned}

All of these tabloids are standard, and so we see that our original — nonstandard — $e_t$ is in the span of the standard polytabloids.

January 25, 2011

## Standard Polytabloids Span Specht Modules

We defined the Specht module $S^\lambda$ as the subspace of the Young tabloid module $M^\lambda$ spanned by polytabloids of shape $\lambda$. But these polytabloids are not independent. We’ve seen that standard polytabloids are independent, and it turns out that they also span. That is, they provide an explicit basis for the Specht module $S^\lambda$.

Anyway, first off we can take care of all the $e_t$ where the columns of $t$ don’t increase down the column. Indeed, if $\sigma\in C_t$ stabilizes the columns of $t$, then

$\displaystyle e_{\sigma t}=\sigma e_t=\mathrm{sgn}(\sigma)e_t$

where we’ve used the sign lemma. So any two polytabloids coming from tableaux in the same column equivalence class are scalar multiples of each other. We’ve just cut our spanning set down from one element for each tableau to one for each column equivalence class of tableaux.

To deal with column equivalence classes, start with the tableau $t_0$ that we get by filling in the shape with the numbers $1$ to $n$ in order down the first column, then the second, and so on. This is the maximum element in the column dominance order, and it’s standard. Given any other tableau $t$, we assume that every tableau $s$ with $[s]\triangleright[t]$ is already in the span of the standard polytabloids. This is an inductive hypothesis, and the base case is taken care of by the maximum tabloid $t_0$.

If $t$ is itself standard, we’re done, since it’s obviously in the span of the standard polytabloids. If not, there must be a row descent — we’ve ruled out column descents already — and so we can pick our Garnir element to write $e_t$ as the sum of a bunch of other polytabloids $e_{\pi t}$, where $[\pi t]\triangleright[t]$ in the column dominance order. But by our inductive hypothesis, all these $e_{\pi t}$ are in the span of the standard polytabloids, and thus $e_t$ is as well.

As an immediate consequence, we conclude that $\dim(S^\lambda)=f^\lambda$, where $f^\lambda$ is the number of standard tableaux of shape $\lambda$. Further, since we know from our decomposition of the left regular representation that each irreducible representation of $S_n$ shows up in $\mathbb{C}[S_n]$ with a multiplicity equal to its dimension, we can write

$\displaystyle\mathbb{C}[S_n]=\bigoplus\limits_{\lambda\vdash n}f^\lambda S^\lambda$

Taking dimensions on both sides we find

$\displaystyle \sum\limits_{\lambda\vdash n}\left(f^\lambda\right)^2=\sum\limits_{\lambda\vdash n}f^\lambda\dim(S^\lambda)=\lvert S_n\rvert=n!$

January 21, 2011

## Properties of Garnir Elements from Tableaux 2

When we pick a tableau $t$ with a certain row descent and use it to pick sets $A$ and $B$, as we’ve done, the resulting Garnir element is a sum of a bunch of tabloids coming from a bunch of tableaux. I say that the column tabloid $[t]$ corresponding to the original tableau is dominated by all the other tabloids, using the column dominance order.

Indeed, when considering column tabloids we can rearrange the entries within columns freely, so we may assume that they’re always increasing down the columns. If we have our row descent in row $i$, we can label the entries in the left column by $a$s and those in the right column by $b$s. Our tabloid then looks — in these two columns, at least — something like

$\displaystyle\begin{array}{ccc}a_1&\hphantom{X}&b_1\\&&\wedge\\a_2&&b_2\\&&\wedge\\\vdots&&\vdots\\&&\wedge\\a_i&>&b_i\\\wedge&&\\\vdots&&\vdots\\\wedge&&b_q\\a_p&&\end{array}$

We see our sets $A=\{a_i,\dots,a_p\}$ and $B=\{b_1,\dots,b_i\}$. The permutations in the transversal that we use to construct our Garnir element work by moving swapping some of the $b$s with some of the $a$s. But since all that $b$s are smaller than all the $a$s, while they occur in a row further to the right, the dominance lemma for column tabloids tells us that any such swap can only move the tabloid up in the dominance order.

It is in this sense that the Garnir element lets us replace a tabloid with a linear combination of other tabloids that are “more standard”. And it puts us within striking distance of our goal.

January 20, 2011