The Unapologetic Mathematician

Mathematics for the interested outsider

More Kostka Numbers

First let’s mention a few more general results about Kostka numbers.

Among all the tableaux that partition n, it should be clear that (n)\triangleright\mu. Thus the Kostka number K_{(n)\mu} is not automatically zero. In fact, I say that it’s always 1. Indeed, the shape is a single row with n entries, and the content \mu gives us a list of numbers, possibly with some repeats. There’s exactly one way to arrange this list into weakly increasing order along the single row, giving K_{(n)\mu}=1.

On the other extreme, \lambda\triangleright(1^n), so K_{\lambda(1^n)} might be nonzero. The shape is given by \lambda, and the content (1^n) gives one entry of each value from 1 to n. There are no possible entries to repeat, and so any semistandard tableau with content (1^n) is actually standard. Thus K_{\lambda(1^n)}=f^\lambda — the number of standard tableaux of shape \lambda.

This means that we can decompose the module M^{(1^n)}:

\displaystyle M^{(1^n)}=\bigoplus\limits_{\lambda}f^\lambda S^\lambda

But f^\lambda=\dim(S^\lambda), which means each irreducible S_n-module shows up here with a multiplicity equal to its dimension. That is, M^{(1^n)} is always the left regular representation.

Okay, now let’s look at a full example for a single choice of \mu. Specifically, let \mu=(2,2,1). That is, we’re looking for semistandard tableaux of various shapes, all with two entries of value 1, two of value 2, and one of value 3. There are five shapes \lambda with \lambda\trianglerighteq\mu. For each one, we will look for all the ways of filling it with the required content.

\displaystyle\begin{array}{cccc}\lambda=(2,2,1)&\begin{array}{cc}\bullet&\bullet\\\bullet&\bullet\\\bullet&\end{array}&\begin{array}{cc}1&1\\2&2\\3&\end{array}&\\\hline\lambda=(3,1,1)&\begin{array}{ccc}\bullet&\bullet&\bullet\\\bullet&&\\\bullet&&\end{array}&\begin{array}{ccc}1&1&2\\2&&\\3&&\end{array}&\\\hline\lambda=(3,2)&\begin{array}{ccc}\bullet&\bullet&\bullet\\\bullet&\bullet&\end{array}&\begin{array}{ccc}1&1&2\\2&3&\end{array}&\begin{array}{ccc}1&1&3\\2&2&\end{array}\\\hline\lambda=(4,1)&\begin{array}{cccc}\bullet&\bullet&\bullet&\bullet\\\bullet&&&\end{array}&\begin{array}{cccc}1&1&2&2\\3&&&\end{array}&\begin{array}{cccc}1&1&2&3\\2&&&\end{array}\\\hline\lambda=(5)&\begin{array}{ccccc}\bullet&\bullet&\bullet&\bullet&\bullet\end{array}&\begin{array}{ccccc}1&1&2&2&3\end{array}&\end{array}

Counting the semistandard tableaux on each row, we find the Kostka numbers. Thus we get the decomposition

\displaystyle M^{(2,2,1)}=S^{(2,2,1)}\oplus S^{(3,1,1)}\oplus2S^{(3,2)}\oplus2S^{(4,1)}\oplus S^{(5)}

February 18, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 1 Comment

Kostka Numbers

Now we’ve finished our proof that the intertwinors \bar{\theta}_T coming from semistandard tableauxspan the space of all intertwinors from the Specht module S^\lambda to the Young tabloid module M^\mu. We also know that they’re linearly independent, and so they form a basis of the space of intertwinors — one for each semistandard generalized tableau.

Since the Specht modules are irreducible, we know that the dimension of this space is the multiplicity of S^\lambda in M^\mu. And the dimension, of course, is the number of basis elements, which is the number of semistandard generalized tableaux of shape \lambda and content \mu. This number we call the “Kostka number” K_{\lambda\mu}. We’ve seen that there is a decomposition

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

Now we know that the Kostka numbers give these multiplicities, so we can write

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

We saw before that when \lambda=\mu, the multiplicity is one. In terms of the Kostka numbers, this tells us that K_{\mu\mu}=1. Is this true? Well, the only way to fit \mu_1 entries with value 1, \mu_2 with value 2, and so on into a semistandard tableau of shape \mu is to put all the i entries on the ith row.

In fact, we can extend the direct sum by removing the restriction on \lambda:

\displaystyle M^\mu=\bigoplus\limits_\lambda K_{\lambda\mu}S^\lambda

