Mathematical statement Newton's identities
1 mathematical statement
1.1 formulation in terms of symmetric polynomials
1.2 application roots of polynomial
1.3 application characteristic polynomial of matrix
1.4 relation galois theory
mathematical statement
formulation in terms of symmetric polynomials
let x1, …, xn variables, denote k ≥ 1 pk(x1, …, xn) k-th power sum:
p
k
(
x
1
,
…
,
x
n
)
=
∑
i
=
1
n
x
i
k
=
x
1
k
+
⋯
+
x
n
k
,
{\displaystyle p_{k}(x_{1},\ldots ,x_{n})=\sum \nolimits _{i=1}^{n}x_{i}^{k}=x_{1}^{k}+\cdots +x_{n}^{k},}
and k ≥ 0 denote ek(x1, …, xn) elementary symmetric polynomial (that is, sum of distinct products of k distinct variables), so
e
0
(
x
1
,
…
,
x
n
)
=
1
,
e
1
(
x
1
,
…
,
x
n
)
=
x
1
+
x
2
+
⋯
+
x
n
,
e
2
(
x
1
,
…
,
x
n
)
=
∑
1
≤
i
<
j
≤
n
x
i
x
j
,
e
n
(
x
1
,
…
,
x
n
)
=
x
1
x
2
⋯
x
n
,
e
k
(
x
1
,
…
,
x
n
)
=
0
,
for
k
>
n
.
{\displaystyle {\begin{aligned}e_{0}(x_{1},\ldots ,x_{n})&=1,\\e_{1}(x_{1},\ldots ,x_{n})&=x_{1}+x_{2}+\cdots +x_{n},\\e_{2}(x_{1},\ldots ,x_{n})&=\textstyle \sum _{1\leq i<j\leq n}x_{i}x_{j},\\e_{n}(x_{1},\ldots ,x_{n})&=x_{1}x_{2}\cdots x_{n},\\e_{k}(x_{1},\ldots ,x_{n})&=0,\quad {\text{for}}\ k>n.\\\end{aligned}}}
then newton s identities can stated as
k
e
k
(
x
1
,
…
,
x
n
)
=
∑
i
=
1
k
(
−
1
)
i
−
1
e
k
−
i
(
x
1
,
…
,
x
n
)
p
i
(
x
1
,
…
,
x
n
)
,
{\displaystyle ke_{k}(x_{1},\ldots ,x_{n})=\sum _{i=1}^{k}(-1)^{i-1}e_{k-i}(x_{1},\ldots ,x_{n})p_{i}(x_{1},\ldots ,x_{n}),}
valid n ≥ 1 , k ≥ 1.
also, 1 has
0
=
∑
i
=
k
−
n
k
(
−
1
)
i
−
1
e
k
−
i
(
x
1
,
…
,
x
n
)
p
i
(
x
1
,
…
,
x
n
)
,
{\displaystyle 0=\sum _{i=k-n}^{k}(-1)^{i-1}e_{k-i}(x_{1},\ldots ,x_{n})p_{i}(x_{1},\ldots ,x_{n}),}
for k > n ≥ 1.
concretely, 1 gets first few values of k:
e
1
(
x
1
,
…
,
x
n
)
=
p
1
(
x
1
,
…
,
x
n
)
,
2
e
2
(
x
1
,
…
,
x
n
)
=
e
1
(
x
1
,
…
,
x
n
)
p
1
(
x
1
,
…
,
x
n
)
−
p
2
(
x
1
,
…
,
x
n
)
,
3
e
3
(
x
1
,
…
,
x
n
)
=
e
2
(
x
1
,
…
,
x
n
)
p
1
(
x
1
,
…
,
x
n
)
−
e
1
(
x
1
,
…
,
x
n
)
p
2
(
x
1
,
…
,
x
n
)
+
p
3
(
x
1
,
…
,
x
n
)
.
{\displaystyle {\begin{aligned}e_{1}(x_{1},\ldots ,x_{n})&=p_{1}(x_{1},\ldots ,x_{n}),\\2e_{2}(x_{1},\ldots ,x_{n})&=e_{1}(x_{1},\ldots ,x_{n})p_{1}(x_{1},\ldots ,x_{n})-p_{2}(x_{1},\ldots ,x_{n}),\\3e_{3}(x_{1},\ldots ,x_{n})&=e_{2}(x_{1},\ldots ,x_{n})p_{1}(x_{1},\ldots ,x_{n})-e_{1}(x_{1},\ldots ,x_{n})p_{2}(x_{1},\ldots ,x_{n})+p_{3}(x_{1},\ldots ,x_{n}).\\\end{aligned}}}
the form , validity of these equations not depend on number n of variables (although point left-hand side becomes 0 does, namely after n-th identity), makes possible state them identities in ring of symmetric functions. in ring 1 has
e
1
=
p
1
,
2
e
2
=
e
1
p
1
−
p
2
,
3
e
3
=
e
2
p
1
−
e
1
p
2
+
p
3
,
4
e
4
=
e
3
p
1
−
e
2
p
2
+
e
1
p
3
−
p
4
,
{\displaystyle {\begin{aligned}e_{1}&=p_{1},\\2e_{2}&=e_{1}p_{1}-p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+p_{3},\\4e_{4}&=e_{3}p_{1}-e_{2}p_{2}+e_{1}p_{3}-p_{4},\\\end{aligned}}}
and on; here left-hand sides never become zero. these equations allow recursively express ei in terms of pk; able inverse, 1 may rewrite them as
p
1
=
e
1
,
p
2
=
e
1
p
1
−
2
e
2
,
p
3
=
e
1
p
2
−
e
2
p
1
+
3
e
3
,
p
4
=
e
1
p
3
−
e
2
p
2
+
e
3
p
1
−
4
e
4
,
⋮
{\displaystyle {\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}p_{1}-2e_{2},\\p_{3}&=e_{1}p_{2}-e_{2}p_{1}+3e_{3},\\p_{4}&=e_{1}p_{3}-e_{2}p_{2}+e_{3}p_{1}-4e_{4},\\&{}\ \ \vdots \end{aligned}}}
in general, have
p
k
(
x
1
,
…
,
x
n
)
=
(
−
1
)
k
−
1
k
e
k
(
x
1
,
…
,
x
n
)
+
∑
i
=
1
k
−
1
(
−
1
)
k
−
1
+
i
e
k
−
i
(
x
1
,
…
,
x
n
)
p
i
(
x
1
,
…
,
x
n
)
,
{\displaystyle p_{k}(x_{1},\ldots ,x_{n})=(-1)^{k-1}ke_{k}(x_{1},\ldots ,x_{n})+\sum _{i=1}^{k-1}(-1)^{k-1+i}e_{k-i}(x_{1},\ldots ,x_{n})p_{i}(x_{1},\ldots ,x_{n}),}
valid n ≥ 1 , k ≥ 1.
also, 1 has
p
k
(
x
1
,
…
,
x
n
)
=
∑
i
=
k
−
n
k
−
1
(
−
1
)
k
−
1
+
i
e
k
−
i
(
x
1
,
…
,
x
n
)
p
i
(
x
1
,
…
,
x
n
)
,
{\displaystyle p_{k}(x_{1},\ldots ,x_{n})=\sum _{i=k-n}^{k-1}(-1)^{k-1+i}e_{k-i}(x_{1},\ldots ,x_{n})p_{i}(x_{1},\ldots ,x_{n}),}
for k > n ≥ 1.
application roots of polynomial
the polynomial roots xi may expanded as
∏
i
=
1
n
(
x
−
x
i
)
=
∑
k
=
0
n
(
−
1
)
n
−
k
e
n
−
k
x
k
,
{\displaystyle \prod _{i=1}^{n}\left(x-x_{i}\right)=\sum _{k=0}^{n}(-1)^{n-k}e_{n-k}x^{k},}
where coefficients
e
k
(
x
1
,
…
,
x
n
)
{\displaystyle e_{k}(x_{1},\ldots ,x_{n})}
symmetric polynomials defined above. given power sums of roots
p
k
(
x
1
,
…
,
x
n
)
=
∑
i
=
1
n
x
i
k
,
{\displaystyle p_{k}(x_{1},\ldots ,x_{n})=\sum _{i=1}^{n}x_{i}^{k},}
the coefficients of polynomial roots
x
1
,
…
,
x
n
{\displaystyle x_{1},\ldots ,x_{n}}
may expressed recursively in terms of power sums as
e
0
=
1
,
−
e
1
=
−
p
1
,
e
2
=
1
2
(
e
1
p
1
−
p
2
)
,
−
e
3
=
−
1
3
(
e
2
p
1
−
e
1
p
2
+
p
3
)
,
e
4
=
1
4
(
e
3
p
1
−
e
2
p
2
+
e
1
p
3
−
p
4
)
,
⋮
{\displaystyle {\begin{aligned}e_{0}&=1,\\-e_{1}&=-p_{1},\\e_{2}&={\frac {1}{2}}(e_{1}p_{1}-p_{2}),\\-e_{3}&=-{\frac {1}{3}}(e_{2}p_{1}-e_{1}p_{2}+p_{3}),\\e_{4}&={\frac {1}{4}}(e_{3}p_{1}-e_{2}p_{2}+e_{1}p_{3}-p_{4}),\\&{}\ \ \vdots \end{aligned}}}
formulating polynomials in way useful in using method of delves , lyness find zeros of analytic function.
application characteristic polynomial of matrix
when polynomial above characteristic polynomial of matrix (in particular when companion matrix of polynomial), roots
x
i
{\displaystyle x_{i}}
eigenvalues of matrix, counted algebraic multiplicity. positive integer k, matrix has eigenvalues powers xi, , each eigenvalue
x
i
{\displaystyle x_{i}}
of contributes multiplicity of eigenvalue xi of a. coefficients of characteristic polynomial of given elementary symmetric polynomials in powers xi. in particular, sum of xi, k-th power sum sk of roots of characteristic polynomial of a, given trace:
s
k
=
tr
(
a
k
)
.
{\displaystyle s_{k}=\operatorname {tr} (a^{k})\,.}
the newton identities relate traces of powers coefficients of characteristic polynomial of a. using them in reverse express elementary symmetric polynomials in terms of power sums, can used find characteristic polynomial computing powers , traces.
this computation requires computing traces of matrix powers , solving triangular system of equations. both can done in complexity class nc (solving triangular system can done divide-and-conquer). therefore, characteristic polynomial of matrix can computed in nc. cayley–hamilton theorem, every matrix satisfies characteristic polynomial, , simple transformation allows find adjugate matrix in nc.
rearranging computations efficient form leads faddeev–leverrier algorithm (1840), fast parallel implementation of due l. csanky (1976). disadvantage requires division integers, in general field should have characteristic, 0.
relation galois theory
for given n, elementary symmetric polynomials ek(x1,…,xn) k = 1,…, n form algebraic basis space of symmetric polynomials in x1,…. xn: every polynomial expression in xi invariant under permutations of variables given polynomial expression in elementary symmetric polynomials, , expression unique equivalence of polynomial expressions. general fact known fundamental theorem of symmetric polynomials, , newton s identities provide explicit formulae in case of power sum symmetric polynomials. applied monic polynomial
t
n
+
∑
k
=
1
n
(
−
1
)
k
a
k
t
n
−
k
{\displaystyle \textstyle t^{n}+\sum _{k=1}^{n}(-1)^{k}a_{k}t^{n-k}}
coefficients ak considered free parameters, means every symmetric polynomial expression s(x1,…,xn) in roots can expressed instead polynomial expression p(a1,…,an) in terms of coefficients only, in other words without requiring knowledge of roots. fact follows general considerations in galois theory (one views ak elements of base field roots in extension field galois group permutes them according full symmetric group, , field fixed under elements of galois group base field).
the newton identities permit expressing elementary symmetric polynomials in terms of power sum symmetric polynomials, showing symmetric polynomial can expressed in power sums. in fact first n power sums form algebraic basis space of symmetric polynomials.
Comments
Post a Comment