A permutation is a bijective function from a set to itself.
Let
X
=
{
X
1
,
…
,
X
n
}
{\displaystyle X={\bigl \{}X_{1},\ldots ,X_{n}{\bigr \}}}
be a finite set. The function
σ
:
X
→
X
{\displaystyle \sigma :X\to X}
is called a permutation if and only if it is one-to-one and onto .
Meaning, for all
1
≤
i
≤
n
{\displaystyle 1\leq i\leq n}
there exists a unique
1
≤
j
≤
n
{\displaystyle 1\leq j\leq n}
such that
σ
(
X
i
)
=
X
σ
(
i
)
=
X
j
{\displaystyle \sigma (X_{i})=X_{\sigma (i)}=X_{j}}
.
The set of all permutations of the elements of
X
{\displaystyle X}
is denoted by
S
X
{\displaystyle S_{X}}
.
For
X
=
{
1
,
2
,
3
}
{\displaystyle X={\bigl \{}1,2,3{\bigr \}}}
there are
3
!
=
6
{\displaystyle 3!=6}
different permutations:
σ
1
=
[
1
2
3
1
2
3
]
,
σ
2
=
[
1
2
3
1
3
2
]
σ
3
=
[
1
2
3
2
1
3
]
,
σ
4
=
[
1
2
3
2
3
1
]
σ
5
=
[
1
2
3
3
1
2
]
,
σ
6
=
[
1
2
3
3
2
1
]
{\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}}}
In general, if
|
X
|
=
n
{\displaystyle |X|=n}
then
|
S
X
|
=
n
!
=
1
⋅
2
⋯
n
{\displaystyle |S_{X}|=n!=1\cdot 2\cdots n}
.
Let
F
(
X
→
n
)
{\displaystyle F({\vec {X}}{}^{n})}
be a polynomial. Let us define:
σ
(
F
)
:=
F
(
X
σ
(
1
)
,
…
,
X
σ
(
n
)
)
{\displaystyle \sigma (F):=F(X_{\sigma (1)},\ldots ,X_{\sigma (n)})}
Let
F
(
X
→
n
)
,
G
(
X
→
n
)
{\displaystyle F({\vec {X}}{}^{n}),G({\vec {X}}{}^{n})}
be polynomials. Then we have:
σ
(
c
F
)
=
c
σ
(
F
)
{\displaystyle \sigma (cF)=c\,\sigma (F)}
such that
c
∈
R
{\displaystyle c\in \mathbb {R} }
.
σ
(
F
±
G
)
=
σ
(
F
)
±
σ
(
G
)
{\displaystyle \sigma (F\pm G)=\sigma (F)\pm \sigma (G)}
σ
(
F
⋅
G
)
=
σ
(
F
)
⋅
σ
(
G
)
{\displaystyle \sigma (F\cdot G)=\sigma (F)\cdot \sigma (G)}
(
σ
1
∘
σ
2
)
(
F
)
=
σ
1
(
σ
2
(
F
)
)
{\displaystyle (\sigma _{1}\circ \sigma _{2})(F)=\sigma _{1}(\sigma _{2}(F))}
By definition, the permutation is applied on the variable indexes only.
First, let
F
,
G
{\displaystyle F,G}
be monomials of the form
F
=
a
X
1
a
1
⋯
X
n
a
n
G
=
b
X
1
b
1
⋯
X
n
b
n
σ
(
F
±
G
)
=
σ
(
a
X
1
a
1
⋯
X
n
a
n
±
b
X
1
b
1
⋯
X
n
b
n
)
=
a
X
σ
(
1
)
a
1
⋯
X
σ
(
n
)
a
n
±
b
X
σ
(
1
)
b
1
⋯
X
σ
(
n
)
b
n
=
σ
(
a
X
1
a
1
⋯
X
n
a
n
)
±
σ
(
b
X
1
b
1
⋯
X
n
b
n
)
=
σ
(
F
)
±
σ
(
G
)
{\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}}}
We can generalize by induction for
F
=
∑
i
1
=
1
k
1
F
i
1
,
G
=
∑
i
2
=
1
k
2
G
i
2
{\displaystyle 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
{\displaystyle F_{i_{1}},G_{i_{2}}}
are monomials.
Same as before, let
F
,
G
{\displaystyle F,G}
be monomials of the form
F
=
a
X
1
a
1
⋯
X
n
a
n
G
=
b
X
1
b
1
⋯
X
n
b
n
σ
(
F
⋅
G
)
=
σ
(
a
X
1
a
1
⋯
X
n
a
n
⋅
b
X
1
b
1
⋯
X
n
b
n
)
=
a
b
σ
(
X
1
a
1
+
b
1
⋯
X
n
a
n
+
b
n
)
=
a
b
X
σ
(
1
)
a
1
+
b
1
⋯
X
σ
(
n
)
a
n
+
b
n
=
(
a
X
σ
(
1
)
a
1
⋯
X
σ
(
n
)
a
n
)
⋅
(
b
X
σ
(
1
)
b
1
⋯
X
σ
(
n
)
b
n
)
=
σ
(
a
X
1
a
1
⋯
X
n
a
n
)
⋅
σ
(
b
X
1
b
1
⋯
X
n
b
n
)
=
σ
(
F
)
⋅
σ
(
G
)
{\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}}}
Again, We can generalize by induction for
F
=
∑
i
1
=
1
k
1
F
i
1
,
G
=
∑
i
2
=
1
k
2
G
i
2
{\displaystyle 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
{\displaystyle F_{i_{1}},G_{i_{2}}}
are monomials:
σ
(
F
⋅
G
)
=
σ
(
∑
i
1
=
1
k
1
F
i
1
⋅
∑
i
2
=
1
k
2
G
i
2
)
=
σ
(
∑
i
1
=
1
k
1
∑
i
2
=
1
k
2
F
i
1
G
i
2
)
=
∑
i
1
=
1
k
1
∑
i
2
=
1
k
2
σ
(
F
i
1
⋅
G
i
2
)
=
∑
i
1
=
1
k
1
∑
i
2
=
1
k
2
σ
(
F
i
1
)
⋅
σ
(
G
i
2
)
=
∑
i
1
=
1
k
1
σ
(
F
i
1
)
⋅
∑
i
2
=
1
k
2
σ
(
G
i
2
)
=
σ
(
∑
i
1
=
1
k
1
F
i
1
)
⋅
σ
(
∑
i
2
=
1
k
2
G
i
2
)
=
σ
(
F
)
⋅
σ
(
G
)
{\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}}}
(
σ
1
∘
σ
2
)
(
F
)
=
F
(
X
(
σ
1
∘
σ
2
)
(
1
)
,
…
,
X
(
σ
1
∘
σ
2
)
(
n
)
)
=
F
(
X
σ
1
(
σ
2
(
1
)
)
,
…
,
X
σ
1
(
σ
2
(
n
)
)
)
=
σ
1
(
F
(
X
σ
2
(
1
)
,
…
,
X
σ
2
(
n
)
)
)
=
σ
1
(
σ
2
(
F
)
)
{\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}}}
Let
P
(
X
→
n
)
{\displaystyle P({\vec {X}}{}^{n})}
be a polynomial. Then it is called symmetric if
σ
(
P
)
=
P
{\displaystyle \sigma (P)=P}
for all permutations
σ
:
{
1
,
…
,
n
}
→
{
1
,
…
,
n
}
{\displaystyle \sigma :\{1,\ldots ,n\}\to \{1,\ldots ,n\}}
.
P
(
x
1
,
x
2
,
x
3
)
=
x
1
2
x
2
2
x
3
2
+
3
x
1
+
3
x
2
+
3
x
3
=
x
1
2
x
3
2
x
2
2
+
3
x
1
+
3
x
3
+
3
x
2
=
x
2
2
x
1
2
x
3
2
+
3
x
2
+
3
x
1
+
3
x
3
=
x
2
2
x
3
2
x
1
2
+
3
x
2
+
3
x
3
+
3
x
1
=
x
3
2
x
1
2
x
2
2
+
3
x
3
+
3
x
1
+
3
x
2
=
x
3
2
x
2
2
x
1
2
+
3
x
3
+
3
x
2
+
3
x
1
{\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}}}
A non-symmetric polynomial:
P
(
x
1
,
x
2
,
x
3
)
=
x
1
+
x
2
−
x
3
≠
x
1
+
x
3
−
x
2
≠
x
2
+
x
1
−
x
3
≠
x
2
+
x
3
−
x
1
≠
x
3
+
x
1
−
x
2
≠
x
3
+
x
2
−
x
1
{\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}}}
The sum and product of symmetric polynomials is a symmetric polynomial.
Let
F
{\displaystyle F}
be a polynomial in variables
Y
1
,
…
,
Y
m
{\displaystyle Y_{1},\ldots ,Y_{m}}
, and let
G
1
,
…
,
G
m
{\displaystyle G_{1},\ldots ,G_{m}}
be symmetric polynomials in variables
X
1
,
…
,
X
n
{\displaystyle X_{1},\ldots ,X_{n}}
.
Then
F
(
G
→
m
(
X
→
n
)
)
{\displaystyle F({\vec {G}}{}^{m}({\vec {X}}{}^{n}))}
is also symmetric in variables
X
1
,
…
,
X
n
{\displaystyle X_{1},\ldots ,X_{n}}
.
This follows from the properties in definition 2 and the symmetric polynomial definition above.
By definition we get:
σ
(
F
(
G
→
m
(
X
→
n
)
)
)
=
σ
(
F
(
G
1
(
X
→
n
)
,
…
,
G
m
(
X
→
n
)
)
)
=
F
(
σ
(
G
1
(
X
→
n
)
)
,
…
,
σ
(
G
m
(
X
→
n
)
)
)
=
F
(
G
1
(
X
→
n
)
,
…
,
G
m
(
X
→
n
)
)
=
F
(
G
→
m
(
X
→
n
)
)
{\displaystyle {\begin{aligned}\sigma {\bigl (}F({\vec {G}}{}^{m}({\vec {X}}{}^{n})){\bigr )}&=\sigma {\bigl (}F(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{\bigl (}G_{1}({\vec {X}}{}^{n}),\ldots ,G_{m}({\vec {X}}{}^{n}){\bigr )}\\[5pt]&=F({\vec {G}}{}^{m}({\vec {X}}{}^{n}))\end{aligned}}}