Related identities Newton's identities




1 related identities

1.1 variant using complete homogeneous symmetric polynomials
1.2 expressing elementary symmetric polynomials in terms of power sums
1.3 expressing complete homogeneous symmetric polynomials in terms of power sums
1.4 expressing power sums in terms of elementary symmetric polynomials
1.5 expressing power sums in terms of complete homogeneous symmetric polynomials
1.6 expressions determinants





related identities

there number of (families of) identities that, while should distinguished newton s identities, closely related them.


a variant using complete homogeneous symmetric polynomials

denoting hk complete homogeneous symmetric polynomial sum of monomials of degree k, power sum polynomials satisfy identities similar newton s identities, not involving minus signs. expressed identities of in ring of symmetric functions, read







k

h

k


=



i
=
1


k



h

k

i



p

i


,


{\displaystyle kh_{k}=\sum _{i=1}^{k}h_{k-i}p_{i},}



valid n ≥ k ≥ 1. contrary newton s identities, left-hand sides not become 0 large k, , right-hand sides contain ever more non-zero terms. first few values of k, 1 has












h

1





=

p

1


,




2

h

2





=

h

1



p

1


+

p

2


,




3

h

3





=

h

2



p

1


+

h

1



p

2


+

p

3


.






{\displaystyle {\begin{aligned}h_{1}&=p_{1},\\2h_{2}&=h_{1}p_{1}+p_{2},\\3h_{3}&=h_{2}p_{1}+h_{1}p_{2}+p_{3}.\\\end{aligned}}}



these relations can justified argument analogous 1 comparing coefficients in power series given above, based in case on generating function identity










k
=
0






h

k


(

x

1


,

,

x

n


)

t

k


=



i
=
1


n




1

1


x

i


t



.


{\displaystyle \sum _{k=0}^{\infty }h_{k}(x_{1},\ldots ,x_{n})t^{k}=\prod _{i=1}^{n}{\frac {1}{1-x_{i}t}}.}



proofs of newton s identities, these given below, cannot adapted prove these variants of identities.


expressing elementary symmetric polynomials in terms of power sums

as mentioned, newton s identities can used recursively express elementary symmetric polynomials in terms of power sums. doing requires introduction of integer denominators, can done in ring Λq of symmetric functions rational coefficients:












e

1





=

p

1


,





e

2





=



1
2



p

1


2





1
2



p

2







=



1
2


(

p

1


2




p

2


)
,






e

3





=



1
6



p

1


3





1
2



p

1



p

2


+


1
3



p

3







=



1
6


(

p

1


3



3

p

1



p

2


+
2

p

3


)
,






e

4





=



1
24



p

1


4





1
4



p

1


2



p

2


+


1
8



p

2


2


+


1
3



p

1



p

3





1
4



p

4







=



1
24


(

p

1


4



6

p

1


2



p

2


+
3

p

2


2


+
8

p

1



p

3



6

p

4


)
,






 
 






e

n





=
(

1

)

n








m

1


+
2

m

2


+

+
n

m

n


=
n



m

1



0
,

,

m

n



0







i
=
1


n





(


p

i



)


m

i







m

i


!

i


m

i













{\displaystyle {\begin{aligned}e_{1}&=p_{1},\\e_{2}&=\textstyle {\frac {1}{2}}p_{1}^{2}-{\frac {1}{2}}p_{2}&&=\textstyle {\frac {1}{2}}(p_{1}^{2}-p_{2}),\\e_{3}&=\textstyle {\frac {1}{6}}p_{1}^{3}-{\frac {1}{2}}p_{1}p_{2}+{\frac {1}{3}}p_{3}&&=\textstyle {\frac {1}{6}}(p_{1}^{3}-3p_{1}p_{2}+2p_{3}),\\e_{4}&=\textstyle {\frac {1}{24}}p_{1}^{4}-{\frac {1}{4}}p_{1}^{2}p_{2}+{\frac {1}{8}}p_{2}^{2}+{\frac {1}{3}}p_{1}p_{3}-{\frac {1}{4}}p_{4}&&=\textstyle {\frac {1}{24}}(p_{1}^{4}-6p_{1}^{2}p_{2}+3p_{2}^{2}+8p_{1}p_{3}-6p_{4}),\\&~~\vdots \\e_{n}&=(-1)^{n}\sum _{m_{1}+2m_{2}+\cdots +nm_{n}=n \atop m_{1}\geq 0,\ldots ,m_{n}\geq 0}\prod _{i=1}^{n}{\frac {(-p_{i})^{m_{i}}}{m_{i}!i^{m_{i}}}}\\\end{aligned}}}



and forth. general formula can conveniently expressed as








e

n


=



(

1

)

n




n
!




b

n


(


p

1


,

1
!

p

2


,

2
!

p

3


,

,

(
n

1
)
!

p

n


)
,


{\displaystyle e_{n}={\frac {(-1)^{n}}{n!}}b_{n}(-p_{1},-1!p_{2},-2!p_{3},\ldots ,-(n-1)!p_{n}),}



where bn complete exponential bell polynomial. expression leads following identity generating functions:










n
=
0






e

n




x

n


=
exp


(



n
=
1








(

1

)

n
+
1



n



p

n




x

n


)

.


{\displaystyle \sum _{n=0}^{\infty }e_{n}\,x^{n}=\exp \left(\sum _{n=1}^{\infty }{\frac {(-1)^{n+1}}{n}}p_{n}\,x^{n}\right).}



applied monic polynomial, these formulae express coefficients in terms of power sums of roots: replace each ei ai , each pk sk.


expressing complete homogeneous symmetric polynomials in terms of power sums

the analogous relations involving complete homogeneous symmetric polynomials can developed, giving equations












h

1





=

p

1


,





h

2





=



1
2



p

1


2


+


1
2



p

2







=



1
2


(

p

1


2


+

p

2


)
,






h

3





=



1
6



p

1


3


+


1
2



p

1



p

2


+


1
3



p

3







=



1
6


(

p

1


3


+
3

p

1



p

2


+
2

p

3


)
,






h

4





=



1
24



p

1


4


+


1
4



p

1


2



p

2


+


1
8



p

2


2


+


1
3



p

1



p

3


+


1
4



p

4







=



1
24


(

p

1


4


+
6

p

1


2



p

2


+
3

p

2


2


+
8

p

1



p

3


+
6

p

4


)
,






 
 






h

n





=






m

1


+
2

m

2


+

+
n

m

n


=
n



m

1



0
,

,

m

n



0







i
=
1


n





p

i



m

i






m

i


!

i


m

i













{\displaystyle {\begin{aligned}h_{1}&=p_{1},\\h_{2}&=\textstyle {\frac {1}{2}}p_{1}^{2}+{\frac {1}{2}}p_{2}&&=\textstyle {\frac {1}{2}}(p_{1}^{2}+p_{2}),\\h_{3}&=\textstyle {\frac {1}{6}}p_{1}^{3}+{\frac {1}{2}}p_{1}p_{2}+{\frac {1}{3}}p_{3}&&=\textstyle {\frac {1}{6}}(p_{1}^{3}+3p_{1}p_{2}+2p_{3}),\\h_{4}&=\textstyle {\frac {1}{24}}p_{1}^{4}+{\frac {1}{4}}p_{1}^{2}p_{2}+{\frac {1}{8}}p_{2}^{2}+{\frac {1}{3}}p_{1}p_{3}+{\frac {1}{4}}p_{4}&&=\textstyle {\frac {1}{24}}(p_{1}^{4}+6p_{1}^{2}p_{2}+3p_{2}^{2}+8p_{1}p_{3}+6p_{4}),\\&~~\vdots \\h_{n}&=\sum _{m_{1}+2m_{2}+\cdots +nm_{n}=n \atop m_{1}\geq 0,\ldots ,m_{n}\geq 0}\prod _{i=1}^{n}{\frac {p_{i}^{m_{i}}}{m_{i}!i^{m_{i}}}}\\\end{aligned}}}



and forth, in there plus signs. in terms of complete bell polynomial,








h

n


=


1

n
!




b

n


(

p

1


,
1
!

p

2


,
2
!

p

3


,

,
(
n

1
)
!

p

n


)
.


{\displaystyle h_{n}={\frac {1}{n!}}b_{n}(p_{1},1!p_{2},2!p_{3},\ldots ,(n-1)!p_{n}).}



these expressions correspond cycle index polynomials of symmetric groups, if 1 interprets power sums pi indeterminates: coefficient in expression hk of monomial p1p2…pl equal fraction of permutations of k have m1 fixed points, m2 cycles of length 2, …, , ml cycles of length l. explicitly, coefficient can written



1

/

n


{\displaystyle 1/n}





n
=

Π

i
=
1


l


(

m

i


!


i


m

i




)


{\displaystyle n=\pi _{i=1}^{l}(m_{i}!\,i^{m_{i}})}

; n number permutations commuting given permutation Ï€ of given cycle type. expressions elementary symmetric functions have coefficients same absolute value, sign equal sign of Ï€, namely (−1).


it can proved considering following inductive step:











m
f
(
m
;

m

1


,
.
.
.
,

m

n


)



=
f
(
m

1
;

m

1



1
,
.
.
.
,

m

n


)
+
.
.
.
+
f
(
m

n
;

m

1


,
.
.
.
,

m

n



1
)





m

1





i
=
1


n




1


i


m

i





m

i


!



+
.
.
.
+
n

m

n





i
=
1


n




1


i


m

i





m

i


!






=
m



i
=
1


n




1


i


m

i





m

i


!









{\displaystyle {\begin{aligned}mf(m;m_{1},...,m_{n})&=f(m-1;m_{1}-1,...,m_{n})+...+f(m-n;m_{1},...,m_{n}-1)\\m_{1}\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}+...+nm_{n}\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}&=m\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}\end{aligned}}}



expressing power sums in terms of elementary symmetric polynomials

one may use newton s identities express power sums in terms of symmetric polynomials, not introduce denominators:












p

1





=

e

1


,





p

2





=

e

1


2



2

e

2


,





p

3





=

e

1


3



3

e

2



e

1


+
3

e

3


,





p

4





=

e

1


4



4

e

2



e

1


2


+
4

e

3



e

1


+
2

e

2


2



4

e

4


,





p

5





=

e

1


5



5

e

2



e

1


3


+
5

e

3



e

1


2


+
5

e

2


2



e

1



5

e

4



e

1



5

e

3



e

2


+
5

e

5


,





p

6





=

e

1


6



6

e

2



e

1


4


+
6

e

3



e

1


3


+
9

e

2


2



e

1


2



6

e

4



e

1


2



12

e

3



e

2



e

1


+
6

e

5



e

1



2

e

2


3


+
3

e

3


2


+
6

e

4



e

2



6

e

6


.






{\displaystyle {\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}^{2}-2e_{2},\\p_{3}&=e_{1}^{3}-3e_{2}e_{1}+3e_{3},\\p_{4}&=e_{1}^{4}-4e_{2}e_{1}^{2}+4e_{3}e_{1}+2e_{2}^{2}-4e_{4},\\p_{5}&=e_{1}^{5}-5e_{2}e_{1}^{3}+5e_{3}e_{1}^{2}+5e_{2}^{2}e_{1}-5e_{4}e_{1}-5e_{3}e_{2}+5e_{5},\\p_{6}&=e_{1}^{6}-6e_{2}e_{1}^{4}+6e_{3}e_{1}^{3}+9e_{2}^{2}e_{1}^{2}-6e_{4}e_{1}^{2}-12e_{3}e_{2}e_{1}+6e_{5}e_{1}-2e_{2}^{3}+3e_{3}^{2}+6e_{4}e_{2}-6e_{6}.\end{aligned}}}



the first 4 formulas obtained albert girard in 1629 (thus before newton).


the general formula (for non-negative integers m) is:








p

m


=






r

1


+
2

r

2


+

+
m

r

m


=
m



r

1



0
,

,

r

m



0




(

1

)

m





