The Unapologetic Mathematician

Mathematics for the interested outsider

Standard Polytabloids are Independent

Now we’re all set to show that the polytabloids that come from standard tableaux are linearly independent. This is half of showing that they form a basis of our Specht modules. We’ll actually use a lemma that applies to any vector space V with an ordered basis e_\alpha. Here \alpha indexes some set B of basis vectors which has some partial order \preceq.

So, let v_1,\dots,v_m be vectors in V, and suppose that for each v_i we can pick some basis vector e_{\alpha_i} which shows up with a nonzero coefficient in v_i subject to the following two conditions. First, for each i the basis element e_{\alpha_i} should be the maximum of all the basis vectors having nonzero coefficients in v_i. Second, the e_{\alpha_i} are all distinct.

We should note that the first of these conditions actually places some restrictions on what vectors the v_i can be in the first place. For each one, the collection of basis vectors with nonzero coefficients must have a maximum. That is, there must be some basis vector in the collection which is actually bigger (according to the partial order \preceq) than all the others in the collection. It’s not sufficient for e_{\alpha_i} to be maximal, which only means that there is no larger index in the collection. The difference is similar to that between local maxima and a global maximum for a real-valued function.

This distinction should be kept in mind, since now we’re going to shuffle the order of the v_i so that e_{\alpha_1} is maximal among the basis elements e_{\alpha_i}. That is, none of the other e_{\alpha_i} should be bigger than e_{\alpha_1}, although some may be incomparable with it. Now I say that e_{\alpha_i} cannot have a nonzero coefficient in any other of the v_i. Indeed, if it had a nonzero coefficient in, say, v_2, then by assumption we would have e_{\alpha_1}\prec e_{\alpha_2}, which contradicts the maximality of e_{\alpha_1}. Thus in any linear combination

\displaystyle c_1v_1+\dots+c_mv_m=0

we must have c_1=0, since there is no other way to cancel off all the occurrences of e_{\alpha_1}. Removing v_1 from the collection, we can repeat the reasoning with the remaining vectors until we get down to a single one, which is trivially independent.

So in the case we care about the space is the Young tabloid module M^\lambda, with the basis of Young tabloids having the dominance ordering. In particular, we consider for our v_i the collection of polytabloids e_t where t is a standard tableau. In this case, we know that \{t\} is the maximum of all the tabloids showing up as summands in e_t. And these standard tabloids are all distinct, since they arise from distinct standard tableaux. Thus our lemma shows that not only are the standard polytabloids e_t distinct, they are actually linearly independent vectors in M^\lambda.

January 13, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 3 Comments

The Maximality of Standard Tableaux

Standard tableaux have a certain maximality property with respect to the dominance order on tabloids. Specifically, if t is standard and \{s\} appears as a summand in the polytabloid e_t, then \{t\}\trianglerighteq\{s\}.

Any such \{s\} comes from s=\pi t, where \pi\in C_t. We will make our induction on the number of “column inversions” in s. That is, the number of pairs of entries k<l that are in the same column of s, but which are “out of order”, in the sense that k is in a lower row than l.

Given any such pair, the dominance lemma tells us that \{s\}\triangleleft(k\,l)\{s\}. That is, by “untwisting” the column inversion, we can move up the dominance order while preserving the columns. It should also be clear that (k\,l)\{s\} has fewer column inversions than \{s\} does. But if we undo all the column inversions, the tableau we’re left with must be standard. That is, it must be \{t\} itself.

January 13, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 2 Comments

The Dominance Lemma for Tabloids

If k<l, and k appears in a lower row than l in the Young tabloid \{t\}, then (k\,l)\{t\} dominates \{t\}. That is, swapping two entries of \{t\} so as to move the lower number to a higher row moves the tabloid up in the dominance relations.

