10.8 Symmetric Polynomials

Some Symmetric Polynomials: p, e and h

Definition

A polynomial in $m$ variables is called symmetric if it is stable under all permutations $\sigma \in S_m$, that is, $\sigma (p(x_1,\cdots ,x_n))=p(x_{\sigma (1)},\cdots ,x_{\sigma (n)})$.

The algebra of symmetric polynomials is denoted by ${\Lambda }_m$.

Examples. They are symmetric polynomials.

• $p_n=x_1^n+\cdots +x_m^n$ for all $n\in {\mathbb{N}}_{+}$, where the corresponding generated function is $P(t)={\sum }_{n=1}^{\infty }{p}_n{t}^{n-1}={\sum }_{i=1}^m\frac{x_i}{1-x_{i}t}$.
• The elementary symmetric polynomials $e_n={\sum }_{i_1<\cdots <i_n}{x}_{i_1}\cdots x_{i_n}$ for $n⩾1$. Furthermore, define $e_0=1$. Note that $e_n=0$ when $n⩾m$, and the corresponding generated function is $E(t)={\sum }_{n=0}^t{e}_n{t}^n={\prod }_{i=1}^m(1+x_{i}t)$.
• The complete symmetric polynomials $h_n={\sum }_{i_1⩽\cdots ⩽i_n}{x}_{i_1}\cdots x_{i_n}$ for $n⩾1$. We also define $h_0=1$, and the corresponding generated function is $H(t)={\sum }_{n=0}^{\infty }{h}_n{t}^n={\prod }_{i=1}^{\infty }\frac{1}{1-x_{i}t}$.

Since $H(t)E(-t)=1$, we have ${\sum }_{n=0}^{\infty }(-1{)}^r{e}_r{h}_{n-r}=0$. Next, notice that $p(t)=d/dt\ln {\prod }_{i=1}^{\infty }\frac{1}{1-x_{i}t}$, then

$$P(t)=d/dt\ln (H(t))=\frac{H^{\prime }(t)}{H(t)}.$$

Similarly $P(-t)=E^{\prime }(t)/E(t)$. It deduces the Newton identity.

the Newton identity

With the definition above, we have $n{h}_n={\sum }_{r=1}^{\infty }{p}_r{h}_{n-r}$ and $n{e}_n={\sum }_{r=1}^n(-1{)}^{r-1}{p}_r{e}_{n-r}$.

Proposition

If $A$ is an $m\times m$ matrix, then the coefficients of the characteristic polynomial $\det (A-tI)$ are given by the elementary symmetric functions of the eigenvalues $\left\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_m\right\}$, with alternating signs $\pm 1$ depending on the degree of each term. The power sums of the eigenvalues coincide with $\mathrm{tr}{A}^n={\lambda }_1^n+\cdots +{\lambda }_m^n$.

Remark. There is some connection between symmetric polynomials and the rooted solution of polynomial equations. See here. When the degree of polynomial is less than or equal to $4$, the roots can be obtained by operating the coefficients by combination of adding, subtracting, multiplication, division, and taking roots.

Schur Polynomial

Definition

Suppose $\lambda =({\lambda }_1,\cdots ,{\lambda }_m)$ is a partition of $n$ of length at most $m$. The Schur polynomial $s_{\lambda }$ is defined by

$$s_{\lambda }=\frac{\left|\begin{array}{ccc}{x}_1^{{\lambda }_1+m-1}& \cdots & x_m^{{\lambda }_1+m-1}\\ x_1^{{\lambda }_2+m-2}& \cdots & x_m^{{\lambda }_2+m-2}\\ ⋮& & ⋮\\ x_1^{{\lambda }_m}& \cdots & x_m^{{\lambda }_m}\end{array}\right|}{\left|\begin{array}{ccc}{x}_1^{m-1}& \cdots & x_m^{m-1}\\ x_1^{m-2}& \cdots & x_m^{m-2}\\ ⋮& & ⋮\\ 1& \cdots & 1\end{array}\right|}.$$

For example, when $\lambda =(n)$, $s_{\lambda }=h_n$. When $\lambda =1^n$ and $m=n$, $s_{\lambda }=x_1\cdots x_n$. We can prove them by computing directly, or by the following proposition.

Jacobi-Trudi formula

We have

$$s_{\lambda }=\left|\begin{array}{cccc}{h}_{{\lambda }_1}& h_{{\lambda }_1+1}& \cdots & h_{{\lambda }_1+m-1}\\ h_{{\lambda }_2-1}& h_{{\lambda }_2}& \cdots & h_{{\lambda }_2+m-2}\\ ⋮& ⋮& & ⋮\\ h_{{\lambda }_m-m+1}& h_{{\lambda }_m-m+2}& \cdots & h_{{\lambda }_m}\end{array}\right|.$$

\begin{proof} Let $\alpha =({\alpha }_1,\cdots ,{\alpha }_m)$ be a composition. Put

$$A_{\alpha }=\left[\begin{array}{ccc}{x}_1^{{\alpha }_1}& \cdots & x_m^{{\alpha }_1}\\ ⋮& & ⋮\\ x_1^{{\alpha }_m}& \cdots & x_m^{{\alpha }_m}\end{array}\right]\text{mbox}and{H}_{\alpha }=\left[\begin{array}{ccc}{h}_{{\alpha }_1-m+1}& \cdots & h_{{\alpha }_1}\\ ⋮& & ⋮\\ h_{{\alpha }_m-m+1}& \cdots & h_{{\alpha }_m}\end{array}\right].$$

Consider the elementary symmetric polynomial $e_n^{(k)}$ in variables $x_1,\cdots ,{\hat{x}}_k,\cdots ,x_m$ with $1⩽k⩽m$ and write them to $m\times m$ matrix

$$M=\left[\begin{array}{ccc}(-1{)}^{m-1}{e}_{m-1}^{(1)}& \cdots & (-1{)}^{m-1}{e}_{m-1}^{(m)}\\ ⋮& & ⋮\\ (-1)e_1^{(1)}& \cdots & (-1)e_1^{(m)}\\ 1& \cdots & 1\end{array}\right].$$

We claim that $A_{\alpha }=H_{\alpha }M$. Consider generating function for $e_n^{(k)}$

$$E^{(k)}(t)=\sum _{n=0}^{m-1}{e}_n^{(k)}{t}^n=\prod _{i\ne k}(1+x_{i}t),$$

then by $H(t)E(-t)=1$ there is

$$H(t)E^{(k)}(t)=\frac{1}{1-x_{k}t}=1+x_{k}t+\cdots +(x_{k}t{)}^{\ell }+\cdots .$$

Take the coefficient of $t^{{\alpha }_i}$ and we have

$$\sum _{j=1}^m{h}_{{\alpha }_i-m+j}(-1{)}^{m-j}{e}_{m-j}^{(k)}=x_k^{{\alpha }_i}.\text{\hspace{1em}(*)}$$

With $(\ast )$, we can prove the claim. Thus, $\det A_{\alpha }=\det H_{\alpha }\det M$ and so $\det H_{\alpha }=\det A_{\alpha }/\det M$. For $\delta =(m-1,m-2,\cdots ,1,0)$, the matrix $H_{\delta }=1$ and so $\det A_{\delta }=\det M$. It follows that

$$\det H_{\alpha }=\frac{\det A_{\alpha }}{\det A_{\delta }}=s_{\lambda },$$

where $\alpha =\lambda +\delta =({\lambda }_1+m-1,{\lambda }_2+m-2,\cdots ,{\lambda }_m)$. Now we finish the proof. \end{proof}

We have a more direct formula for $s_{\lambda }$ by considering a generalized tableau of shape $\lambda$.

Definition

We place numbers $\{1,\cdots ,n\}$ into tableau $\lambda ⊢n$ allowing repetition. Such tableau is called semistandard if rows are weakly increasing (not decreasing) while columns are strictly increasing sequences.

If $T$ is semistandard with $\{1,\cdots ,n\}$, set

$$x^T=\prod _{i=1}^n(x_i{)}^{\mathrm{numberofoccurrenceof}i\in T}.$$

Proposition

For $\lambda ⊢n$ with length $m$, the Schur polynomial in $m$ variables is $s_{\lambda }={\sum }_T{x}^T$.

Basis of ${\Lambda }_m$

Now we consider algebra of symmetric polynomials in $m$ variables.

First define ${\Lambda }_m^n=\mathrm{span}\{s_{\lambda }:\lambda ⊢n\}$, the subspace of homogeneous symmetric polynomial of degree $n$, and then define ${\Lambda }_m={\oplus }_{n⩾0}{\Lambda }_m^n$.

For example, when $m=3$, we have ${\Lambda }_m^0=\mathrm{span}\{1\}$, ${\Lambda }_m^1=\mathrm{span}\{x_1+x_2+x_3\}$,

$$\begin{array}{rl}{\Lambda }_m^2& =\mathrm{span}\{s_{(1,1)},s_{(2,0)}\}=\mathrm{span}\{x_1{x}_2+x_1{x}_3+x_2{x}_3,x_1^2+x_2^2+x_3^2+x_1{x}_2+x_1{x}_3+x_2{x}_3\},\\ {\Lambda }_m^3& =\mathrm{span}\{s_{(3)},s_{(2,1)},s_{(1,1,1)}\}=\mathrm{span}\{x_1{x}_2{x}_3,x_1^2{x}_2+x_1^2{x}_3+x_1{x}_2^2+2x_1{x}_2{x}_3+x_1{x}_3^2+x_2^2{x}_3+x_2{x}_3^2,h_3\}.\end{array}$$

Proposition

$s_{\lambda }$ is a basis for ${\Lambda }_m$ for all $\lambda ⊢n$ with $n⩾0$. (For a fixed $n$, $\lambda ⊢n$ running through all partitions $\{s_{\lambda }:\lambda ⊢n\}$ is a basis for ${\Lambda }_m^k$.)

Then we introduce a few families of symmetric polynomials for algebra ${\Lambda }_m$.

• For any partition $\lambda =({\lambda }_1,\cdots ,{\lambda }_m)$, define $p_{\lambda }=p_{{\lambda }_1}\cdots p_{{\lambda }_m}$, $e_{\lambda }=e_{{\lambda }_1}\cdots e_{{\lambda }_m}$ and $h_{\lambda }=h_{{\lambda }_1}\cdots h_{{\lambda }_m}$. For example, when $m=3$ and $n=2$, $p_{(2)}=p_2=x_1^2+x_2^2+x_3^2$ and $p_{(1,1)}=p_1{p}_1=(x_1+x_2+x_3{)}^2$, $e_{(2)}=e_2=x_1{x}_2+x_2{x}_3+x_1{x}_3$ and $e_{(1,1)}=e_1{e}_1=(x_1+x_2+x_3{)}^2$, $h_{(2)}=h_2=x_1^2+x_2^2+x_3^2+x_1{x}_2+x_1{x}_3+x_2{x}_3$ and $h_{(1,1)}=h_1{h}_1=(x_1+x_2+x_3{)}^2$.
• Let $\lambda =({\lambda }_1,\cdots ,{\lambda }_m)$. Another family of symmetric polynomials is defined as the sum of all different monomials obtained from $x_1^{{\lambda }_1}\cdots x_m^{{\lambda }_m}$ under permutation. For example, when $m=3$ and $n=2$, we have $m_{(2)}=x_1^2+x_2^2+x_3^2$, $m_{(1,1)}=2(x_1{x}_2+x_2{x}_3+x_1{x}_3)$.

Theorem

Suppose that $\lambda$ runs over all partitions of $n$ of length at most $m$. Then each of the following families is basis of the space ${\Lambda }_m^n$:

$$m_{\lambda },s_{\lambda },e_{{\lambda }^{\prime }},h_{{\lambda }^{\prime }},p_{{\lambda }^{\prime }},e_{\lambda },h_{\lambda },p_{\lambda }$$

In particular, $\dim {\Lambda }_m^n=p(n)$ with $m⩾n$.

\begin{proof} We first prove $\{m_{\lambda }:\lambda ⊢n\}$ is a basis. Note that they are linearly independent: If $\lambda ⊢n$ and $\mu ⊢n$ with $\lambda \ne \mu$, then $m_{\lambda }$ and $m_{\mu }$ have no common monomials. Hence, if ${\sum }_i{\alpha }_i{m}_{{\lambda }_i}=0$, then ${\alpha }_i=0$. Suppose $f\in {\Lambda }_m^n$, and we aim to show $f\in \mathrm{span}\{m_{\lambda }:\lambda ⊢n\}$. We do induction on the order of the element. Take the greatest element $x_1^{n_1}\cdots x_m^{n_m}$ in lexicographic order with $\mu =(n_1,\cdots ,n_m)$. Then $f-m_{\mu }\in {\Lambda }_m^n$ and $f-m_{\mu }<f$. By induction, $f$ can be written as linear combination of $\{m_{\lambda }:\lambda ⊢n\}$.

To show $s_{\lambda }$ form a basis, define $A_m$ as the space of skew-symmetric polynomials in $x_1,\cdots ,x_m$. We say $g$ is skew-symmetric if $(ij)g=-g$. It is easy to see that any skew-symmetric polynomials is divisible by ${\prod }_{1⩽i<j⩽m}(x_i-x_j)$. We have that $\phi :{\Lambda }_m\to A_m,f\mapsto f{\prod }_{1⩽i<j⩽m}(x_i-x_j)$, where $\phi$ defines an isomorphism between ${\Lambda }_m$ and $A_m$. One can check that basis of $A_m$ can be given by

$$b_{\lambda }=\left|\begin{array}{ccc}{x}_1^{{\lambda }_1+m-1}& \cdots & x_m^{{\lambda }_1+m-1}\\ x_1^{{\lambda }_2+m-2}& \cdots & x_m^{{\lambda }_2+m-2}\\ ⋮& & ⋮\\ x_1^{{\lambda }_m}& \cdots & x_m^{{\lambda }_m}\end{array}\right|$$

where $\lambda$ runs over through partitions of $n$ of length $⩽m$. Notice that $s_{\lambda }=b_{\lambda }/{\prod }_{1⩽i<j⩽m}(x_i-x_j)$ and $\phi (s_{\lambda })=b_{\lambda }$. Furthermore, as $\dim {\Lambda }_m^n=\dim A_m^{n+\left(\genfrac{}{}{0ex}{}{m}{2}\right)}$, it deduces that $s_{\lambda }$ form a basis. Moreover, recall that ^i3a31d and similarly we have $s_{\mu }={\sum }_{\lambda }{\kappa }_{\mu \lambda }{m}_{\lambda }=m_{\mu }+{\sum }_{\lambda \ne \mu }{\kappa }_{\mu \lambda }{m}_{\lambda }$, and it yields that $⟨s_{\mu }:\mu ⊢n⟩=⟨m_{\mu }:\mu ⊢n⟩={\Lambda }_m^n$.

To show $e_{{\lambda }^{\prime }}$ form a basis, suppose that $\lambda ⊢n$ with $\lambda =({\lambda }_1,\cdots ,{\lambda }_k)$ and ${\lambda }^{\prime }=({\rho }_1,\cdots ,{\rho }_k)$, and then

$$e_{{\lambda }^{\prime }}=e_{{\rho }_1}\cdots e_{{\rho }_k}=(x_1\cdots x_{{\rho }_1}+\cdots )(x_1\cdots x_{{\rho }_2}+\cdots )\cdots (x_1\cdots x_{{\rho }_k}+\cdots )=x_1^{{\lambda }_1}\cdots x_m^{{\lambda }_m}+\cdots +\text{mbox}smallerterms=m_{\lambda }+\sum _{\mu ⊲\lambda }{m}_{\mu }.$$

For $h_{\lambda }$, we can do it by ^jrsjoc, as it deduces that $⟨s_{\lambda }:\lambda ⊢n⟩\subseteq ⟨h_{\lambda }:\lambda ⊢n⟩$. \end{proof}

Definition

For each $m$ we have

$${\Lambda }_{m+1}\to {\Lambda }_m,f(x_1,\cdots ,x_m,x_{m+1})\mapsto f(x_1,\cdots ,x_m,0)$$

Define a projective limit algebra $\Lambda ={\oplus }_{n⩾0}{\Lambda }^n$ where $f=(f_m:m⩾0)$ is a sequence of $f_m\in {\Lambda }_m^n$ and $f_{m+1}\mapsto f_m$ for all $m⩾0$.

Then $f$ is a formal series in infinitely many variables, and there are several examples:

• $p_n={\sum }_{i=1}^{\infty }{x}_i^n$
• $e_n={\sum }_{1⩽i_1<\cdots <i_n}{x}_{i_1}\cdots x_{i_n}$
• $h_n={\sum }_{1⩽i_1⩽\cdots ⩽i_n}{x}_{i_1}\cdots x_{i_n}$

For more details of projective limit, see page 489 of Algebra chapter 0 - 2009 - Aluffi.pdf. The sequence of Schur polynomials $s_{\lambda }$ defines Schur functions, and the sequence of $m_{\lambda }$ defines the monomial symmetric functions.

Lemma

We have

$$h_n=\sum _{\lambda ⊢n}\frac{p_{\lambda }}{z_{\lambda }}\text{mbox}and{e}_n=\sum _{\lambda ⊢n}\frac{{ϵ}_{\lambda }{p}_{\lambda }}{z_{\lambda }}$$

where $\lambda =(1^{m_1},\cdots ,n^{m_n})$, $z_{\lambda }=1^{m_1}{m}_1!\cdots n^{m_n}{m}_n!$ and ${ϵ}_{\lambda }=(-1{)}^{n-\ell (\lambda )}$.

\begin{proof} Recall that

P(t)=d/dt\ln(H(t))=\frac{H'(t)}{H(t)}.

Link to original

It follows

$$H(t)=\exp (\sum _{k=1}^{\infty }\frac{p_k{t}^k}{k})=\prod _{k=1}^{\infty }\exp (\frac{p_k{t}^k}{k})=\left(1+p_{1}t+\frac{(p_{1}t{)}^2}{2!}+\cdots \right)\left(1+\frac{p_{2}t}{2}+\frac{(p_{1}t{)}^2}{2^2\cdot 2!}+\cdots \right)\left(1+\frac{p_{3}t}{3}+\frac{(p_{3}t{)}^2}{3^2\cdot 2!}+\cdots \right)$$

and it deduces what we desire. Similarly we can prove $e_n={\sum }_{\lambda ⊢n}{ϵ}_{\lambda }{p}_{\lambda }/z_{\lambda }$. \end{proof}

orthogonal properties

For two families of variables $x=(x_1,\cdots ,x_k,\cdots )$ and $y=(y_1,\cdots ,y_k,\cdots )$, we have the following properties

$$\begin{array}{rl}\prod _{i,j⩾1}(1-x_i{y}_j{)}^{-1}& =\sum _{\lambda }{z}_{\lambda }^{-1}{p}_{\lambda }(x)p_{\lambda }(y),\\ \prod _{i,j⩾1}(1-x_i{y}_j{)}^{-1}& =\sum _{\lambda }{h}_{\lambda }(x)m_{\lambda }(y)=\sum _{\lambda }{m}_{\lambda }(x)h_{\lambda }(y)=\sum _{\lambda }{s}_{\lambda }(x)s_{\lambda }(y).\end{array}$$

\begin{proof} By ^dbe3dc, we have

$$\prod _{i⩾1}(1-x_{i}t{)}^{-1}=\sum _{\lambda }{z}_{\lambda }^{-1}{p}_{\lambda }{t}^{|\lambda |}\text{\hspace{1em}(*)}$$

where $|\lambda |$ is the length of $\lambda$.

Note that ${\sum }_{i,j}(x_i{y}_j{)}^k=p_k(x)p_k(y)$. Use $(\ast )$ for $x_i{y}_j$ and set $t=1$, we have

$$\prod _{i,j⩾1}(1-x_i{y}_j{)}^{-1}=\sum _{\lambda }{z}_{\lambda }^{-1}{p}_{\lambda }(x_i{y}_j)=\sum _{\lambda }{z}_{\lambda }^{-1}{p}_{\lambda }(x_i)p_{\lambda }(y_j).$$

Equip $\Lambda$ with the following form $⟨h_{\lambda },m_{\mu }⟩={\delta }_{\lambda \mu }$, and it deduces that $⟨p_{\lambda },p_{\mu }⟩=z_{\lambda }{\delta }_{\lambda \mu }$ and $⟨s_{\lambda },s_{\mu }⟩={\delta }_{\lambda \mu }$. With respect to this inner product, $\{s_{\lambda }:\lambda ⊢n\}$ is orthonormal basis of ${\Lambda }^n$. \end{proof}