Polynomials and Representations I

We have already seen symmetric polynomials and some of their applications in an earlier article. Let us delve into this a little more deeply. Consider the ring \mathbb{Z}[x_1, \ldots, x_n] of integer polynomials. The symmetric group S_n acts on it by permuting the variables; specifically, \sigma \in S_n takes:

f(x_1, \ldots, x_n) \mapsto f(x_{\sigma(1)}, \ldots, x_{\sigma(n)}).

For example, \sigma = {\small\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\end{pmatrix}} takes x_1 + 2x_2 + 3x_3 to x_2 + 2x_3 + 3x_1. Denote the ring of symmetric polynomials by:

\Lambda_n:= \mathbb{Z}[x_1, \ldots, x_n]^{S_n}.

This is a homogeneous ring, written as a direct sum:

\Lambda_n = \Lambda_n^{(0)} \oplus \Lambda_n^{(1)} \oplus \ldots,

where \Lambda_n^{(d)} is the additive group of homogeneous polynomials of degree d. For example, when n=3, we have (upon renaming the variables to xyz):

\begin{aligned} x+y+z &\in \Lambda_3^{(1)},\\ xy + yz + zx &\in \Lambda_3^{(2)},\\x^2 (y+z) + y^2(z+x) + z^2(x+y) &\in \Lambda_3^{(3)}.\end{aligned}

Let us fix n, the number of variables.

blue-lin

Monomial Basis

Clearly, each \Lambda_n^{(d)} is a free additive abelian group. For example, for \Lambda_3^{(3)}, a basis is given by:

x^3 + y^3+ z^3, \ x^2(y+z) + y^2(x+z) + z^2(x+y), \ xyz.

More generally, recall that a partition \lambda of d is a sequence of non-negative integers:

\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_l), \qquad \lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_l \ge 0, \qquad \sum_i \lambda_i = d.

Two partitions of d are considered the same if we can obtain one from the other by appending or dropping zeros. E.g. (3, 2, 1, 0) and (3, 2, 1) are identical partitions of 6.

Definition. Given a partition \lambda of d, let m_\lambda be the symmetric polynomial obtained by summing all terms of the form:

x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2}\ldots x_{i_l}^{\alpha_l}, \qquad {\small\begin{aligned} & 1\le i_1 < \ldots < i_l \le n, \\ & \alpha_1, \alpha_2, \ldots, \alpha_l \text{ is a permutation of } \lambda_1, \lambda_2, \ldots, \lambda_l.\end{aligned}}

For example when n=3, we have m_{(3)} = x^3 + y^3 + z^3, and m_{(2,1)} = x^2(y+z) + y^2(x+z) + z^2(x+y).

The following result is clear.

Theorem. The additive group \Lambda_n^{(d)} is free with basis given by m_\lambda, for all partitions \lambda of d into at most n parts.

Let us consider an example where d=4, n=3. A basis of \Lambda_3^{(4)} is given by:

\begin{aligned} m_{4} &= x^4 + y^4 + z^4,\\ m_{31} &= x^3 (y+z) + y^3 (x+z) + z^3(x+y),\\ m_{22} &= x^2 y^2 + y^2 z^2 + z^2 x^2,\\ m_{211} &= x^2 yz + xy^2 z + xyz^2. \end{aligned}

Note that for brevity of notation, we write m_{211} instead of m_{(2,1,1)}. However, if the subscripts involve variables, we will include the commas for clarity.

blue-lin

Elementary Symmetric Polynomials

Recall that the elementary symmetric polynomials in xyz are given by x+y+zxy+yz+zx and xyz. Generalizing this, we define:

e_0 = 1, \qquad e_k = \sum_{1 \le i_1 < i_2 < \ldots< i_k \le n} x_{i_1} x_{i_2} \ldots x_{i_k}\text{ for } 1 \le k \le n.

Furthermore, given a partition \lambda of d, we define:

e_\lambda := e_{\lambda_1} e_{\lambda_2} \ldots e_{\lambda_l},

