Polynomials and Representations II

More About Partitions

Recall that a partition $\lambda$ is a sequence of weakly decreasing non-negative integers, where appending or dropping ending zeros gives us the same partition. A partition is usually represented graphically as a table of boxes or dots:

partition_boxes_and_dots

We will be using the left diagram – this is called the Young diagram of $\lambda$ .

We will also use notations $|\lambda| := \sum_i \lambda_i$ and write $l(\lambda)$ for the largest $i$ for which $\lambda_i > 0$ . If $|\lambda| = d$ , we also say $\lambda \vdash d.$ For example if $\lambda = (5, 4, 2)$ , then:

$|\lambda| = 11$ ;
$l(\lambda) = 3$ ;
$\lambda$ is a partition of 11, or $\lambda \vdash 11$ .

Definition. If $\lambda$ is a partition, its transpose $\overline \lambda$ is the partition obtained by flipping the Young diagram about the main diagonal.

We will be labeling variables with partitions $v_\lambda$ so it helps to have an ordering on the set of all partitions of d. The lexicographical order (or dictionary order) on the set $\{\lambda : \lambda \vdash d\}$ is given as follows: $\lambda < \mu$ if and only if there is an $i$ such that

$\lambda_1 = \mu_1, \ \lambda_2 = \mu_2,\ \ldots,\ \lambda_i = \mu_i,\ \lambda_{i+1} < \mu_{i+1}.$

For example, the set of all partitions of 5 is ordered as follows:

(1, 1, 1, 1, 1) < (2, 1, 1, 1) < (2, 2, 1) < (3, 1, 1) < (3, 2) < (4, 1) < (5).

However, algorithmically it is easier to generate the set of partitions in the reverse lexicographical order, so in labeling $v_\lambda$ we will use that instead.

blue-lin

Dominance Ordering of Partitions

Now, the lexicographical ordering is total (i.e. any two partitions can be compared), but the problem is that taking the transpose does not give us any discernible result. E.g. for partitions of 6, we have:

(2,2,1,1) < (2,2,2) and taking the transpose gives (4,2) > (3,3).
(2,2,2) < (3,1,1,1) but taking the transpose gives (3,3) < (4,1,1).

Thus, we consider the following partial ordering instead.

Definition. Given partitions $\lambda, \mu$ of d, we write $\lambda \trianglelefteq \mu$ if for each i we have

$\lambda_1 + \lambda_2 + \ldots + \lambda_i \le \mu_1 + \mu_2 + \ldots + \mu_i.$

Although the definition makes sense for any two partitions, in practice we only use them to compare cases where $|\lambda| = |\mu|.$ We have the following.

Proposition. For $\lambda, \mu \vdash d$ , we have $\lambda \trianglelefteq \mu$ if and only if $\overline\lambda \trianglerighteq \overline\mu.$

Proof.

Suppose $\lambda\trianglelefteq \mu$ . We first claim that, for each $k\ge 1$ , we have:

$(\overline\lambda_1 + \overline\lambda_2 + \ldots + \overline \lambda_k) + (\lambda_1 - k) + (\lambda_2 - k) + \ldots + (\lambda_j - k) = |\lambda| = |\mu|$

where $j = \overline\lambda_k$ is the largest value for which $\lambda_j \ge k$ ; equivalently, $j$ is the largest value for which $\lambda_j - k \ge 0.$ The claim can be readily seen from the diagram below:

partition_transpose_sum

Now $(\lambda_1 - k) + \ldots + (\lambda_j - k) \le (\mu_1 - k) + \ldots + (\mu_j - k).$ Let $j' = \overline\mu_k$ . We have two cases.

