Тождества Ньютона

По определению, ${\displaystyle \prod _{i=1}^{k}(t-x_{i})=\sum _{i=0}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k})t^{i}}$

Следовательно, при ${\displaystyle t=x_{j}}$ имеем

${\displaystyle 0=\sum _{i=0}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k}){x_{j}}^{i},\quad 1\leq j\leq k}$

Суммируя по всем ${\displaystyle j}$, получаем

${\displaystyle 0=(-1)^{k}ke_{k}(x_{1},\ldots ,x_{k})+\sum _{i=1}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k})p_{i}(x_{1},\ldots ,x_{k}),}$

Из этого выражения немедленно следует ${\displaystyle k}$-тое тождество Ньютона при ${\displaystyle k}$ переменных. Поскольку оно является тождеством между симметрическими однородными многочленами.

Далее всё выводится из этого факта. При ${\displaystyle n<k}$ тождество очевидным образом получается из присваивания ${\displaystyle x_{n+1}=x_{n+2}=\dots =x_{k}=0}$ в тождестве для ${\displaystyle n=k}$

Пусть теперь ${\displaystyle n=k+1}$. Обозначим через ${\displaystyle f(x_{1},\dots ,x_{n})}$ и ${\displaystyle g(x_{1},\dots ,x_{n})}$ соответственно левую и правую части тождества. Из выполнения тождества при ${\displaystyle n=k}$ следует, что

${\displaystyle {\begin{aligned}&f(0,x_{2},\dots ,x_{k},x_{k+1})=g(0,x_{2},\dots ,x_{k},x_{k+1})\\&f(x_{1},0,\dots ,x_{k},x_{k+1})=g(x_{1},0,\dots ,x_{k},x_{k+1})\\&\dots \\&f(x_{1},x_{2},\dots ,0,x_{k+1})=g(x_{1},x_{2},\dots ,0,x_{k+1})\\&f(x_{1},x_{2},\dots ,x_{k},0)=g(x_{1},x_{2},\dots ,x_{k},0)\end{aligned}}}$

Однако из этого следует, что разность ${\displaystyle f-g}$ представима в виде ${\displaystyle h(x_{1},\dots ,x_{n})x_{i}}$ для любого ${\displaystyle i}$ (если бы не была, то при каких-то ${\displaystyle x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{k+1}}$ разность была бы ненулевой и одно из равенств, обозначенных выше, не выполнялось бы). Следовательно, разность ${\displaystyle f-g}$ представима в виде ${\displaystyle h(x_{1},\dots ,x_{n})x_{1}x_{2}\dots x_{k}x_{k+1}}$, однако это невозможно так как полная степень и ${\displaystyle f}$ и ${\displaystyle g}$ равна ${\displaystyle k}$.

Аналогичные рассуждения для ${\displaystyle n>k+1}$ дают индукционный переход и доказывают тождества для произвольного ${\displaystyle n}$.

Прямым раскрытием скобок можно получить, что

${\displaystyle \prod _{i=1}^{n}(t-x_{i})=\sum _{k=0}^{n}(-1)^{k}e_{k}(x_{1},\dots ,x_{n})t^{n-k}}$

${\displaystyle \prod _{i=1}^{n}(1-{\frac {x_{i}}{t}})=\sum _{k=0}^{n}(-1)^{k}e_{k}(x_{1},\dots ,x_{n}){\frac {1}{t^{k}}}}$

Обозначая ${\displaystyle s={\frac {1}{t}}}$, получаем ${\displaystyle \prod _{i=1}^{n}(1-x_{i}s)=\sum _{k=0}^{n}(-1)^{k}e_{k}(x_{1},\dots ,x_{n})s^{k}}$.

Формально дифференцируя (беря производную) по ${\displaystyle s}$ и домножая обе части на ${\displaystyle s}$, получаем