m
(

r

1


+

r

2


+

+

r

m



1
)
!



r

1


!

r

2


!


r

m


!






i
=
1


m


(


e

i



)


r

i




.


{\displaystyle p_{m}=\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,\ldots ,r_{m}\geq 0}(-1)^{m}{\frac {m(r_{1}+r_{2}+\cdots +r_{m}-1)!}{r_{1}!r_{2}!\cdots r_{m}!}}\prod _{i=1}^{m}(-e_{i})^{r_{i}}.}



this can conveniently stated in terms of ordinary bell polynomials as








p

m


=
(

1

)

m


m



k
=
1


m




1
k






b
^




m
,
k


(


e

1


,

,


e

m

k
+
1


)
.


{\displaystyle p_{m}=(-1)^{m}m\sum _{k=1}^{m}{\frac {1}{k}}{\hat {b}}_{m,k}(-e_{1},\dots ,-e_{m-k+1}).}



the formula can proved considering following inductive step:











f
(
m
;


r

1


,

,

r

n


)



=
f
(
m

1
;


r

1



1
,

,

r

n


)
+

+
f
(
m

n
;


r

1


,

,

r

n



1
)






=


1

(

r

1



1
)
!


r

n


!



(
m

1
)
(

r

1


+

+

r

n



2
)
!
+

+


1


r

1


!

(

r

n



1
)
!



(
m

n
)
(

r

1


+

+

r

n



2
)
!






=


1


r

1


!


r

n


!




[

r

1


(
m

1
)
+

+

r

n


(
m

n
)
]


[

r

1


+

+

r

n



2
]

!






=


1


r

1


!


r

n


!




[
m
(

r

1


+

+

r

n


)

m
]


[

r

1


+

+

r

n



2
]

!






=



m
(

r

1


+

+

r

n



1
)
!



r

1


!


r

n


!









{\displaystyle {\begin{aligned}f(m;\;r_{1},\cdots ,r_{n})&=f(m-1;\;r_{1}-1,\cdots ,r_{n})+\cdots +f(m-n;\;r_{1},\cdots ,r_{n}-1)\\&={\frac {1}{(r_{1}-1)!\cdots r_{n}!}}(m-1)(r_{1}+\cdots +r_{n}-2)!+\cdots +{\frac {1}{r_{1}!\cdots (r_{n}-1)!}}(m-n)(r_{1}+\cdots +r_{n}-2)!\\&={\frac {1}{r_{1}!\cdots r_{n}!}}\left[r_{1}(m-1)+\cdots +r_{n}(m-n)\right]\left[r_{1}+\cdots +r_{n}-2\right]!\\&={\frac {1}{r_{1}!\cdots r_{n}!}}\left[m(r_{1}+\cdots +r_{n})-m\right]\left[r_{1}+\cdots +r_{n}-2\right]!\\&={\frac {m(r_{1}+\cdots +r_{n}-1)!}{r_{1}!\cdots r_{n}!}}\end{aligned}}}



expressing power sums in terms of complete homogeneous symmetric polynomials

finally 1 may use variant identities involving complete homogeneous symmetric polynomials express power sums in term of them:












p

1





=
+

h

1


,





p

2





=


h

1


2


+
2

h

2


,





p

3





=
+

h

1


3



3

h

2



h

1


+
3

h

3


,





p

4





=


h

1


4


+
4

h

2



h

1


2



4

h

3



h

1



2

h

2


2


+
4

h

4


,





p

5





=
+

h

1


5



5

h

2



h

1


3


+
5

h

2


2



h

1


+
5

h

3



h

1


2



5

h

3



h

2



5

h

4



h

1


+
5

h

5


,





p

6





=


h

1


6


+
6

h

2



h

1


4



9

h

2


2



h

1


2



6

h

3



h

1


3


+
2

h

2


3


+
12

h

3



h

2



h

1


+
6

h

4



h

1


2



3

h

3


2



6

h

4



h

2



6

h

1



h

5


+
6

h

6


,