If $j \le j'$ , then this sum is at most $(\mu_1 - k) + \ldots +(\mu_{j'} - k)$ since there are more non-negative terms in the sum.
If $j > j'$ , the sum is still at most $(\mu_1 - k) + \ldots +(\mu_{j'} - k)$ since the excess terms $\mu_{j'+1} - k, \ldots, \mu_j - k$ are negative.

Hence $(\lambda_1 - k) + \ldots + (\lambda_j - k) \le (\mu_1 - k) + \ldots + (\mu_{j'} - k)$ which gives:

$\overline \lambda_1 + \overline \lambda_2 + \ldots + \overline \lambda_k \ge \overline \mu_1+ \overline \mu_2 + \ldots + \overline \mu_k.$

So $\lambda \trianglelefteq \mu \implies \overline\lambda \trianglerighteq \overline\mu$ ; replacing $\lambda,\mu$ by their transposes we get the reverse implication. ♦

Thus, in our above example, $(2,2,1,1) \trianglelefteq (2,2,2)$ and the transpose gives $(4,2) \trianglerighteq (3,3)$ . On the other hand $(2,2,2) \not\trianglelefteq (3,1,1,1).$

blue-lin

Properties of $N_{\lambda\mu}$

Previously, we saw that the elementary symmetric polynomial $e_\lambda$ can be expressed as:

$\displaystyle e_\lambda = \sum_{\mu \vdash d} N_{\lambda\mu} m_\mu.$

In the case where $l(\mu) > n$ , the monomial $m_\mu = 0$ vanishes. Now, we write the above expression vectorially.

$\mathbf e = \mathbf N \mathbf m$

Lemma 1. For each partition $\lambda$ , we have $N_{\lambda\overline \lambda} = 1.$

Proof.

We claim that the unique binary matrix is obtained from the Young diagram by replacing boxes (or dots) with 1’s. E.g. for $\lambda = (5, 4, 2)$ and $\overline \lambda = (3, 3, 2, 2, 1)$ , the matrix must be:

$\begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{pmatrix}.$

Indeed, the first row must be filled with all 1’s since the number of columns is exactly $\lambda_1.$ Removing the first row and dropping trailing zeros in $\overline\lambda,$ the number of remaining columns is exactly $\lambda_2$ so the second row must be filled with all 1’s. And so on. ♦

Lemma 2. For any partitions $\lambda, \mu$ of $d$ , if $N_{\lambda\mu}>0$ then $\lambda \trianglelefteq \overline\mu.$

Proof.

Suppose $(a_{ij})$ is a binary matrix whose row sums are $\lambda_i$ and column sums are $\mu_j.$ Erase the 0’s and replace the 1’s in the matrix by consecutive 1, 2, …, d, where $d = |\lambda| = |\mu|.$ E.g. if $\lambda = (3, 2, 2, 1)$ and $\mu = (2, 2, 2, 1, 1)$ , pick:

$\begin{array}{|c|ccccc|} \hline 3 & 1 &1 & 0 & 1 & 0 \\ 2 & 1 & 0 & 1 & 0 & 0\\ 2 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ \hline & 2 & 2 & 2 & 1 & 1 \\ \hline\end{array} \implies \begin{array}{|ccccc|}\hline 1 & 2 & & 3 & \\ 4 & & 5 & & \\ & & 6 & & 7 \\ & 8 & & & \\ \hline\end{array}$

Left-justify the resulting matrix to obtain a matrix. Similarly, top-justify it to obtain another matrix:

$M_S = \left[\begin{matrix} 1 & 2 & 3 \\ 4 & 5 \\6 & 7 \\8 \end{matrix}\right] \qquad M_T = \left[\begin{matrix} 1 & 2 & 5 & 3 & 7\\ 4 & 8 & 6\end{matrix}\right].$

Note that $M_S$ and $M_T$ have shapes $\lambda$ and $\overline \mu$ respectively, i.e. there are $\lambda_i$ terms in row i of $M_S$ and $\overline \mu_i$ terms in row i of $M_T.$ By construction, if an element occurs in row i of $M_S,$ then it must occur in row i or above in $M_T.$ Thus, the number of elements in rows 1-k of $M_S$ is at most the number of elements in rows 1-k of $M_T$ and we have:

$\lambda_1 + \lambda_2 + \ldots + \lambda_k \le \overline\mu_1 + \overline\mu_2 + \ldots + \overline\mu_k$

as desired. ♦

blue-lin

Elementary Symmetric Polynomials as Basis

Now let $\mathbf J$ be the permutation matrix which switches $\lambda$ with its transpose $\overline \lambda.$ The prior two lemmas show that $\mathbf J \mathbf N$ is upper-triangular, with all 1’s on the main diagonal. Hence $\mathbf J\mathbf N$ is invertible over the integers, and so is $\mathbf N$ .

Example: n=3, d=4.

We have:

$\small\begin{pmatrix} e_{31} \\ e_{22} \\ e_{211} \\ e_{1111} \end{pmatrix} = \begin{pmatrix}0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 1 & 2 & 5 \\ 1 & 4 & 6 & 12 \end{pmatrix} \begin{pmatrix} m_4 \\ m_{31}\\ m_{22}\\ m_{211}\end{pmatrix}\\ \implies \mathbf N=\begin{pmatrix}0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 2\\ 0 & 1 & 2 & 5 \\ 1 & 4 & 6 & 12 \end{pmatrix}, \mathbf J = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0\end{pmatrix}.$

Since we know that

$\{m_\lambda : |\lambda| = d, l(\lambda) \le n\}$

gives a Z-basis of $\Lambda_n^{(d)}$ , we see that

$\{ e_\lambda : |\lambda| = d, \lambda_1 \le n\}$

gives a Z-basis as well, since J (taking transpose) gives a bijection between partitions

$\{\lambda: |\lambda| = d, l(\lambda) \le n\} \leftrightarrow \{ \lambda: |\lambda|=d, \lambda_1 \le n\}.$

As a result:

Corollary. We have $\Lambda_n \cong \mathbb{Z}[e_1, \ldots, e_n]$ , where the RHS is a freely generated commutative ring. The isomorphism preserves the grading, where $deg(e_i) = i.$

Exercise

Work out the matrices J and N for the cases of (n, d) = (4, 4), (3, 5), (4, 5), (5, 5).