${\displaystyle {\begin{aligned}\sum _{k=0}^{n}(-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})s^{k}&=s\sum _{i=1}^{n}\left[(-x_{i})\prod \nolimits _{j\neq i}(1-x_{j}s)\right]\\&=-\left(\sum _{i=1}^{n}{\frac {x_{i}s}{1-x_{i}s}}\right)\prod \nolimits _{j=1}^{n}(1-x_{j}s)\\&=-\left[\sum _{i=1}^{n}\sum _{j=1}^{\infty }(x_{i}s)^{j}\right]\left[\sum _{\ell =0}^{n}(-1)^{\ell }e_{\ell }(x_{1},\ldots ,x_{n})s^{\ell }\right]\\&=\left[\sum _{j=1}^{\infty }p_{j}(x_{1},\ldots ,x_{n})s^{j}\right]\left[\sum _{\ell =0}^{n}(-1)^{\ell -1}e_{\ell }(x_{1},\ldots ,x_{n})s^{\ell }\right],\\\end{aligned}}}$

Так как тождественное равенство многочленов влечёт равенство всех коэффициентов, то по правилам умножения многочленов из этого напрямую следует, что

${\displaystyle (-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})=\sum _{j=1}^{k}(-1)^{k-j-1}p_{j}(x_{1},\ldots ,x_{n})e_{k-j}(x_{1},\ldots ,x_{n}),}$

Пусть фиксировано некоторое ${\displaystyle k\geq 1}$. Обозначим через ${\displaystyle r_{i}^{(k)}(x_{1},\dots ,x_{n})}$ сумму всех одночленов, состоящих из ${\displaystyle k}$ различных переменных, одна из которых входит в одночлен со степенью ${\displaystyle i}$, а все другие - со степенью 1. Такие одночлены естественным образом возникают в произведении ${\displaystyle p_{i}(x_{1},\dots ,x_{n})e_{k-i}(x_{1},\dots ,x_{n})}$ (переменные со степенью ${\displaystyle i}$ "приходят" из полинома ${\displaystyle p_{i}}$, а остальные, входящие в одночлен с первой степенью - из ${\displaystyle e_{k-i}}$).

Конкретнее, легко проверяются следующие тождества:

${\displaystyle {\begin{aligned}&p_{1}e_{k-1}=ke_{k}+r_{2}^{(k)}\\&p_{i}e_{k-i}=r_{i}^{(k)}+r_{i+1}^{(k)},&1<i<k\\&p_{k}e_{0}=p_{k}=r_{k}^{(k)}\end{aligned}}}$

Особенность первого из них обусловлена, грубо говоря, тем, что при ${\displaystyle i\geq 2}$ для одночлена ${\displaystyle x_{0}^{i}x_{1}\dots x_{k-i}}$ однозначно понятно, какая переменная взята из ${\displaystyle p_{i}}$, а какие - из ${\displaystyle e_{k-i}}$, так что каждый такой многочлен входит в произведение ${\displaystyle p_{i}e_{k-i}}$ с коэффициентом ${\displaystyle 1}$. В случае же ${\displaystyle i=1}$ многочлен ${\displaystyle x_{1},\dots ,x_{k}}$ встретится в произведении ${\displaystyle p_{1}e_{k-1}}$ ровно ${\displaystyle k}$ раз - как каждое возможное перемножение одной из переменных с остальной частью одночлена: ${\displaystyle x_{1}x_{2}\dots x_{k-1}x_{k}=x_{1}\cdot x_{2}x_{3}\dots x_{k-1}x_{k}=x_{2}\cdot x_{1}x_{3}\dots x_{k-1}x_{k}=\dots =x_{k}\cdot x_{1}x_{2}\dots x_{k-2}x_{k-1}}$. Это даёт коэффициент ${\displaystyle k}$ при ${\displaystyle e_{k}}$

Из представленных выше тождеств легко получить, что