assuming \lambda_{l+1} = \lambda_{l+2} = \ldots = 0. Note that since e_0 = 1, we can take as many terms as we want by increasing l without affecting e_\lambda. For example, when n=3 we have:

e_{3221} = xyz(xy + yz + zx)^2 (x+y+z).

Now since e_\lambda \in \Lambda_n^{(d)} (here, d=|\lambda| where |\lambda| denotes the sum of all \lambda_i), it is natural to ask the following question.

Task. Express the symmetric polynomial e_\lambda as a \mathbb{Z}-linear combination of the monomial polynomials m_\mu for various |\mu| = d.

In our above example, expanding e_{3221} with WolframAlpha gives us: m_{431} + 2m_{422} + 5m_{332}. In the remaining of this article, we will describe a more systematic method of computation.

blue-lin

Expanding the e‘s

Here is our main result.

Theorem. Suppose |\l| =d. Consider the expression

e_\lambda = \sum_{\mu} N_{\lambda\mu} m_\mu,

where we sum over all partitions \mu with |\mu| = d. The coefficient N_{\lambda\mu} is given by the number of matrices (a_{ij}) with entries either 0 or 1 such that

\sum_i a_{ij} = \lambda_j \text{ for each } j, \qquad \sum_j a_{ij} = \mu_i \text{ for each } i.

Here is a sample computation: take the polynomial e_{3221} above and find the coefficient for the monomial m_{332}. For that, we need to find the number of binary matrices with column sums \lambda = (3,2,2,1) and row sum \mu = (3,3,2). As expected, we get 5 solutions:

five_binary_matrices

Proof of Theorem.

Using the above example with n=3, we expand e_\lambda = e_{\lambda_1} e_{\lambda_2} \ldots e_{\lambda_l} and attempt to find the coefficient of x^\mu = x_1^{\mu_1} x_2^{\mu_2} \ldots x_l^{\mu_l}. E.g. suppose \lambda = (3, 2, 2, 1) and \mu = (3, 3, 2). We wish to expand:

e_3 e_2 e_2 e_1 = x_1 x_2 x_3(x_1 x_2 + x_1 x_3 + x_2 x_3)(x_1 x_2 + x_1 x_3 + x_2 x_3) (x_1 + x_2 + x_3).

Here is one way we can multiply terms to obtain x^\mu = x_1^3 x_2^3 x_3^2.

\begin{aligned} e_3 = &\boxed{x_1 x_2 x_3}, \\ e_2 = x_1 x_2 + &\boxed{x_1 x_3} + x_2 x_3, \\ e_2 = &\boxed{x_1 x_2} + x_1 x_3 + x_2 x_3,\\ e_1 = x_1 + &\boxed{x_2} + x_3. \end{aligned}\implies \begin{array}{|c|ccc|} \hline 3 & 1 & 1 & 1 \\ 2 & 1 & 0 & 1 \\ 2 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ \hline & 3 & 3 & 2\\ \hline \end{array}

Thus each binary matrix corresponds to a way of obtaining x^\mu by multiplying terms from e_{\lambda_1}, e_{\lambda_2}, etc. ♦

warningIn the definition of N_{\lambda\mu}, the variable n is ostensibly missing. However note that if \mu_{n+1} > 0, then the monomial m_{\mu}=0 since it would involve more than n variables. For example, if n=2 and \lambda = (2,1), then the above expansion gives e_{21} = m_{21} + 3m_{111} = m_{21} since m_{111} = 0. One can verify this directly by expanding e_{21} = xy(x+y).

On the other hand, if n=3, we now have e_{21} = (xy + yz + zx)(x+y+z) = m_{21} + 3m_{111} and now m_{111} \ne 0.

blue-lin

Exercise

1. Express (w + x + y + z)^4 as a linear combination of the monomial symmetric polynomials:

m_4, \quad m_{31},\quad m_{22}, \quad m_{211}, \quad m_{1111}.

Check your computations with WolframAlpha.

2. Write a program in Python (or any language) which computes N_{\lambda\mu} for any partitions \lambda, \mu.

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