The Unapologetic Mathematician

Mathematics for the interested outsider

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


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


This tells us that


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


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


gives the sequence of compositions


while the semistandard generalized column tabloid


gives the sequence of compositions


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


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


is semistandard, but


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


Continuing our example, with

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

we we define


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


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


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

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


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


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 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 2 Comments

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


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:


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 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 1 Comment

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


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:


Taking dimensions, we find


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 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 1 Comment

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<i. 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 ns 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


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 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 5 Comments