Let the composition sequences of \{t\} and (k\,l)\{t\} be \lambda^i and \mu^i, respectively. For i<k and i\geq l we automatically have \lambda^i=\mu^i. For k\leq i<l there is a difference between the two: the entry k has been added in a different place. Let k and l be in rows q and r of \{t\}, respectively. In \lambda^i, the entry k is added to row q, while in \mu^i it’s been added to row r. That is, \lambda^i is the same as \mu^i with part q increased by one and part r decreased by one. Our assumption that k is in a lower row than l in \{t\} is that q>r. Therefore, since the lower row in \lambda^i is less than in \mu^i, we find that \lambda^i\triangleleft\mu^i. And we conclude that \{t\}\trianglelefteq(k\,l)\{t\}, as asserted.

January 11, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 3 Comments

The Dominance Order on Tabloids

Sorry, this should have gone up last Friday.

If \{t\} is a Young tabloid with shape \lambda\vdash n, we can define tabloids \{t^i\} for each i from 1 to n by letting \{t^i\} be formed by the entries in \{t\} less than or equal to i. We define \lambda^i to be the shape of \{t^i\} as a composition. For example, if we have

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

then we define

\displaystyle\begin{aligned}\{t^1\}&=\begin{array}{c}\cline{1-1}\\\cline{1-1}1\\\cline{1-1}\end{array}\\\lambda^1&=(0,1)\\\{t^2\}&=\begin{array}{c}\cline{1-1}2\\\cline{1-1}1\\\cline{1-1}\end{array}\\\lambda^2&=(1,1)\\\{t^3\}&=\begin{array}{cc}\cline{1-2}2&3\\\cline{1-2}1&\\\cline{1-1}\end{array}\\\lambda^3&=(2,1)\\\{t^4\}&=\begin{array}{cc}\cline{1-2}2&3\\\cline{1-2}1&4\\\cline{1-2}\end{array}\\\lambda^4&=(2,2)\end{aligned}

Along the way we see why we might want to consider a composition like (0,1) with a zero part.

Anyway, now we define a dominance order on tabloids. If \{s\} and \{t\} are two tabloids with composition sequences \lambda^i and \mu^i, respectively, then we say \{s\} “dominates” \{t\} — and we write \{s\}\triangleright\{t\} — if \lambda^i dominates \mu^i for all i.

As a (big!) example, we can write down the dominance order on all tabloids of shape (2,2):

\displaystyle\begin{array}{ccccc}&&\begin{array}{cc}\cline{1-2}1&2\\\cline{1-2}3&4\\\cline{1-2}\end{array}&&\\&&\uparrow&&\\&&\begin{array}{cc}\cline{1-2}1&3\\\cline{1-2}2&4\\\cline{1-2}\end{array}&&\\&\nearrow&&\nwarrow&\\\begin{array}{cc}\cline{1-2}2&3\\\cline{1-2}1&4\\\cline{1-2}\end{array}&&&&\begin{array}{cc}\cline{1-2}1&4\\\cline{1-2}2&3\\\cline{1-2}\end{array}\\&\nwarrow&&\nearrow&\\&&\begin{array}{cc}\cline{1-2}2&4\\\cline{1-2}1&3\\\cline{1-2}\end{array}&&\\&&\uparrow&&\\&&\begin{array}{cc}\cline{1-2}3&4\\\cline{1-2}1&2\\\cline{1-2}\end{array}&&\end{array}

It’s an exercise to verify that these are indeed all the tabloids with this shape. For each arrow, we can verify the dominance. As an example, let’s show that

\displaystyle\begin{array}{cc}\cline{1-2}1&2\\\cline{1-2}3&4\\\cline{1-2}\end{array}\trianglerighteq\begin{array}{cc}\cline{1-2}2&3\\\cline{1-2}1&4\\\cline{1-2}\end{array}

First, let’s write down their composition sequences:

\displaystyle\begin{array}{c|cc}i&\lambda^i&\mu^i\\\cline{1-3}1&(1)&(0,1)\\2&(2)&(1,1)\\3&(2,1)&(2,1)\\4&(2,2)&(2,2)\end{array}

