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 x, y, z):

$\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 x, y, z are given by x+y+z, xy+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 $|\lambda| =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. ♦

warning In 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.$

4 Responses to Polynomials and Representations I

Manas Jana says:

May 12, 2020 at 1:46 pm

I think in the last theorem there should be $|\lambda |=d$

- limsup says:
  
  May 13, 2020 at 4:25 am
  
  Thanks. Corrected.
  
  - Manas Jana says:
    
    May 13, 2020 at 4:26 am
    
    Can you give your mail. My mail id m——-@gmail.com.
    
    [ Author: thanks. I’ve edited your email to prevent people from spamming you. ]
Manas Jana says:

May 12, 2020 at 1:47 pm

Please reply. Actually i don’t know your mail.. thank you.