This is because when \lambda\triangleleft\mu we have K_{\lambda\mu}=0. Indeed, we must eventually have \lambda_1+\dots+\lambda_i<\mu_1+\dots+\mu_i, and so we can't fit all the entries with values 1 through i on the first i rows of \lambda. We must at the very least have a repeated entry in some column, if not a descent. There are thus no semistandard generalized tableaux with shape \lambda and content \mu in this case.

February 17, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 2 Comments

Intertwinors from Semistandard Tableaux Span, part 3

Now we are ready to finish our proof that the intertwinors \bar{\theta}_T:S^\lambda\to M^\mu coming from semistandard generalized tableaux T span the space of all intertwinors between these modules.

As usual, pick any intertwinor \theta:S^\lambda\to M^\mu and write

\displaystyle\theta(e_t)=\sum\limits_Tc_TT

Now define the set L_\theta to consist of those semistandard generalized tableaux S so that [S]\trianglelefteq[T] for some T appearing in this sum with a nonzero coefficient. This is called the “lower order ideal” generated by the T in the sum. We will prove our assertion by induction on the size of this order ideal.

If L_\theta is empty, then \theta must be the zero map. Indeed, our lemmas showed that if \theta is not the zero map, then at least one semistandard T shows up in the above sum, and this T would itself belong to L_\theta. And of course the zero map is contained in any span.

Now, if L_\theta is not empty, then there is at least some semistandard T with c_T\neq0 in the sum. Our lemmas even show that we can pick one so that [T] is maximal among all the tableaux in the sum. Let’s do that and define a new intertwinor:

\displaystyle \theta' = \theta - c_T\bar{\theta}_T

