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.

partition_transpose_by_diagram

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 (nd) = (4, 4), (3, 5), (4, 5), (5, 5).

This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

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