The Unapologetic Mathematician

Mathematics for the interested outsider

The Lexicographic Order on Partitions

The biggest problem with the dominance order is that it’s only a partial order. That is, there are some pairs of partitions \lambda and \mu so that neither \lambda\trianglerighteq\mu nor \mu\triangleright\lambda. We sometimes need a total order, and that’s where the lexicographic order comes in.

The lexicographic order gets its name because it’s just like the way we put words in order in the dictionary. We compare the first parts of each partition. If they’re different we use their order, while if they’re the same we break ties with the tails of the partitions. More explicitly, \lambda<\mu if for some i we have \lambda_j=\mu_j for all j<i, and \lambda_i<\mu_i.

As an example, here’s the lexicographic order on the partitions of 6:

\displaystyle\begin{aligned}(6)&>(5,1)\\&>(4,2)\\&>(4,1,1)\\&>(3,3)\\&>(3,2,1)\\&>(3,1,1,1)\\&>(2,2,2)\\&>(2,2,1,1)\\&>(2,1,1,1,1)\\&>(1,1,1,1,1,1)\end{aligned}

Now, comparing this order to the dominance order, we notice that they’re almost the same. Specifically, every time \lambda\trianglerighteq\mu, we find \lambda>\mu as well.

If \lambda=\mu, then this is trivially true. But if \lambda\neq\mu there must be at least one i with \lambda_i\neq\mu_i. Let i be the first such index. Now we find that

\displaystyle\sum\limits_{j=1}^{i-1}\lambda_j=\sum\limits_{j=1}^{i-1}\mu_j

and also

\displaystyle\sum\limits_{j=1}^i\lambda_j>\sum\limits_{j=1}^i\mu_j

This inequality must go in this direction since \lambda\triangleright\mu. We conclude that \lambda_i>\mu_i, and so \lambda>\mu in the lexicographic order.

About these ads

December 21, 2010 - Posted by | Algebra, Representation Theory, Representations of Symmetric Groups

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 388 other followers

%d bloggers like this: