Symmetric functions

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 04 March 2012

Symmetric functions

The symmetric group $S_n$ acts on the vector space $${\mathbb{Z}}^n=\mathbb{Z}-\mathrm{span}\{x_1,...,x_n\}byw{x}_i=x_{w\left(i\right)},$$ for $w\in S_n, 1\le i\le n.$ This action induces an action of $S_n$ on the polynomial ring $\mathbb{Z}\left[X_n\right]=\mathbb{Z}[x_1,...,x_n]$ by ring automorphisms. For a seq uence $\gamma =({\gamma }_1,...,{\gamma }_n)$ of non-negative integers let $$x^{\gamma }={x_1}^{{\gamma }_1}\cdots {x_n}^{{\gamma }_n},so\; that\mathbb{Z}[x_1,...,x_n]=\mathbb{Z}-\mathrm{span}\left\{x^{\gamma } \right| \gamma \in {\mathbb{Z}}_{\ge 0}^n\}.$$ The ring of symmetric functions is $$\begin{array}{ll}\mathbb{Z}{\left[X_n\right]}^{S_n}=\{f\in \mathbb{Z}\left[X_n\right] | wf=f for\; all\; w\in S_n\}.& (Sf\; 1.1)\end{array}$$ Define the orbit sums, or monomial symmetric functions, by $$m_{\lambda }=\sum _{\gamma \in S_n\lambda }{x}^{\gamma },for\; \lambda \in {\mathbb{Z}}_{\ge 0}^n,$$ where $S_n\lambda$ is the orbit of $\lambda$ under the action of $S_n.$ Let $$\begin{array}{ll}{P}^{+}=\{\lambda ={\lambda }_1,...,{\lambda }_n)\in {\mathbb{Z}}_{\ge 0}^n | {\lambda }_1\ge \cdots \ge {\lambda }_n\}& (Sf\; 1.2)\end{array}$$ so that $$\begin{array}{ll}\left\{m_{\lambda } \right| \lambda \in P^{+}\}is\; a\; \mathbb{Z}-basis\; of\; \mathbb{Z}{\left[X_n\right]}^{S_n}.& (Sf\; 1.3)\end{array}$$

Partitions

A partition is a collection $\mu$ of boxes in a corner where the convention is that gravity goes up and to the left. As for matrices, the rows and columns of $\mu$ are indexed from top to bottom and left to right, respectively. $$\begin{array}{lll}The\; \mathit{\text{parts}} \; of\; \mu \; are& {\mu }_i=\left(the\; number\; of\; boxes\; in\; row\; i of \mu \right),& \\ the\; \mathit{\text{length}} \; of\; \mu \; is& l\left(\mu \right)=\left(the\; number\; of\; rows\; of \mu \right),& (Sf\; 1.4)\\ the\; \mathit{\text{size}} \; of\; \mu \; is& \left|\mu \right|={\mu }_1+\cdots +{\mu }_{l\left(\mu \right)}=\left(the\; number\; of\; boxes\; of \mu \right).& \end{array}$$ Then $\mu$ is determined by (and identified with) the sequence $\mu =({\mu }_1,...,{\mu }_l)$ of positive integers such that ${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_l>0,$ where $l=l\left(\mu \right).$ For example, $$(5,5,3,3,1,1)=\begin{array}{c}\\ \end{array}.$$ A partition of k is a partition $\lambda$ with $k$ boxes. Write $\lambda \&rline;k$ if $\lambda$ is a partition of $k.$ Make the convention that ${\lambda }_i=0$ if $i>l\left(\lambda \right).$ The dominance order is the partial order on the set of partitions of $k,$ $$P^{+}\left(k\right)=\left\{partitions\; of\; k\right\}=\{\lambda =({\lambda }_1,...,{\lambda }_l) | {\lambda }_1\ge \cdots \ge {\lambda }_l>0, {\lambda }_1+\cdots +{\lambda }_l=k\},$$ given by $$\lambda \ge \mu if{\lambda }_1+{\lambda }_2+\cdots +{\lambda }_i\ge {\mu }_1+{\mu }_2+\cdots +{\mu }_{i}for\; all\; 1\le i\le \max \{l\left(\lambda \right),l\left(\mu \right)\}.$$ PUT THE PICTURE OF THE HASSE DIAGRAM FOR $k=6$ HERE.

Tableaux

Let $\lambda$ be a partition and let $\mu =({\mu }_1,...,{\mu }_n)\in {\mathbb{Z}}_{\ge 0}^n$ be a sequence of nonnegative integers. A column strict tableau of shape $\lambda$ and weight $\mu$ is a filling of the boxes of $\lambda$ with ${\mu }_1$ 1s, ${\mu }_2$ 2s, ... , ${\mu }_n$ $ns$, such that

1. the rows are weakly increasing from left to right,
2. the columns are strictly increasing from top to bottom.

If $p$ is a column strict tableau write $\mathrm{shp}\left(p\right)$ and $\mathrm{wt}\left(p\right)$ for the shape and the weight of $p$ so that $$\begin{array}{rcl}\mathrm{shp}\left(p\right)=({\lambda }_1,...,{\lambda }_n),& where& {\lambda }_i= \; number\; of\; boxes\; in\; row\; i \; of\; p, \; and\\ \mathrm{wt}\left(p\right)=({\mu }_1,...,{\mu }_n),& where& {\mu }_i= \; number\; of\; is \; in\; p.\end{array}$$ For example, $$p=\begin{array}{c} 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 4 3 3 3 4 4 4 5 4 5 5 6 6 7 7 \end{array}has\begin{array}{rcl}\mathrm{shp}\left(p\right)& =& (9,7,7,4,2,1,0)and\\ \mathrm{wt}\left(p\right)& =& (7,6,5,5,3,2,2).\end{array}$$ For a partition $\lambda$ and a sequence $\mu =({\mu }_1,...{\mu }_n)\in {\mathbb{Z}}_{\ge 0}$ of nonnegative integers write $$\begin{array}{ll}\begin{array}{rcl}B\left(\lambda \right)& =& \left\{column\; strict\; tableaux\; p \right| \mathrm{shp}\left(p\right)=\lambda \},\\ {B\left(\lambda \right)}_{\mu }& =& \left\{column\; strict\; tableaux\; p \right| \mathrm{shp}\left(p\right)=\lambda \; and\; \mathrm{wt}\left(p\right)=\mu \}.\end{array}& (Sf\; 1.5)\end{array}$$

Elementary symmetric functions

Define symmetric functions $e_r,$ $0\le r\le n,$ via the generating function $$\prod _{i=1}^n(1-x_{i}z)=\sum _{r=0}^n{(-1)}^r{e}_r{z}^r.$$ Then $e_0=1$ and, for $0\le r\le n,$ $$e_r=m_{\left(1^r\right)}=\sum _{1\le i_1<i_2<\cdots <i_r\le n}{x}_{i_1}{x}_{i_2}\cdots x_{i_r}=\sum _{\mathrm{shp}\left(p\right)=\left(1^r\right)}{x}^{\mathrm{wt}\left(p\right)},$$ where the last sum is over all column strict tableaux $p$ of shape $\left(1^r\right).$

If $f\left(t\right)$ is a polynomial in $t$ with roots ${\gamma }_1,...,{\gamma }_n$ then $$the\; coefficient\; of\; t^r \; in\; f\left(t\right) \; is\; {(-1)}^{n-r}{e}_r({\gamma }_1,...,{\gamma }_n).$$ If $A$ is an $n\times n$ matrix with entries in $𝔽$ with eigenvalues ${\gamma }_1,...,{\gamma }_n$ then the trace of the action of $A$ on the $r^{\mathrm{th}}$ exterior power of the vector space ${𝔽}^n$ is $$\mathrm{tr}(A,{\wedge }^r{𝔽}^n)=e_r({\gamma }_1,...,{\gamma }_n), \; so\; that\; \mathrm{Tr}\left(A\right)=e_1({\gamma }_1,...,{\gamma }_n),\det \left(A\right)=e_n({\gamma }_1,...,{\gamma }_n),$$ and the characteristic polynomials of $A$ is $${\mathrm{char}}_t\left(A\right)=\sum _{r=0}^n{(-1)}^{n-r}{e}_{n-r}({\gamma }_1,...,{\gamma }_n)t^r.$$

Let $\gamma =({\gamma }_1,...,{\gamma }_n)$ be a partition. Then $$e_{\lambda \text{'}}=\sum _{\mu \le \lambda }{a}_{\lambda \text{'}\mu }{m}_{\mu },$$ where $a_{\lambda \text{'}\mu }$ is the number of matrices with entries from $\{0,1\}$ with row sums $\lambda \text{'}$ and column sums $\mu .$ Furthermore, $a_{\lambda \text{'}\lambda }=1$ and $a_{\lambda \text{'}\mu }=0$ unless $\mu \le \lambda .$

		Proof.
	If $A$ is an $l\times n$ matrix with entries from $\{0,1\}$ let $$x^A=\prod _{i=1}^n{\left(x_i\right)}^{a_{ij}}$$ and define $$\begin{array}{rcl}\mathrm{rs}\left(A\right)& =& ({\rho }_1,...,{\rho }_n),\\ \mathrm{cs}\left(A\right)& =& ({\gamma }_1,...,{\gamma }_n),\end{array}where{\rho }_i=\sum _{j=1}^l{a}_{ij} and {\gamma }_j=\sum _{i=1}^n{a}_{ij},$$ so that $rs\left(A\right)$ and $cs\left(A\right)$ are the sequences of row sums and column sums of $A$, respectively. If $\lambda \text{'}=({\lambda }_1\text{'},...,{\lambda }_l\text{'})$ then $$e_{\lambda \text{'}}=\prod _{j=1}^l{e}_{{\lambda }_j\text{'}}=\sum _{rs\left(A\right)=\lambda \text{'}}{x}^A=\sum _{\gamma \in {\mathbb{Z}}_{\ge 0}^n}\sum _{\genfrac{}{}{0ex}{}{rs\left(A\right)=\lambda \text{'}}{cs\left(A\right)=\gamma }}{x}^{\gamma }=\sum _{\mu }{a}_{\lambda \text{'}\mu }{m}_{\mu }.$$ Since there is a unique matrix $A$ with $rs\left(A\right)=\lambda \text{'}$ and $cs\left(A\right)=\lambda , a_{\lambda \text{'}\lambda }=1.$ If $A$ is a $0,1$ matrix with $rs\left(A\right)=\lambda \text{'}$ and $cs\left(A\right)=mu$ then ${\mu }_1+\cdots +{\mu }_i\le {\lambda }_1+\cdots +{\lambda }_i$ since there are at most ${\lambda }_1+\cdots +{\lambda }_i$ nonzero entries in the first $i$ columns of $A.$ Thus $a_{\lambda \text{'}\mu }=0$ unless $\mu \le \lambda .$ $\square$

