Math 202C: Lecture 7

*** Problems in this lecture due April 19 at 23:59 ***

Recall our objective: we know that

\{m_\lambda(x_1,\dots,x_n) \colon \lambda \in \mathrm{Par}_n^d\}

is a basis for \mathcal{S}_n^d = \mathbb{C}[x_1,\dots,x_n]^{S_n}, and we are trying to prove that

\{e_\lambda(x_1,\dots,x_n) \colon \lambda^\prime \in \mathrm{Par}_n^d\}

is a second basis, where \lambda^\prime is the partition obtained by transposing the Young diagram of \lambda. Thus, the condition \lambda^\prime \in \mathrm{Par}_n^d means that the largest part of \lambda satisfies \lambda_1 \leq n, hence all parts of \lambda are bounded by n. Since

e_{\lambda}(x_1,\dots,x_n) = \prod\limits_{i=1}^{\ell(\lambda)} e_{\lambda_i}(x_1,\dots,x_n)

is defined multiplicatively, this is equivalent to the statement that \mathbb{C}[x_1,\dots,x_n]^{S_n}=\mathbb{C}[e_1,\dots,e_n]. Note that since \lambda is a partition of d, we can write it as \lambda=(\lambda_1,\dots,\lambda_d) where we allow trailing zero coordinates, and declare e_0(x_1,\dots,x_n)=1.

Theorem 7.1. For every \lambda \vdash d with \lambda_1 \leq n, we have

e_{\lambda^\prime}(x_1,\dots,x_n) = \sum\limits_{\mu \in \mathrm{Par}_n^d} M_{\lambda\mu}m_\mu(x_1,\dots,x_n)

where M_{\lambda\mu} is the number of d \times n matrices with entries in \{0,1\} with row sum vector \lambda=(\lambda_1,\dots,\lambda_d) and column sum vector \mu=(\mu_1,\dots,\mu_n).

Proof: Our objective is to expand the product

e_{\lambda}(x_1,\dots,x_n)=\prod\limits_{i=1}^d e_{\lambda_i}(x_1,\dots,x_n)

as a sum of monomials, where each factor in the product has the form

e_{\lambda_i}(x_1,\dots,x_n)=\sum\limits_{\substack{S \subseteq [n] \\ |S|=\lambda_i}} \prod\limits_{i \in S} x_i

and by convention e_0(x_1,\dots,x_n)=1. Also, [n]=\{1,\dots,n\}. To visualize the monomials which occur in this expansion, write down the d \times n symbolic matrix

\begin{bmatrix} x_1 & x_2 & \dots & x_n \\ x_1 & x_2 & \dots & x_n \\ \vdots & \vdots & \dots & \vdots \\ x_1 & x_2 & \dots & x_n \end{bmatrix}

obtained by listing the variable sequence x_1,x_2,\dots,x_n a total of d times. Each monomial in the expansion of e_\lambda(x_1,\dots,x_n) is obtained exactly once by choosing \lambda_i distinct entries from the first row of the above matrix, \lambda_2 distinct entries from the second row, etc. This selection process can be recorded by setting all chosen elements to 1 and all unchosen elements to 0, leaving a d \times n matrix with entries in \{0,1\} whose row sums form the list \lambda=(\lambda_1,\dots,\lambda_n). The meaning of the list \alpha=(\alpha_1,\dots,\alpha_n) of column sums of this \{0,1\}-matrix is that \alpha_1 is the number of times the variable x_1 was chosen, \alpha_2 is the number of times the variable x_2 was chosen, etc., so that \alpha_1+\dots+\alpha_n=d. Thus the number of times the monomial

x^\alpha=x_1^{\alpha_1} \dots x_n^{\alpha_n}

appears in the expansion is M_{\lambda\alpha}, the number of d \times n matrices over \{0,1\} with row sums given by the partition \lambda of d and column sums given the by the composition \alpha of d. That is, we have

e_\lambda(x_1,\dots,x_n)=\sum\limits_{\alpha \in \mathrm{Com}_n^d} x^\lambda.

Finally, if \mu \in \mathrm{Par}_n^d is the weakly decreasing rearrangement of \alpha, we have M_{\lambda\alpha}=M_{\lambda\mu} since permuting columns has no effect on row sums. \square

In order to parlay the above expansion into a proof that \{e_\lambda \colon \lambda^\prime \in \mathrm{Par}_n^d\} is a basis of \mathcal{S}_n^d, we want to exploit properties of the “matrix” of coefficients M_{\lambda\mu}. The quotes indicate the fact that, since we have not said how the elements of \mathrm{Par}_n^d should be ordered, we have not said how the numbers M_{\lambda\mu} should be tabulated.

In order to rectify this, we first introduce a partial order on \mathrm{Par}_n^d called dominance order. This is not as kinky as it sounds, and is in fact given by a very straightforward recipe: given two nonnegative integer vectors \mu=(\mu_1,\dots,\mu_n) and \nu=(\nu_1,\dots,\nu_n) with weakly decreasing coordinates and total sum equal to d, we declare \mu \leq \nu if and only if

\mu_1 + \dots + \mu_k \leq \nu_1 + \dots + \nu_k

holds for all 1 \leq k \leq n.

Problem 7.1. Prove that dominance order really is a partial order on \mathrm{Par}_n^d\}.

The key property of dominance order in relation to Theorem 7.1 is the following.

Problem 7.2. Prove that the numbers M_{\lambda\mu} defined by Theorem 7.1 satisfy M_{\lambda\mu}=0 unless \mu \leq \lambda^\prime, and that moreover M_{\lambda\lambda^\prime}=1.

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply