# Algebra/Chapter 10/Symmetric Polynomials/Permutations and Symmetry
## Definition 1

A permutation is a bijective function from a set to itself.
Let $X={\bigl \X_{1},\ldots ,X_{n}{\bigr \}}$ 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\leq i\leq n$ there exists a unique $1\leq j\leq 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={\bigl \1,2,3{\bigr \}}$ there are $3!=6$ different permutations:
    ${\begin{aligned}&\sigma _{1}={\begin{bmatrix}1&2&3\\1&2&3\end{bmatrix}},\quad \sigma _{2}={\begin{bmatrix}1&2&3\\1&3&2\end{bmatrix}}\\[5pt]&\sigma _{3}={\begin{bmatrix}1&2&3\\2&1&3\end{bmatrix}},\quad \sigma _{4}={\begin{bmatrix}1&2&3\\2&3&1\end{bmatrix}}\\[5pt]&\sigma _{5}={\begin{bmatrix}1&2&3\\3&1&2\end{bmatrix}},\quad \sigma _{6}={\begin{bmatrix}1&2&3\\3&2&1\end{bmatrix}}\end{aligned}}$
In general, if $|X|=n$ then $|S_{X}|=n!=1\cdot 2\cdots n$.

## Definition 2

Let $F({\vec {X}}^{n})$ be a polynomial. Let us define:
    $\sigma (F):=F(X_{\sigma (1)},\ldots ,X_{\sigma (n)})$

### Properties

Let $F({\vec {X}}^{n}),G({\vec {X}}^{n})$ be polynomials. Then we have:
* $\sigma (cF)=c\,\sigma (F)$ such that $c\in \mathbb {R}$.
* $\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{aligned}F&=a\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}\\[5pt]G&=b\,X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}}\\[5pt]\sigma (F\pm G)&=\sigma {\bigla\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}\!\pm b\,X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}}{\bigl )}\\[5pt]&=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}}\\[5pt]&=\sigma {\bigla\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}{\bigl )}\pm \sigma {\biglb\,X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}}{\bigl )}\\[5pt]&=\sigma (F)\pm \sigma (G)\end{aligned}}$
    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{aligned}F&=a\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}\\[5pt]G&=b\,X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}}\\[5pt]\sigma (F\cdot G)&=\sigma {\bigla\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}\!\cdot b\,X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}}{\bigl )}\\[5pt]&=ab\,\sigma {\biglX_{1}^{a_{1}+b_{1}}\!\cdots X_{n}^{a_{n}+b_{n}}{\bigl )}\\[5pt]&=ab\,X_{\sigma (1)}^{a_{1}+b_{1}}\!\cdots X_{\sigma (n)}^{a_{n}+b_{n}}\\[5pt]&={\bigla\,X_{\sigma (1)}^{a_{1}}\!\cdots X_{\sigma (n)}^{a_{n}}{\bigr )}\cdot {\biglb\,X_{\sigma (1)}^{b_{1}}\!\cdots X_{\sigma (n)}^{b_{n}}{\bigr )}\\[5pt]&=\sigma {\bigla\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}{\bigl )}\cdot \sigma {\biglb\,X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}}{\bigl )}\\[5pt]&=\sigma (F)\cdot \sigma (G)\end{aligned}}$
    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{aligned}\sigma (F\cdot G)&=\sigma {\bigg\sum _{i_{1}\,=\,1}^{k_{1}}F_{i_{1}}\cdot \sum _{i_{2}\,=\,1}^{k_{2}}G_{i_{2}}{\bigg )}\\[5pt]&=\sigma {\bigg\sum _{i_{1}\,=\,1}^{k_{1}}\sum _{i_{2}\,=\,1}^{k_{2}}F_{i_{1}}G_{i_{2}}{\bigg )}\\[5pt]&=\sum _{i_{1}\,=\,1}^{k_{1}}\sum _{i_{2}\,=\,1}^{k_{2}}\sigma (F_{i_{1}}\!\cdot G_{i_{2}})\\[5pt]&=\sum _{i_{1}\,=\,1}^{k_{1}}\sum _{i_{2}\,=\,1}^{k_{2}}\sigma (F_{i_{1}})\cdot \sigma (G_{i_{2}})\\[5pt]&=\sum _{i_{1}\,=\,1}^{k_{1}}\sigma (F_{i_{1}})\cdot \sum _{i_{2}\,=\,1}^{k_{2}}\sigma (G_{i_{2}})\\&=\sigma {\bigg\sum _{i_{1}\,=\,1}^{k_{1}}F_{i_{1}}{\bigg )}\cdot \sigma {\bigg\sum _{i_{2}\,=\,1}^{k_{2}}G_{i_{2}}{\bigg )}\\[5pt]&=\sigma (F)\cdot \sigma (G)\end{aligned}}$