Now it should be easy to see on each row that \lambda^i\trianglerighteq\mu^i. As another example, let’s try to compare \begin{array}{cc}\cline{1-2}2&3\\\cline{1-2}1&4\\\cline{1-2}\end{array} and \begin{array}{cc}\cline{1-2}1&4\\\cline{1-2}2&3\\\cline{1-2}\end{array}. Again, we write down their composition sequences:

\displaystyle\begin{array}{c|cc}i&\lambda^i&\mu^i\\\cline{1-3}1&(0,1)&(1)\\2&(1,1)&(1,1)\\3&(2,1)&(1,2)\\4&(2,2)&(2,2)\end{array}

We see that \lambda^1\not\trianglerighteq\mu^1, but \mu^3\not\trianglerighteq\lambda^3. Thus neither tabloid dominates the other. The other examples to verify this diagram are all similarly straightforward.

January 10, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 4 Comments

Compositions

A “composition” is sort of like a partition, except the parts are allowed to come in any specified order. That is, a composition of n is an ordered sequence of nonnegative integers \lambda=(\lambda_1,\dots,\lambda_k) that sums up to n. Every partition is a composition — specifically one in which the sequence is nonincreasing. Since a general composition allows its parts to increase, it’s possible that some of the \lambda_i are zero, which can’t really happen for partitions.

The notions of Ferrers diagrams and Young tableaux, and Young tabloids carry over right away to compositions. For instance, the Ferrers diagram of the composition (1,3,2) is

\displaystyle\begin{array}{ccc}\bullet&&\\\bullet&\bullet&\bullet\\\bullet&\bullet&\end{array}

and one possible Young tableau with this shape is

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

Now, it should be made clear that this is not a standard tableau, despite the fact that the rows and columns increase. The usual line is that we imagine the tableau to be at the upper-left corner of a quarter-plane, so there are cells extending out to the right and bottom of the diagram that aren’t part of the tableau. These, we say, are all filled with \infty, and so the second column of this particular tableau is “actually” (\infty,3,6,\dots), so it doesn’t actually increase after all. But as far as I can tell this is a lot of word salad designed to back up the definition we really want: the notion of standard Young tableaux only applies to partitions, not to compositions in general.

We can, however, extend the idea of the dominance order to general compositions. As usual we say that \lambda\trianglerighteq\mu if

\displaystyle\lambda_1+\dots+\lambda_i\geq\mu_1+\dots+\mu_i

for all i. We just don’t have to add up all the biggest parts first.

January 6, 2011 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 2 Comments

Standard Tableaux

So we’ve described the Specht modules, and we’ve shown that they give us a complete set of irreducible representations for the symmetric groups. But we haven’t described them very explicitly, and we certainl can’t say much about them. There’s still work to be done.

We say that a Young tableau t is “standard” if its rows and columns are all increasing sequences. In this case, we also say that the Young tabloid \{t\} and the polytabloid e_t=\kappa_t\{t\} are standard.

Recall that we had a canonical Young tableau for each shape \lambda that listed the numbers from 1 to n in each row from top to bottom, as in

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

It should be clear that this canonical tableau is standard, so there is always at least one standard tableau for each shape. There may be more, of course. For example:

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

Clearly, any two distinct standard tableaux s^\lambda and t^\lambda give rise to distinct tabloids \{s\} and \{t\}. Indeed, if \{s\}=\{t\}, then s and t would have to be row-equivalent. But only one Young tableau in any row-equivalence class has increasing rows, and only that one even has a chance to be standard. Thus if s and t are row-equivalent standard tableaux, they must be equal.

What’s not immediately clear is that the standard polytabloids e_s and e_t are distinct. Further, it turns out that the collection of standard polytabloids e_t of shape \lambda is actually independent, and furnishes a basis for the Specht module S^\lambda. This is our next major goal.

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

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

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

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

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

Follow

Get every new post delivered to your Inbox.

Join 366 other followers