A permutation is a bijective function from a set to itself.
Let
be a finite set. The function
is called a permutation if and only if it is one-to-one and onto.
Meaning, for all
there exists a unique
such that
.
The set of all permutations of the elements of
is denoted by
.
For
there are
different permutations:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab3de4604f4ef8315c4360c299b83945015adf6c)
In general, if
then
.
Let
be a polynomial. Let us define:
![{\displaystyle \sigma (F):=F(X_{\sigma (1)},\ldots ,X_{\sigma (n)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a86cd6c7b14189c26a222431cf52b7f0401ff66)
Let
be polynomials. Then we have:
such that
.
![{\displaystyle \sigma (F\pm G)=\sigma (F)\pm \sigma (G)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69e22b832bb1d4af150ee2aa734a86e029e1c930)
![{\displaystyle \sigma (F\cdot G)=\sigma (F)\cdot \sigma (G)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c49554146c618a8c743e421c317fddee310382c4)
![{\displaystyle (\sigma _{1}\circ \sigma _{2})(F)=\sigma _{1}(\sigma _{2}(F))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c7d4b24e9bc83ab82aaf1a768d20a47fa91a3e1)
- By definition, the permutation is applied on the variable indexes only.
- First, let
be monomials of the form
![{\displaystyle {\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 {\bigl (}a\,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 {\bigl (}a\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}{\bigl )}\pm \sigma {\bigl (}b\,X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}}{\bigl )}\\[5pt]&=\sigma (F)\pm \sigma (G)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8fc0a1831b719bc44b3795d1d87370fef0110475)
- We can generalize by induction for
, such that
are monomials.
- Same as before, let
be monomials of the form
![{\displaystyle {\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 {\bigl (}a\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}\cdot b\,X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}}{\bigl )}\\[5pt]&=ab\,\sigma {\bigl (}X_{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]&={\bigl (}a\,X_{\sigma (1)}^{a_{1}}\!\cdots X_{\sigma (n)}^{a_{n}}{\bigr )}\cdot {\bigl (}b\,X_{\sigma (1)}^{b_{1}}\!\cdots X_{\sigma (n)}^{b_{n}}{\bigr )}\\[5pt]&=\sigma {\bigl (}a\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}{\bigl )}\cdot \sigma {\bigl (}b\,X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}}{\bigl )}\\[5pt]&=\sigma (F)\cdot \sigma (G)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05e9ebc89eb7816cacaa25e63f089b4c73ff487a)
- Again, We can generalize by induction for
, such that
are monomials:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba125ff6b5150fe677961371e866483048352ec4)
![{\displaystyle {\begin{aligned}(\sigma _{1}\circ \sigma _{2})(F)&=F{\bigl (}X_{(\sigma _{1}\,\circ \,\sigma _{2})(1)},\ldots ,X_{(\sigma _{1}\,\circ \,\sigma _{2})(n)}{\bigr )}\\[5pt]&=F{\bigl (}X_{\sigma _{1}(\sigma _{2}(1))},\ldots ,X_{\sigma _{1}(\sigma _{2}(n))}{\bigr )}\\[5pt]&=\sigma _{1}{\bigl (}F(X_{\sigma _{2}(1)},\ldots ,X_{\sigma _{2}(n)}){\bigr )}\\[5pt]&=\sigma _{1}(\sigma _{2}(F))\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/710ec98971c6c6d524692bb58122efa3558cabc3)
Let
be a polynomial. Then it is called symmetric if
![{\displaystyle \sigma (P)=P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/906c73ddbacb51d76d69c423fdd2f22b904eca7c)
for all permutations
.
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac511dfb498833bb30d5c5fe4dc212410e32d1db)
- A non-symmetric polynomial:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b56adf83a86a80d88289d3bb0be503e6b984d900)
- The sum and product of symmetric polynomials is a symmetric polynomial.
- Let
be a polynomial in variables
, and let
be symmetric polynomials in variables
.
- Then
is also symmetric in variables
.
- This follows from the properties in definition 2 and the symmetric polynomial definition above.
- By definition we get:
![{\displaystyle {\begin{aligned}H(X_{1},\ldots ,X_{n})&=F{\bigl (}G_{1}(X_{1},\ldots ,X_{n}),\ldots ,G_{m}(X_{1},\ldots ,X_{n}){\bigr )}\\[5pt]\sigma {\bigl (}H(X_{1},\ldots ,X_{n}){\bigr )}&=\sigma {\bigl (}F(G_{1},\ldots ,G_{m}){\bigr )}\\[5pt]&=F{\bigl (}\sigma (G_{1}),\ldots ,\sigma (G_{m}){\bigr )}\\[5pt]&=F(G_{1},\ldots ,G_{m})\\[5pt]&=H(X_{1},\ldots ,X_{n})\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5c95a4876f8742b7f3e415f6185dbe24325fb10)