{\displaystyle {\begin{aligned}p_{1}&=+h_{1},\\p_{2}&=-h_{1}^{2}+2h_{2},\\p_{3}&=+h_{1}^{3}-3h_{2}h_{1}+3h_{3},\\p_{4}&=-h_{1}^{4}+4h_{2}h_{1}^{2}-4h_{3}h_{1}-2h_{2}^{2}+4h_{4},\\p_{5}&=+h_{1}^{5}-5h_{2}h_{1}^{3}+5h_{2}^{2}h_{1}+5h_{3}h_{1}^{2}-5h_{3}h_{2}-5h_{4}h_{1}+5h_{5},\\p_{6}&=-h_{1}^{6}+6h_{2}h_{1}^{4}-9h_{2}^{2}h_{1}^{2}-6h_{3}h_{1}^{3}+2h_{2}^{3}+12h_{3}h_{2}h_{1}+6h_{4}h_{1}^{2}-3h_{3}^{2}-6h_{4}h_{2}-6h_{1}h_{5}+6h_{6},\\\end{aligned}}}



and on. apart replacement of each ei corresponding hi, change respect previous family of identities in signs of terms, in case depend on number of factors present: sign of monomial




Π

i
=
1


l



h

i



m

i






{\displaystyle \pi _{i=1}^{l}h_{i}^{m_{i}}}

−(−1). in particular above description of absolute value of coefficients applies here well.


the general formula (for non-negative integers m) is:








p

m


=







r

1


+
2

r

2


+

+
m

r

m


=
m



r

1



0
,
.
.
.
,

r

m



0







m
(

r

1


+

r

2


+

+

r

m



1
)
!



r

1


!

r

2


!


r

m


!






i
=
1


m


(


h

i



)


r

i






{\displaystyle p_{m}=-\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,...,r_{m}\geq 0}{\frac {m(r_{1}+r_{2}+\cdots +r_{m}-1)!}{r_{1}!r_{2}!\cdots r_{m}!}}\prod _{i=1}^{m}(-h_{i})^{r_{i}}}



expressions determinants

one can obtain explicit formulas above expressions in form of determinants, considering first n of newton s identities (or counterparts complete homogeneous polynomials) linear equations in elementary symmetric functions known , power sums unknowns (or vice versa), , apply cramer s rule find solution final unknown. instance taking newton s identities in form












e

1





=
1

p

1


,




2

e

2





=

e

1



p

1



1

p

2


,




3

e

3





=

e

2



p

1




e

1



p

2


+
1

p

3


,











n

e

n





=

e

n

1



p

1




e

n

2



p

2


+

+
(

1

)

n



e

1



p

n

1


+
(

1

)

n

1



p

n








{\displaystyle {\begin{aligned}e_{1}&=1p_{1},\\2e_{2}&=e_{1}p_{1}-1p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+1p_{3},\\&\vdots \\ne_{n}&=e_{n-1}p_{1}-e_{n-2}p_{2}+\cdots +(-1)^{n}e_{1}p_{n-1}+(-1)^{n-1}p_{n}\\\end{aligned}}}



we consider




p

1




{\displaystyle p_{1}}

,






p

2





{\displaystyle {-p_{2}}}

,




p

3




{\displaystyle p_{3}}

, …,



(

1

)

n



p

n

1




{\displaystyle (-1)^{n}p_{n-1}}

,




p

n




{\displaystyle p_{n}}

unknowns, , solve final one, giving












p

n


=







|



1


0







e

1







e

1




1


0





2

e

2







e

2





e

1




1



3

e

3






















e

n

1








e

2





e

1




n

e

n





|





|



1


0









e

1




1


0








e

2





e

1




1


















e

n

1








e

2





e

1




(

1

)

n

1





|




1






=

(

1

)

n

1







|



1


0







e

1







e

1




1


0





2

e

2







e

2





e

1




1



3

e

3






















e

n

1








e

2





e

1




n

e

n





|






=







|




e

1




1


0







2

e

2





e

1




1


0







3

e

3





e

2





e

1




1

















n

e

n





e

n

1









e

1





|


.