* By definition we get:
       ${\begin{aligned}(\sigma _{1}\circ \sigma _{2})(F)&=F{\biglX_{(\sigma _{1}\,\circ \,\sigma _{2})(1)},\ldots ,X_{(\sigma _{1}\,\circ \,\sigma _{2})(n)}{\bigr )}\\[5pt]&=F{\biglX_{\sigma _{1}(\sigma _{2}(1))},\ldots ,X_{\sigma _{1}(\sigma _{2}(n))}{\bigr )}\\[5pt]&=\sigma _{1}{\biglF(X_{\sigma _{2}(1)},\ldots ,X_{\sigma _{2}(n)}){\bigr )}\\[5pt]&=\sigma _{1}(\sigma _{2}(F))\end{aligned}}$

## Definition 3

Let $P({\vec {X}}^{n})$ be a polynomial. Then it is called symmetric if
    $\sigma (P)=P$
for all permutations $\sigma :\{1,\ldots ,n\}\to \{1,\ldots ,n\}$.

### Examples

* A symmetric polynomial:
       ${\begin{aligned}P({\color {red}x_{1}},{\color {Green}x_{2}},{\color {blue}x_{3}})&={\color {red}x_{1}^{2}}{\color {Green}x_{2}^{2}}{\color {blue}x_{3}^{2}}+{\color {red}3x_{1}}+{\color {Green}3x_{2}}+{\color {blue}3x_{3}}\\[5pt]&={\color {red}x_{1}^{2}}{\color {blue}x_{3}^{2}}{\color {Green}x_{2}^{2}}+{\color {red}3x_{1}}+{\color {blue}3x_{3}}+{\color {Green}3x_{2}}\\[5pt]&={\color {Green}x_{2}^{2}}{\color {red}x_{1}^{2}}{\color {blue}x_{3}^{2}}+{\color {Green}3x_{2}}+{\color {red}3x_{1}}+{\color {blue}3x_{3}}\\[5pt]&={\color {Green}x_{2}^{2}}{\color {blue}x_{3}^{2}}{\color {red}x_{1}^{2}}+{\color {Green}3x_{2}}+{\color {blue}3x_{3}}+{\color {red}3x_{1}}\\[5pt]&={\color {blue}x_{3}^{2}}{\color {red}x_{1}^{2}}{\color {Green}x_{2}^{2}}+{\color {blue}3x_{3}}+{\color {red}3x_{1}}+{\color {Green}3x_{2}}\\[5pt]&={\color {blue}x_{3}^{2}}{\color {Green}x_{2}^{2}}{\color {red}x_{1}^{2}}+{\color {blue}3x_{3}}+{\color {Green}3x_{2}}+{\color {red}3x_{1}}\end{aligned}}$
* A non-symmetric polynomial:
       ${\begin{aligned}P({\color {red}x_{1}},{\color {Green}x_{2}},{\color {blue}x_{3}})&={\color {red}x_{1}}+{\color {Green}x_{2}}-{\color {blue}x_{3}}\\[5pt]&\neq {\color {red}x_{1}}+{\color {blue}x_{3}}-{\color {Green}x_{2}}\\[5pt]&\neq {\color {Green}x_{2}}+{\color {red}x_{1}}-{\color {blue}x_{3}}\\[5pt]&\neq {\color {Green}x_{2}}+{\color {blue}x_{3}}-{\color {red}x_{1}}\\[5pt]&\neq {\color {blue}x_{3}}+{\color {red}x_{1}}-{\color {Green}x_{2}}\\[5pt]&\neq {\color {blue}x_{3}}+{\color {Green}x_{2}}-{\color {red}x_{1}}\end{aligned}}$

### Properties

* The sum and product of symmetric polynomials is a symmetric polynomial.
* Let $F$ be a polynomial in variables $Y_{1},\ldots ,Y_{m}$, and let $G_{1},\ldots ,G_{m}$ be symmetric polynomials in variables $X_{1},\ldots ,X_{n}$.
    Then $F({\vec {G}}^{m}({\vec {X}}^{n}))$ is also symmetric in variables $X_{1},\ldots ,X_{n}$.

#### Proof

* This follows from the properties in definition 2 and the symmetric polynomial definition above.
* By definition we get:
    ${\begin{aligned}\sigma {\biglF({\vec {G}}^{m}({\vec {X}}^{n})){\bigr )}&=\sigma {\biglF(G_{1}({\vec {X}}^{n}),\ldots ,G_{m}({\vec {X}}^{n})){\bigr )}\\[5pt]&=F{\bigl\sigma (G_{1}({\vec {X}}^{n})),\ldots ,\sigma (G_{m}({\vec {X}}^{n})){\bigr )}\\[5pt]&=F{\biglG_{1}({\vec {X}}^{n}),\ldots ,G_{m}({\vec {X}}^{n}){\bigr )}\\[5pt]&=F({\vec {G}}^{m}({\vec {X}}^{n}))\end{aligned}}$
| ←Monomial Ordering | Permutations and Symmetry | Elementary Symmetric Polynomials→ |