1. The set $\left\{e_{\lambda } \right| l\left(\lambda \text{'}\right)\le n\}$ is a basis of $\mathbb{Z}{\left[X_n\right]}^{S_n}.$
2. $\mathbb{Z}{\left[X_n\right]}^{S_n}=\mathbb{Z}[e_1,...,e_n].$

Complete symmetric functions

Define symmetric functions $h_r$, $r\in {\mathbb{Z}}_{\ge 0},$ via the generating function $$\prod _{i=1}^n\frac{1}{1-x_{i}z}=\sum _{r\in {\mathbb{Z}}_{\ge 0}}{h}_r{z}^r.$$ Then $h_0=1$ and, for $r\in {\mathbb{Z}}_{>0},$ $$h_r=\sum _{\lambda ⊢r}{m}_{\lambda }=\sum _{1\le i_1\le i_2\le \cdots \le i_r\le n}{x}_{i_1}{x}_{i_2}\cdots x_{i_r}=\sum _{\mathrm{sh}\left(p\right)=\left(r\right)}{x}^{\mathrm{wt}\left(p\right)},$$ where the last sum is over all column strict tableaux $p$ of shape $\left(r\right).$

There is an involutive automorphism $\omega$ of $\mathbb{Z}{\left[X_n\right]}^{S_n}$ defined by $$\begin{array}{rrcl}\omega :& \mathbb{Z}{\left[X_n\right]}^{S_n}& \to & \mathbb{Z}{\left[X_n\right]}^{S_n}\\ & e_k& \mapsto & h_k\end{array}$$

		Proof.
	Comparing coefficients of $z^k$ on each side of $$1=\left(\prod _{i=1}^n(1-x_{i}z)\right)\left(\prod _{i=1}^n\frac{1}{1-x_{i}z}\right)yields0=\sum _{r=1}^k{(-1)}^r{e}_r{h}_{n-r}.$$ $\square$

1. The set $\left\{h_{\lambda } \right| l\left(\lambda \text{'}\right)\le n\}$ is a basis of $\mathbb{Z}{\left[X_n\right]}^{S_n}.$
2. $\mathbb{Z}{\left[X_n\right]}^{S_n}=\mathbb{Z}[h_1,...,h_n].$

The monomials in $\{x_1^{{\epsilon }_1}{x}_2^{{\epsilon }_2}\cdots x_n^{{\epsilon }_n} | 0\le {\epsilon }_i\le n-i\}$ form a basis of $\mathbb{Z}[x_1,...,x_n]$ as a ${\mathbb{Z}[x_1,...,x_n]}^{S_n}$ module.

		Proof.
	Let $I=⟨e_1,...,e_n⟩$ be the ideal in $\mathbb{Z}[x_1,...,x_n]$ generated by $e_1,...,e_n.$ Since $(1-x_{1}t)\cdots (1-x_{n}t)=0 \mathrm{mod}I,$ $$(1-x_{i-1}t)\cdots (1-x_{n}t)=\frac{1}{(1-x_{1}t)\cdots (1-x_{i}t)} \mathrm{mod}I,$$ and so $$\sum _{r=0}^{n-i}{(-1)}^r{e}_r(x_{i+1},...,x_n)t^r=\sum _{l\ge 0}{h}_l(x_1,...,x_i)t^l\mathrm{mod}I.$$ Comparing coefficients of $t^{n-i+1}$ on each side gives that, for all $1\le i\le n,$ $$0=h_{n-i+1}(x_1,...,x_i)=\sum _{r=0}^{n-i+1}{x}^{n-i+1-r}{h}_r(x_1,...,x_{i-1})\mathrm{mod}I,$$ and thus $$\begin{array}{ll}{x}_i^{n-i+1}=-\sum _{r=1}^{n-i+1}{x}^{n-i+1-r}{h}_r(x_1,...,x_{i-1})\mathrm{mod}I.& (Sf\; 1.11)\end{array}$$ This identity shows (by induction on $i$) that $x_i^{n-i+1}$ can be rewritten, $\mathrm{mod}I,$ as a linear combination of monomials in $x_1,...,x_i$ with the exponent of $x_i$ being $\le n-i.$ In particular, $$0=h_{n-1+1}\left(x_1\right)=x_1^n \mathrm{mod}I$$ and it follows that any polynomial can be written, $\mathrm{mod}I,$ as a linear combination of monomials $$\begin{array}{ll}{x}_1^{{\epsilon }_1}{x}_2^{{\epsilon }_2}\cdots x_n^{{\epsilon }_n}with0\le {\epsilon }_i\le n-i.& (Sf\; 1.12)\end{array}$$ If $S^k$ is the set of homogeneous degree $k$ polynomials in $S=\mathbb{Z}[x_1,...,x_n]$ and ${\left(S^W\right)}^k$ is the set of homogeneous degree $k$ polynomials in $S^W=\mathbb{Z}[e_1,...,e_n]=\mathbb{Z}{[x_1,...,x_n]}^{S_n}$ the Poincaré series of $S$ and $S^W$ are $$\frac{1}{{(1-t)}^n}=\sum _{k\ge 0}\dim \left(S^k\right)t^{k}and\prod _{i=1}^n\left(\frac{1}{1-t^i}\right)=\sum _{k\ge 0}\dim \left({\left(S^W\right)}^k\right)t^k.$$ Then the Poincaré series of $S/I$ is $$\prod _{i=1}^n\frac{1-t^i}{1-t}=\left[n\right]!=1\cdot (1+t)\cdots (1+t+\cdots +t^{n-1}).$$ There are $n(n-1)\cdots 2\cdot 1=n!$ monomials in (???) and thus the monomials in (*) form a basis of $S$ as an $S^W$ module. The relations (???) provide a way to expand any polynomial in terms of this basis (with coefficients in $S^W$). $\square$

The groups $G_{r,p,n}$

Let $r$ and $n$ be positive integers. The group $G_{r,1,n}$ is the group of $n\times n$ matrices with

1. exactly one non zero entry in each row and each column,
2. the nonzero entries are $r^{\mathrm{th}}$ roots of 1.

Let $p$ be a positive integer (not necessarily prime) such that $p$ divides $r.$ The group $G_{r,p,n}$ is defined by the exact sequence $$\left\{1\right\}\to G_{r,p,n}\to G_{r,1,n}\stackrel{\phi }{\to }\mathbb{Z}/p\mathbb{Z}\to \left\{1\right\},where\phi \left(g\right)={\left(\prod _{g_{ij}\ne 0}{g}_{ij}\right)}^p$$ is the $p^{\mathrm{th}}$ power of the product of the nonzero entries of $g,$ and $\mathbb{Z}/p\mathbb{Z}$ is identified with the group of $p^{\mathrm{th}}$ roots of unity. Thus $G_{r,p,n}=\ker \phi$ is a normal subgroup of $G_{r,1,n}$ of index $p.$ Examples are

1. $G_{1,1,n}=S_n=W{A}_{n-1}$ is the symmetric group (the Weyl group of type $A_{n-1}$),
2. $G_{2,1,n}=O_n\left(\mathbb{Z}\right)=W{B}_n$ is the hyperoctahedral group of orthogonal matrices with entries in $\mathbb{Z}$ (the Weyl group of type $B_n$),
3. $G_{2,2,n}=W{D}_n$ is the group of signed permutations with an even number of negative signs (the Weyl group of type $D_n$),
4. $G_{r,1,1}=\mathbb{Z}/r\mathbb{Z}$ is the cyclic group of order $r$ of $r^{\mathrm{th}}$ roots of unity, and
5. $G_{r,r,2}=W{I}_2\left(r\right)$ is the dihedral group of order $2r.$

Let $\xi =e^{\frac{2\pi i}{r}}$ be the primitive $r^{\mathrm{th}}$ root of unity and let $𝔬=\mathbb{Z}\left[\xi \right].$ If $x_1,...,x_n$ is a basis of ${𝔬}^n$ then the natural action of $G_{r,p,n}$ extends uniquely to an action of $G_{r,p,n}$ on the polynomial ring $𝔬[x_1,...,x_n]$ by ring automorphisms. The invariant ring is $$𝔬{[x_1,...,x_n]}^{G_{r,p,n}}=\{f\in 𝔬[x_1,...,x_n] | wf=f \; for\; all\; w\in G_{r,p,n}\}.$$

Let $$\begin{array}{rcl}{f}_i(x_1,...,x_n)& =& e_i(x_1^r,...,x_n^r),for\; 1\le i\le n-1 \; and\\ f_n(x_1,...,x_n)& =& e_n(x_1^{\frac{r}{p}},...,x_n^{\frac{r}{p}}).\end{array}$$

1. $𝔬{[x_1,...,x_n]}^{G_{r,p,n}}=𝔬[f_1,...,f_n].$
2. $𝔬[x_1,...,x_n]$ is a free $𝔬{[x_1,...,x_n]}^{G_{r,p,n}}-module$ with basis $$\{x_1^{{\epsilon }_1}{x}_2^{{\epsilon }_2}\cdots x_n^{{\epsilon }_n} | 0\le {\epsilon }_1\le \frac{r}{p}-1 \; and\; 0\le {\epsilon }_1\le ir-1, \; for\; 2\le i\le n\}.$$

		Proof.
	To show: $f_1,...,f_n$ generate $𝔬{\left[X_n\right]}^W$ and they are algebraically independent. $\square$

Each element $w\in G_{r,1,n}$ can be written uniquely in the form $$w=t_1^{{\gamma }_1}\cdots t_n^{{\gamma }_n}\sigma ,where{t}_i=\mathrm{diag}(1,...,1,\xi ,1,...,1),\sigma \in S_n,0\le {\gamma }_i\le r-1,$$ so that $t_i$ is the diagonal matrix with 1s on the diagonal except for $\xi$ in the $i^{\mathrm{th}}$ diagonal entry. The element $w\in G_{r,p,n}if{\gamma }_1+\cdots +{\gamma }_n=0 \mathrm{mod}p,$ and thus $$G_{r,p,n}=\{w=t_1^{{\gamma }_1}\cdots t_n^{{\gamma }_n}\sigma | \sigma \in S_n, 0\le {\gamma }_n\le \frac{r}{p}-1, \; and\; 0\le {\gamma }_i\le r-1 \; for\; 1\le i\le n-1\}.$$ For each $w\in G_{r,p,n}$ define a monomial $$x_w=\left(\prod _{j=1}^n{(x_{\sigma \left(1\right)}\cdots x_{\sigma \left(j\right)})}^{{\gamma }_j}\right)\left(\prod _{\genfrac{}{}{0ex}{}{i \; such\; that}{\sigma \left(i\right)>\sigma (i+1)}}(x_{\sigma \left(1\right)}\cdots x_{\sigma \left(i\right)})\right).$$

The polynomial ring $𝔬[x_1,...,x_n]$ is a free $𝔬{[x_1,...,x_n]}^{G_{r,p,n}}-module$ with basis $$\left\{x_w \right| w\in G_{r,p,n}\}.$$

		Proof.
	$\square$

Notes and References

Taken from lecture notes on symmetric functions by Arun Ram.

References

References?

page history