{\displaystyle {\begin{aligned}p_{n}={}&{\begin{vmatrix}1&0&\cdots &&e_{1}\\e_{1}&1&0&\cdots &2e_{2}\\e_{2}&e_{1}&1&&3e_{3}\\\vdots &&\ddots &\ddots &\vdots \\e_{n-1}&\cdots &e_{2}&e_{1}&ne_{n}\end{vmatrix}}{\begin{vmatrix}1&0&\cdots &\\e_{1}&1&0&\cdots \\e_{2}&e_{1}&1&\\\vdots &&\ddots &\ddots \\e_{n-1}&\cdots &e_{2}&e_{1}&(-1)^{n-1}\end{vmatrix}}^{-1}\\={(-1)^{n-1}}&{\begin{vmatrix}1&0&\cdots &&e_{1}\\e_{1}&1&0&\cdots &2e_{2}\\e_{2}&e_{1}&1&&3e_{3}\\\vdots &&\ddots &\ddots &\vdots \\e_{n-1}&\cdots &e_{2}&e_{1}&ne_{n}\end{vmatrix}}\\={}&{\begin{vmatrix}e_{1}&1&0&\cdots \\2e_{2}&e_{1}&1&0&\cdots \\3e_{3}&e_{2}&e_{1}&1\\\vdots &&&\ddots &\ddots \\ne_{n}&e_{n-1}&\cdots &&e_{1}\end{vmatrix}}.\end{aligned}}}



solving




e

n




{\displaystyle e_{n}}

instead of




p

n




{\displaystyle p_{n}}

similar, analogous computations complete homogeneous symmetric polynomials; in each case details messier final results, (macdonald 1979, p. 20):












e

n


=


1

n
!







|




p

1




1


0








p

2





p

1




2


0




















p

n

1





p

n

2








p

1




n

1





p

n





p

n

1








p

2





p

1





|







p

n


=
(

1

)

n

1






|




h

1




1


0







2

h

2





h

1




1


0







3

h

3





h

2





h

1




1

















n

h

n





h

n

1









h

1





|







h

n


=


1

n
!







|




p

1





1


0








p

2





p

1





2


0




















p

n

1





p

n

2








p

1




1

n





p

n





p

n

1








p

2





p

1





|


.






{\displaystyle {\begin{aligned}e_{n}={\frac {1}{n!}}&{\begin{vmatrix}p_{1}&1&0&\cdots \\p_{2}&p_{1}&2&0&\cdots \\\vdots &&\ddots &\ddots \\p_{n-1}&p_{n-2}&\cdots &p_{1}&n-1\\p_{n}&p_{n-1}&\cdots &p_{2}&p_{1}\end{vmatrix}}\\p_{n}=(-1)^{n-1}&{\begin{vmatrix}h_{1}&1&0&\cdots \\2h_{2}&h_{1}&1&0&\cdots \\3h_{3}&h_{2}&h_{1}&1\\\vdots &&&\ddots &\ddots \\nh_{n}&h_{n-1}&\cdots &&h_{1}\end{vmatrix}}\\h_{n}={\frac {1}{n!}}&{\begin{vmatrix}p_{1}&-1&0&\cdots \\p_{2}&p_{1}&-2&0&\cdots \\\vdots &&\ddots &\ddots \\p_{n-1}&p_{n-2}&\cdots &p_{1}&1-n\\p_{n}&p_{n-1}&\cdots &p_{2}&p_{1}\end{vmatrix}}.\end{aligned}}}



note use of determinants makes formula




h

n




{\displaystyle h_{n}}

has additional minus signs compared 1




e

n




{\displaystyle e_{n}}

, while situation expanded form given earlier opposite. remarked in (littlewood 1950, p. 84) 1 can alternatively obtain formula




h

n




{\displaystyle h_{n}}

taking permanent of matrix




e

n




{\displaystyle e_{n}}

instead of determinant, , more expression schur polynomial can obtained taking corresponding immanant of matrix.








Comments

Popular posts from this blog

Investigation Murder of Brooke Wilberger

Geography St Columb Major

Shri Ram Centre for Performing Arts Shriram Bharatiya Kala Kendra