${\displaystyle {\begin{aligned}&p_{1}e_{k-1}-p_{2}e_{k-2}+\dots +(-1)^{k-1}p_{k}=\\&=ke_{k}+r_{2}^{(k)}-\left({r_{2}^{(k)}+r_{3}^{(k)}}\right)+\left({r_{3}^{(k)}+r_{4}^{(k)}}\right)-\dots +(-1)^{k}r_{k}^{(k)}=\\&=ke_{k}+r_{2}^{(k)}-r_{2}^{(k)}-r_{3}^{(k)}+r_{3}^{(k)}+r_{4}^{(k)}-r_{4}^{(k)}\dots +(-1)^{k-1}r_{k}^{(k)}+(-1)^{k}r_{k}^{(k)}=\\&=ke_{k}\\\end{aligned}}}$

Раскрывая явно выражение ${\displaystyle e_{i}}$ через ${\displaystyle p_{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}}}$

Общая формула может быть также переписана как

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

где ${\displaystyle B_{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).}$

Аналогично, раскрывая напрямую рекуррентные выражения, можно получить, что

${\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}}}$

Первые четыре формулы были получены Альбером Жираром ещё до Ньютона, в 1629 году. Общая формула имеет следующий вид:

${\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}}.}$

Это может быть переформулировано в терминах многочленов Белла:

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

Многочлен ${\displaystyle f(x)}$ с корнями ${\displaystyle x_{1},\dots ,x_{n}}$ может быть представлен как

${\displaystyle f(x)=\prod _{i=1}^{n}\left(x-x_{i}\right)=\sum _{k=0}^{n}(-1)^{n-k}e_{n-k}x^{k},}$,

где коэффициенты ${\displaystyle e_{k}=e_{k}(x_{1},\dots ,x_{n})}$ - симметрические многочлены, определённые выше. При известных значениях степенных сумм ${\displaystyle p_{k}(x_{1},\dots ,x_{n})=\sum \limits _{i=1}^{n}{{x_{i}}^{k}}}$ коэффициенты многочлена ${\displaystyle f(x)}$ можно найти из рекуррентных формул.

Тождества Ньютона позволяют свести вычисление коэффициентов характеристического многочлена матрицы ${\displaystyle A}$ к вычислению следа различных её степеней.

Рассмотрим характеристический многочлен некоторой матрицы ${\displaystyle A}$. Его корни ${\displaystyle x_{1},\dots ,x_{n}}$ являются собственными числами этой матрицы (каждый корень представлен со своей кратностью). Тогда коэффициенты характеристического многочлена выражаются через симметрические многочлены ${\displaystyle e_{i}}$.

Для любого положительного ${\displaystyle k}$ собственными числами матрицы ${\displaystyle A^{k}}$ являются степени ${\displaystyle {x_{1}}^{k},\dots ,{x_{n}}^{k}}$. Поскольку сумма собственных чисел матрицы равна её следу, то

${\displaystyle p_{k}(x_{1},\dots ,x_{n})=tr(A^{k})}$

Следовательно, и ${\displaystyle e_{1},\dots ,e_{n}}$, и коэффициенты характеристического многочлена можно выразить линейно из ${\displaystyle tr(A),\dots ,tr(A^{n})}$. Вычисление коэффициентов многочлена, таким образом, сводится к двум этапам:

• вычисление степеней матрицы ${\displaystyle A}$ и их следа
• решение системы линейных уравнений с треугольной матрицей

Оба этапа относятся к классу сложности NC, так что задача нахождения коэффициентов характеристического многочлена тоже относится к классу NC. На этой идее основан алгоритм Фадеева-Леверье (1840).

Поскольку по теореме Гамильтона-Кэли любая матрица является корнем своего характеристического многочлена, то быстрое вычисление коэффициентов этого многочлена даёт быстрый способ нахождения обратной матрицы.

Тождества Ньютона могут использоваться при оценке рациональных тригонометрических сумм по простому модулю для однозначного нахождения частного случая интеграла Виноградова при равном количестве переменных и уравнений.