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.

December 21, 2010 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | Leave a comment