Algebra/Chapter 10/Symmetric Polynomials/Permutations and Symmetry

Definition 1

A permutation is a bijective function from a set to itself.

Let $X=\{X_1,\dots ,X_n\}$ be a finite set. The function $\sigma :X\to X$ is called a permutation if and only if it is one-to-one and onto.

Meaning, for all $1\le i\le n$ there exists a unique $1\le j\le n$ such that $\sigma (X_i)=X_{\sigma (i)}=X_j$.

The set of all permutations of the elements of $X$ is denoted by $S_X$.

Example

For $X=\{1,2,3\}$ there are $3!=6$ different permutations:

$\begin{array}{cc}& {\sigma }_1=\left[\begin{array}{ccc}1& 2& 3\\ 1& 2& 3\end{array}\right],{\sigma }_2=\left[\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right]\\ & {\sigma }_3=\left[\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right],{\sigma }_4=\left[\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right]\\ & {\sigma }_5=\left[\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right],{\sigma }_6=\left[\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right]\end{array}$

In general, if $|X|=n$ then $|S_X|=n!=1\cdot 2\cdots n$.

Definition 2

Let $F(\overrightarrow{X}{}^n)$ be a polynomial. Let us define:

$\sigma (F):=F(X_{\sigma (1)},\dots ,X_{\sigma (n)})$

Properties

Let $F(\overrightarrow{X}{}^n),G(\overrightarrow{X}{}^n)$ be polynomials. Then we have:

• $\sigma (cF)=c\sigma (F)$ such that $c\in ℝ$.
• $\sigma (F\pm G)=\sigma (F)\pm \sigma (G)$
• $\sigma (F\cdot G)=\sigma (F)\cdot \sigma (G)$
• $({\sigma }_1\circ {\sigma }_2)(F)={\sigma }_1({\sigma }_2(F))$

Proof

• By definition, the permutation is applied on the variable indexes only.
• First, let $F,G$ be monomials of the form

$\begin{array}{cc}F& =a{X}_1^{a_1}\cdots X_n^{a_n}\\ G& =b{X}_1^{b_1}\cdots X_n^{b_n}\\ \sigma (F\pm G)& =\sigma (a{X}_1^{a_1}\cdots X_n^{a_n}\pm b{X}_1^{b_1}\cdots X_n^{b_n})\\ & =a{X}_{\sigma (1)}^{a_1}\cdots X_{\sigma (n)}^{a_n}\pm b{X}_{\sigma (1)}^{b_1}\cdots X_{\sigma (n)}^{b_n}\\ & =\sigma (a{X}_1^{a_1}\cdots X_n^{a_n})\pm \sigma (b{X}_1^{b_1}\cdots X_n^{b_n})\\ & =\sigma (F)\pm \sigma (G)\end{array}$

We can generalize by induction for $F=\sum _{i_1=1}^{k_1}{F}_{i_1},G=\sum _{i_2=1}^{k_2}{G}_{i_2}$, such that $F_{i_1},G_{i_2}$ are monomials.

• Same as before, let $F,G$ be monomials of the form

$\begin{array}{cc}F& =a{X}_1^{a_1}\cdots X_n^{a_n}\\ G& =b{X}_1^{b_1}\cdots X_n^{b_n}\\ \sigma (F\cdot G)& =\sigma (a{X}_1^{a_1}\cdots X_n^{a_n}\cdot b{X}_1^{b_1}\cdots X_n^{b_n})\\ & =ab\sigma (X_1^{a_1+b_1}\cdots X_n^{a_n+b_n})\\ & =ab{X}_{\sigma (1)}^{a_1+b_1}\cdots X_{\sigma (n)}^{a_n+b_n}\\ & =(a{X}_{\sigma (1)}^{a_1}\cdots X_{\sigma (n)}^{a_n})\cdot (b{X}_{\sigma (1)}^{b_1}\cdots X_{\sigma (n)}^{b_n})\\ & =\sigma (a{X}_1^{a_1}\cdots X_n^{a_n})\cdot \sigma (b{X}_1^{b_1}\cdots X_n^{b_n})\\ & =\sigma (F)\cdot \sigma (G)\end{array}$

Again, We can generalize by induction for $F=\sum _{i_1=1}^{k_1}{F}_{i_1},G=\sum _{i_2=1}^{k_2}{G}_{i_2}$, such that $F_{i_1},G_{i_2}$ are monomials:

$\begin{array}{cc}\sigma (F\cdot G)& =\sigma (\sum _{i_1=1}^{k_1}{F}_{i_1}\cdot \sum _{i_2=1}^{k_2}{G}_{i_2})\\ & =\sigma \left(\sum _{i_1=1}^{k_1}\sum _{i_2=1}^{k_2}{F}_{i_1}{G}_{i_2}\right)\\ & =\sum _{i_1=1}^{k_1}\sum _{i_2=1}^{k_2}\sigma (F_{i_1}\cdot G_{i_2})\\ & =\sum _{i_1=1}^{k_1}\sum _{i_2=1}^{k_2}\sigma (F_{i_1})\cdot \sigma (G_{i_2})\\ & =\sum _{i_1=1}^{k_1}\sigma (F_{i_1})\cdot \sum _{i_2=1}^{k_2}\sigma (G_{i_2})\\ & =\sigma \left(\sum _{i_1=1}^{k_1}{F}_{i_1}\right)\cdot \sigma \left(\sum _{i_2=1}^{k_2}{G}_{i_2}\right)\\ & =\sigma (F)\cdot \sigma (G)\end{array}$

• By definition we get:

$\begin{array}{cc}({\sigma }_1\circ {\sigma }_2)(F)& =F(X_{({\sigma }_1\circ {\sigma }_2)(1)},\dots ,X_{({\sigma }_1\circ {\sigma }_2)(n)})\\ & =F(X_{{\sigma }_1({\sigma }_2(1))},\dots ,X_{{\sigma }_1({\sigma }_2(n))})\\ & ={\sigma }_1(F(X_{{\sigma }_2(1)},\dots ,X_{{\sigma }_2(n)}))\\ & ={\sigma }_1({\sigma }_2(F))\end{array}$

Definition 3

Let $P(\overrightarrow{X}{}^n)$ be a polynomial. Then it is called symmetric if

$\sigma (P)=P$

for all permutations $\sigma :\{1,\dots ,n\}\to \{1,\dots ,n\}$.

Examples

• A symmetric polynomial:

$\begin{array}{cc}P(x_1,x_2,x_3)& =x_1^2{x}_2^2{x}_3^2+3x_1+3x_2+3x_3\\ & =x_1^2{x}_3^2{x}_2^2+3x_1+3x_3+3x_2\\ & =x_2^2{x}_1^2{x}_3^2+3x_2+3x_1+3x_3\\ & =x_2^2{x}_3^2{x}_1^2+3x_2+3x_3+3x_1\\ & =x_3^2{x}_1^2{x}_2^2+3x_3+3x_1+3x_2\\ & =x_3^2{x}_2^2{x}_1^2+3x_3+3x_2+3x_1\end{array}$

• A non-symmetric polynomial:

$\begin{array}{cc}P(x_1,x_2,x_3)& =x_1+x_2-x_3\\ & \ne x_1+x_3-x_2\\ & \ne x_2+x_1-x_3\\ & \ne x_2+x_3-x_1\\ & \ne x_3+x_1-x_2\\ & \ne x_3+x_2-x_1\end{array}$

Properties

• The sum and product of symmetric polynomials is a symmetric polynomial.
  
• Let $F$ be a polynomial in variables $Y_1,\dots ,Y_m$, and let $G_1,\dots ,G_m$ be symmetric polynomials in variables $X_1,\dots ,X_n$.

Then $F(\overrightarrow{G}{}^m(\overrightarrow{X}{}^n))$ is also symmetric in variables $X_1,\dots ,X_n$.

Proof

• This follows from the properties in definition 2 and the symmetric polynomial definition above.
• By definition we get:

$\begin{array}{cc}\sigma (F(\overrightarrow{G}{}^m(\overrightarrow{X}{}^n)))& =\sigma (F(G_1(\overrightarrow{X}{}^n),\dots ,G_m(\overrightarrow{X}{}^n)))\\ & =F(\sigma (G_1(\overrightarrow{X}{}^n)),\dots ,\sigma (G_m(\overrightarrow{X}{}^n)))\\ & =F(G_1(\overrightarrow{X}{}^n),\dots ,G_m(\overrightarrow{X}{}^n))\\ & =F(\overrightarrow{G}{}^m(\overrightarrow{X}{}^n))\end{array}$