I say that L_{\theta'} is L_\theta with T removed.

Every S appearing in \bar{\theta}_T(e_t) has [S]\trianglelefteq[T], since if T is semistandard then [T] is the largest column equivalence class in \theta_T(\{t\}). Thus L_{\theta'} must be a subset of L_\theta since we can’t be introducing any new nonzero coefficients.

Our lemmas show that if [S]=[T], then c_S must appear with the same coefficient in both \theta(e_t) and c_T\bar{\theta}_T(e_t). That is, they must be cancelled off by the subtraction. Since T is maximal there’s nothing above it that might keep it inside the ideal, and so T\notin L_{\theta'}.

So by induction we conclude that \theta' is contained within the span of the \bar{\theta}_T generated by semistandard tableaux, and thus \theta must be as well.

February 14, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 3 Comments

Intertwinors from Semistandard Tableaux Span, part 2

We continue our proof that the intertwinors \bar{\theta}_T:S^\lambda\to M^\mu that come from semistandard tableaux span the space of all such intertwinors. This time I assert that if \theta\in\hom(S^\lambda,M^\mu) is not the zero map, then there is some semistandard T with c_T\neq0.

Obviously there are some nonzero coefficients; if \theta(e_t)=0, then

\displaystyle\theta(e_{\pi t})=\theta(\pi e_t)=\pi\theta(e_t)=0

which would make \theta the zero map. So among the nonzero c_T, there are some with [T] maximal in the column dominance order. I say that we can find a semistandard T among them.

By the results yesterday we know that the entries in the columns of these T are all distinct, so in the column tabloids we can arrange them to be strictly increasing down the columns. What we must show is that we can find one with the rows weakly increasing.

Well, let’s pick a maximal T and suppose that it does have a row descent, which would keep it from being semistandard. Just like the last time we saw row descents, we get a chain of distinct elements running up the two columns:

\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 choose the sets A and B and the Garnir element g_{A,B} just like before. We find

\displaystyle g_{A,B}\left(\sum\limits_Tc_TT\right)=g_{A,B}\left(\theta(e_t)\right)=\theta\left(g_{A,B}(e_t)\right)=\theta(0)=0

The generalized tableau T must appear in g_{A,B}(T) with unit coefficient, so to cancel it off there must be some other generalized tableau T'\neq T with T'=\pi T for some \pi that shows up in g_{A,B}. But since this \pi just interchanges some a and b entries, we can see that [T']\triangleright[T], which contradicts the maximality of our choice of T.

Thus there can be no row descents in T, and T is in fact semistandard.

February 12, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 1 Comment

Intertwinors from Semistandard Tableaux Span, part 1

Now that we’ve shown the intertwinors that come from semistandard tableaux are independent, we want to show that they span the space \hom(S^\lambda,M^\mu). This is a bit fidgety, but should somewhat resemble the way we showed that standard polytabloids span Specht modules.

So, let \theta\in\hom(S^\lambda,M^\mu) be any intertwinor, and write out the image

\displaystyle\theta(e_t)=\sum\limits_Tc_TT

Here we’re implicitly using the fact that \mathbb{C}[T_{\lambda\mu}]\cong M^\mu.

First of all, I say that if \pi\in C_t and T_1=\pi T_2, then the coefficients of T_1 and T_2 differ by a factor of \mathrm{sgn}(\pi). Indeed, we calculate

\displaystyle\pi\left(\theta(e_t)\right)=\theta\left(\pi(\kappa_t\{t\})\right)=\theta(\mathrm{sgn}\kappa_t\{t\})=\mathrm{sgn}(\pi)\theta(e_t)

This tells us that

\displaystyle\pi\sum\limits_Tc_TT=\mathrm{sgn}(\pi)\sum\limits_Tc_TT

Comparing coefficients on the left and right gives us our assertion.

As an immediate corollary to this lemma, we conclude that if T has a repetition in some column, then c_T=0. Indeed, we can let \pi be the permutation that swaps the places of these two identical entries. Then T=\pi T, while the previous result tells us that c_T=\mathrm{sgn}c_T=-c_T, and so c_T=0.

February 11, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 2 Comments

Independence of Intertwinors from Semistandard Tableaux

Let’s start with the semistandard generalized tableaux T\in T_{\lambda\mu}^0 and use them to construct intertwinors \bar{\theta}_T:\hom(S^\lambda,M^\mu). I say that this collection is linearly independent.

Indeed, let’s index the semistandard generalized tableaux as T_1,\dots,T_m. We will take our reference tableau t and show that the vectors \bar{\theta}_{T_i}(e_t)\in M^\mu are independent. This will show that the \bar{\theta}_{T_i} are independent, since any linear dependence between the operators would immediately give a linear dependence between the \bar{\theta}_{T_i}(v) for all v\in S^\lambda.

Anyway, we have

\displaystyle\bar{\theta}_{T_i}(e_t)=\theta_{T_i}\left(\kappa_t\{t\}\right)=\kappa_t\theta_{T_i}(\{t\})

Since we assumed T_i to be semistandard, we know that [T_i]\triangleright[S] for all summands S\in\theta_{T_i}(\{t\}). Now the permutations in \kappa_t do not change column equivalence classes, so this still holds: [T_i]\triangleright[S] for all summands S\in\kappa_t\theta_{T_i}(\{t\}). And further all the [T_i] are distinct since no column equivalence class can contain more than one semistandard tableau.

But now we can go back to the lemma we used when showing that the standard polytabloids were independent! The \kappa_t\theta_{T_i}(\{t\})=\bar{\theta}(e_t) are a collection of vectors in M^\mu. For each one, we can pick a basis vector [T_i] which is maximum among all those having a nonzero coefficient in the vector, and these selected maximum basis elements are all distinct. We conclude that our collection of vectors in independent, and then it follows that the intertwinors \bar{\theta}_{T_i} are independent.

February 9, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 2 Comments

Dominance for Generalized Tabloids

Sorry I forgot to post this yesterday afternoon.

You could probably have predicted this: we’re going to have orders on generalized tabloids analogous to the dominance and column dominance orders for tabloids without repetitions. Each tabloid (or column tabloid) gives a sequence of compositions, and at the ith step we throw in all the entries with value i.

For example, the generalized column tabloid

\displaystyle[S]=\begin{array}{|c|c|c|}2&1&1\\3&2&\multicolumn{1}{c}{}\end{array}

gives the sequence of compositions

\displaystyle\begin{aligned}\lambda^1&=(0,1,1)\\\lambda^2&=(1,2,1)\\\lambda^3&=(2,2,1)\end{aligned}

while the semistandard generalized column tabloid

\displaystyle[T]=\begin{array}{|c|c|c|}1&1&1\\2&3&\multicolumn{1}{c}{}\end{array}

gives the sequence of compositions

\displaystyle\begin{aligned}\mu^1&=(1,1,1)\\\mu^2&=(2,1,1)\\\mu^3&=(2,2,1)\end{aligned}

and we find that [S]\trianglelefteq[T] since \lambda^i\trianglelefteq\mu^i for all i.

We of course have a dominance lemma: if k<l, k occurs in a column to the left of l in T, and S is obtained from T by swapping these two entries, then [T]\triangleright[S]. As an immediate corollary, we find that if T is semistandard and S\in\{T\} is different from T, then [T]\triangleright[S]. That is, [T] is the "largest" (in the dominance order) equivalence class in \theta_T{t}. The proofs of these facts are almost exactly as they were before.

February 9, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 2 Comments

Semistandard Generalized Tableaux

We want to take our intertwinors and restrict them to the Specht modules. If the generalized tableau T has shape \lambda and content \mu, we get an intertwinor \bar{\theta}_T\in\hom(S^\lambda,M^\mu). This will eventually be useful, since the dimension of this hom-space is the multiplicity of S^\lambda in M^\mu.

Anyway, if t is our standard “reference” tableau, then we can calculate

\displaystyle\begin{aligned}\bar{\theta}_T(e_t)&=\bar{\theta}_T(\kappa_t\{t\})\\&=\kappa_t\theta_T(\{t\})\\&=\kappa_t\left(\sum\limits_{S\in\{T\}}S\right)\\&=\sum\limits_{S\in\{T\}}\kappa_t(S)\end{aligned}

We can see that it will be useful to know when \kappa_t(S)=0. It turns out this happens if and only if S has two equal elements in some column.

Indeed, if \kappa_t(S)=0, then

\displaystyle S+\sum\limits_{\substack{\pi\in C_t\\\pi\neq e}}\mathrm{sgn}(\pi)\pi S=0

Thus for some \sigma\in C_t with \mathrm{sgn}(\sigma)=-1 we must have S=\sigma S. But then we must have all the elements in each cycle of \sigma the same, and these cycles are restricted to the columns. Since \sigma is not the identity, we have at least one nontrivial cycle and at least two elements the same.

On the other hand, assume S(i)=S(j) in the same column of S. Then [e-(i\,j)](S)=0. But then the sign lemma tells us that (e-(i\,j)) is a factor of \kappa_t, and thus \kappa_t(S)=0.

This means that we can eliminate some intertwinors \bar{\theta}_T from consideration by only working with things like standard tableaux. We say that a generalized tableau is semistandard if its columns strictly increase (as for standard tableaux) and its rows weakly increase. That is, we allow repetitions along the rows, but only so long as we never have any row descents. The tableau

\displaystyle\begin{array}{ccc}1&1&2\\2&3&\end{array}

is semistandard, but

\displaystyle\begin{array}{ccc}2&1&1\\3&2&\end{array}

is not.

February 8, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 1 Comment

Intertwinors from Generalized Tableaux

Given any generalized Young tableau T with shape \lambda and content \mu, we can construct an intertwinor \theta_T:M^\lambda\to M^\mu. Actually, we’ll actually go from M^\lambda to \mathbb{C}[T_{\lambda\mu}, but since we’ve seen that this is isomorphic to M^\mu, it’s good enough. Anyway, first, we have to define the row-equivalence class \{T\} and column-equivalence class [T]. These are the same as for regular tableaux.

So, let t be our reference tableau and let \{t\} be the associated tabloid. We define

\displaystyle\theta_T\left(\{t\}\right)=\sum\limits_{S\in\{T\}}S

Continuing our example, with

\displaystyle T=\begin{array}{ccc}2&1&1\\3&2&\end{array}

we we define

\displaystyle\begin{aligned}\theta_T\left(\begin{array}{ccc}\cline{1-3}1&2&3\\\cline{1-3}4&5&\\\cline{1-2}\end{array}\right)&=\begin{array}{ccc}2&1&1\\3&2&\end{array}+\begin{array}{ccc}1&2&1\\3&2&\end{array}+\begin{array}{ccc}1&1&2\\3&2&\end{array}\\&+\begin{array}{ccc}2&1&1\\2&3&\end{array}+\begin{array}{ccc}1&2&1\\2&3&\end{array}+\begin{array}{ccc}1&1&2\\2&3&\end{array}\end{aligned}

Now, we extend in the only way possible. The module M^\lambda is cyclic, meaning that it can be generated by a single element and the action of \mathbb{C}[S_n]. In fact, any single tabloid will do as a generator, and in particular \{t\} generates M^\lambda.

So, any other module element in M^\lambda is of the form \pi\{t\} for some \pi\in\mathbb{C}[S_n]. And so if \theta_T is to be an intertwinor we must define

\displaystyle\theta_T\left(\pi\{t\}\right)=\pi\theta_T(\{t\})=\sum\limits_{S\in\{T\}}\pi S

Remember here that \pi acts on generalized tableaux by shuffling the entries by place, not by value. Thus in our example we find

\displaystyle\begin{aligned}\theta_T\left(\begin{array}{ccc}\cline{1-3}2&4&3\\\cline{1-3}1&5&\\\cline{1-2}\end{array}\right)&=\theta_T\left((1\,2\,4)\begin{array}{ccc}\cline{1-3}1&2&3\\\cline{1-3}4&5&\\\cline{1-2}\end{array}\right)\\&=(1\,2\,4)\theta_T\left(\begin{array}{ccc}\cline{1-3}1&2&3\\\cline{1-3}4&5&\\\cline{1-2}\end{array}\right)\\&=(1\,2\,4)\begin{array}{ccc}2&1&1\\3&2&\end{array}+(1\,2\,4)\begin{array}{ccc}1&2&1\\3&2&\end{array}+(1\,2\,4)\begin{array}{ccc}1&1&2\\3&2&\end{array}\\&+(1\,2\,4)\begin{array}{ccc}2&1&1\\2&3&\end{array}+(1\,2\,4)\begin{array}{ccc}1&2&1\\2&3&\end{array}+(1\,2\,4)\begin{array}{ccc}1&1&2\\2&3&\end{array}\\&=\begin{array}{ccc}3&2&1\\1&2&\end{array}+\begin{array}{ccc}3&1&1\\2&2&\end{array}+\begin{array}{ccc}3&1&2\\1&2&\end{array}\\&+\begin{array}{ccc}2&2&1\\1&3&\end{array}+\begin{array}{ccc}2&1&1\\2&3&\end{array}+\begin{array}{ccc}2&1&2\\1&3&\end{array}\end{aligned}

Now it shouldn’t be a surprise that since so much of our construction to this point has depended on an aribtrary choice of a reference tableau t, the linear combination of generalized tableaux on the right doesn’t quite seem like it comes from the tabloid on the left. But this is okay. Just relax and go with it.

February 5, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 5 Comments

Modules of Generalized Young Tableaux

We can obviously create vector spaces out of generalized Young tableaux. Given the collection T_{\lambda\mu} of tableaux of shape \lambda and content \mu, we get the vector space \mathbb{C}[T_{\lambda\mu}]. We want to turn this into an S_n-module.

First, given any tabloid \{s\} of shape \mu, we can product a (generalized) tableau T\in T_{\lambda\mu} by defining T(i) to be the number of the row in s that contains the entry i. As an example, consider the tabloid

\displaystyle\{s\}=\begin{array}{cc}\cline{1-2}2&3\\\cline{1-2}1&5\\\cline{1-2}4&\\\cline{1-1}\end{array}

This gives us the function T(2)=T(3)=1, T(1)=T(5)=2, and T(4)=3. If \lambda=(3,2) and we use the usual reference tableau t, this gives us the generalized tabloid

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

The shape of T is obviously \lambda, and it’s easy to see that the content is exactly \mu. Indeed, there are \mu_i entries in T with the value i, just as there are \mu_i entries in the first row of \{s\}.

It should also be clear that this correspondence is a bijection. That is, given any generalized tableau T of shape \lambda and content \mu we can get a tabloid of shape \mu by turning T into a function and then putting k on row i of \{s\} if T(k)=i.

That means that the basis of generalized tableaux T_{\lambda\mu} of the vector space \mathbb{C}[T_{\lambda\mu}] is in bijection with the basis of \mu-tabloids of the vector space M^\mu. And this space carries an action of S_n — the linear extension of the action on tabloids. We want to pull this action across the bijection we just set up to get an action on T_{\lambda\mu}.

On the one hand, this is as easy as saying it: if T corresponds to \{s\}, we define \pi T to be the generalized tableau corresponding to \pi\{s\} and we’re done. To be a bit more explicit, we define \pi T by considering it as a function and setting

\displaystyle\left[\pi T\right](i)=T(\pi^{-1}i)

So, for example, if

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

then we can calculate

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

Even more explicitly, if

\displaystyle T=\begin{array}{ccc}2&1&1\\3&2&\end{array}

then we calculate

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

We should be clear about a major distinction here: the permutation \pi\in S_n acts on the entries in \{s\} — replacing i by \pi i — but it acts on the places in T — moving T(i) to the position of T(\pi i).

If we write the correspondence as \theta(\{s\})=T, then for \theta to be an intertwinor we need \theta(\pi\{s\})=\pi T. This forces

\displaystyle\begin{aligned}\left[\pi T\right](i)&=\text{row number of }i\text{ in }\pi\{s\}\\&=\text{row number of }\pi^{-1}i\text{ in }\{s\}\\&=T(\pi^{-1}i)\end{aligned}

and so this explicit action is forced on us.

The really interesting thing is that when we use this action on the generalized tableaux in T_{\lambda\mu}, we always get a module \mathbb{C}[T_{\lambda\mu}]\cong M^\mu, no matter what shape \lambda we start with.

February 3, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 2 Comments

« Previous Entries