The Unapologetic Mathematician

The Column Dominance Order

Okay, for the last couple posts I’ve talked about using Garnir elements to rewrite nonstandard polytabloids — those coming from tableaux containing “row descents” — in terms of “more standard” polytabloids. Finally, we’re going to define another partial order that will give some meaning to this language.

Given a tableau $t$, consider the column stabilizer $C_t$, and use it to build the “column tabloid” $[t]=C_tt$. This is defined just like our other tabloids, except by shuffling columns instead of rows.

For example, consider the tabloid

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

from which we get the column tabloid

$\displaystyle\begin{array}{|c|c|}1&2\\3&\multicolumn{1}{c}{}\end{array}=\left\{\begin{array}{cc}1&2\\3&\end{array},\begin{array}{cc}3&2\\1&\end{array}\right\}$

And now we can define the dominance order on column tabloids just like the dominance order for row tabloids. Of course, in doing so we have to alter our definition of the dominance order on Ferrers diagrams to take columns into account instead of rows.

But one thing at least will make our life simpler: it should be clear that we still have a dominance lemma for column dominance. To be explicit: if $k< l$, and $k$ appears in a column to the right of $l$ in the column tabloid $[t]$, then $(k\,l)[t]$ dominates $[t]$ in the column dominance order.

January 20, 2011

Properties of Garnir Elements from Tableaux 1

Pick a Young tableau $t$, and sets $A$ and $B$ as we did last time. If there are more entries in $A\uplus B$ than there are in the $j$th column of $t$ — the one containing $A$ — then $g_{A,B}e_t=0$. In particular, if we pick $A$ and $B$ by selecting a row descent, letting $A$ be the entries below the left entry, and letting $B$ be the entries above the right entry, then this situation will hold.

As a first step, I say that ${S_{A\uplus B}}^-e_t=0$. That is, if we allow all the permutations of entries in these two sets (along with signs) then everything cancels out. Indeed, let $\sigma\in C_t$ be any column-stabilizing permutation. Our hypothesis on the number of entries in $A\uplus B$ tells us that we must have some pair of $a\in A$ and $b\in B$ in the same row of $\sigma t$. Thus the swap $(a\,b)\in S_{A\uplus B}$. The sign lemma then tells us that ${S_{A\uplus B}}^-\{\sigma t\}=0$. Since this is true for every summand $\{\sigma t\}$ of $e_t=C_t^-\{t\}$, it is true for $e_t$ itself.

Now, our assertion is not that this is true for all of $S_{A\uplus B}$, but rather that it holds for our transversal $\Pi$. We use the decomposition

$\displaystyle S_{A\uplus B}=\biguplus\limits_{\pi\in\Pi}\pi(S_A\times S_B)$

This gives us a factorization

$\displaystyle{S_{A\uplus B}}^-=\Pi^-(S_A\times S_B)^-=g_{A,B}(S_A\times S_B)^-$

And so we conclude that $g_{A,B}(S_A\times S_B)^-e_t=0$.

But now we note that $S_A\times S_B\subseteq C_t$. So if $\sigma\in S_A\times S_B$ we use the sign lemma to conclude

$\displaystyle\mathrm{sgn}(\sigma)\sigma e_t=\mathrm{sgn}(\sigma)\sigma C_t^-\{t\}=C_t^-\{t\}=e_t$

Thus $(S_A\times S_B)^-e_t=\lvert S_A\times S_B\rvert e_t$, and so

$\displaystyle 0=g_{A,B}(S_A\times S_B)^-e_t=g_{A,B}\lvert S_A\times S_B\rvert e_t=\lvert S_A\times S_B\rvert g_{A,B}e_t$

which can only happen if $g_{A,B}e_t=0$, as asserted.

This result will allow us to pick out a row descent in $t$ and write down a linear combination of polytabloids that lets us rewrite $e_t$ in terms of other polytabloids. And it will turn out that all the other polytabloids will be “more standard” than $e_t$.

January 18, 2011

Garnir Elements from Tableaux

There are, predictably enough, certain Garnir elements we’re particularly interested in. These come from Young tableaux, and will be useful to us as we move forward.

Given a tableau $t$, let $A$ be a subset of the entries in the $j$th column of $t$, and let $B$ be a subset of the entries in the $j+1$st column. We can come up with Garnir elements associated to this choice of $A$ and $B$, but — as we pointed out last time — we need some way of picking which particular transversal elements to use. For each summand in $g_{A,B}$, we separate $A\uplus B$ into a pair of sets $(A',B')$, but we have flexibility in how we order the elements of $A'$ and $B'$. Our answer in this case is to always pick the permutation that puts the elements of $A\uplus B$ into increasing order as we move down the columns of $t$.

For example, consider the tableau

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

This tableau has a “row descent” in the second row: a pair of adjacent entries in the row where the larger entry is on the left instead of the right. Let $A$ be the entry on the left along with all the entries below it in its column — $\{5,6\}$ — and let $B$ be the entry on the right along with all the entries above it in its column — $\{2,4\}$. We look at all six ways of rearranging the collection $\{2,4,5,6\}$ into two subsets of two elements each (we listed then last time, actually) and choose permutations that keep entries in increasing order as we move down the columns.

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

Notice that we’ve picked different permutations this time, and so we get a different Garnir element:

$\displaystyle g_{A,B}=e-(4\,5)+(2\,4\,5)+(4\,6\,5)-(2\,4\,6\,5)+(2\,5)(4\,6)$

Also, note that only the first of these tableaux has the descent in the second row, although some now have descents in the first row. Slightly less obvious is the fact that $g_{A,B}e_t=0$, and so we can write

$\displaystyle e_t=(4\,5)e_t-(2\,4\,5)e_t-(4\,6\,5)e_t+(2\,4\,6\,5)_t-(2\,5)(4\,6)e_t$

Thus we can rewrite this polytabloid that has a row descent in terms of a bunch of other polytabloids that don’t have it and are “more standard”, in a sense we’ll define later.

January 17, 2011

Garnir Elements

Let $A$ and $B$ be two disjoint sets of positive integers. We’re mostly interested in the symmetric group $S_{A\uplus B}$, which shuffles around all the integers in both sets. But a particularly interesting subgroup is $S_A\times S_B$, which shuffles around the integers in $A$ and $B$, but doesn’t mix the two together. Clearly, $S_A\times S_B$ is a subgroup of $S_{A\uplus B}$.

Now, let $\Pi\subseteq S_{A\uplus B}$ be a transversal collection of permutations for this subgroup. That is, we can decompose the group into cosets

$\displaystyle S_{A\uplus B}=\biguplus\limits_{\pi\in\Pi}\pi(S_A\times S_B)$

Then a “Garnir element” is

$\displaystyle g_{A,B}=\Pi^-=\sum\limits_{\pi\in\Pi}\mathrm{sgn}(\pi)\pi\in\mathbb{C}[S_{A\uplus B}]$

Now, the problem here is that we’ve written $g_{A,B}$ as if it only depends on the sets $A$ and $B$, when it clearly depends on the choice of the transversal $\Pi$. But we’ll leave this alone for the moment.

How can we come up with an explicit transversal in the first place? Well, consider the set of pairs of sets $(A',B')$ so that $\lvert A'\rvert=\lvert A\rvert$, $\lvert B'\rvert=\lvert B\rvert$, and $A'\uplus B'=A\uplus B$. That is, each $(A',B')$ is another way of breaking the same collection of integers up into two parts of the same sizes as $A$ and $B$.

Any permutation $\pi\in S_{A\uplus B}$ acts on the collection of such pairs of sets in the obvious way, sending $(A',B')$ to $(\pi(A'),\pi(B'))$, which is another such pair. In fact, it’s transitive, since we can always find some $\pi$ with $A'=\pi(A)$ and $B'=\pi(B)$. If for each $(A',B')$ we make just such a choice of $\pi$, then this collection of permutations gives us a transversal!

We can check this by first making sure we have the right number of elements. A pair $(A',B')$ is determined by taking all $\lvert A\uplus B\rvert$ integers and picking $\lvert A\rvert$ to go into $A'$. That is, we have

$\displaystyle\binom{\lvert A\uplus B\rvert}{\lvert A\rvert}=\frac{\lvert A\uplus B\rvert!}{\lvert A\rvert!\lvert B\rvert!}$

pairs. But this is also the number of cosets of $S_A\times S_B$ in $S_{A\uplus B}$!

Do we accidentally get two representatives $\pi$ and $\pi'$ for the same coset? If we did, then we’d have to have $\pi^{-1}\pi'\in S_A\times S_B$. But then $\pi^{-1}\pi'(A,B)=(A,B)$, and thus $\pi'(A,B)=\pi(A,B)$. But we only picked one permutation sending $(A,B)$ to a given pair, so $\pi'=\pi$.

As an example, let $A=\{5,6\}$ and $B=\{2,4\}$. Then we have six pairs of sets to consider

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

where in each case I’ve picked a $\pi$ that sends $(A,B)$ to $(A',B')$. This will give us the following Garnir element:

$g_{A,B}=e-(4\,5)-2\,5)-(4\,6)-(2\,6)+(2\,5)(4\,6)$

But, again, this is far from the only possible choice for this $A$ and $B$.

January 14, 2011

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

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

The Dominance Lemma for Tabloids

If $k, 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 and $i\geq l$ we automatically have $\lambda^i=\mu^i$. For $k\leq i 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

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

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

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