WikiSort.ru - Не сортированное

Через специальный случай ${\displaystyle k=n}$

По определению, ${\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})}$ . Вычисение коэффициентов многочлена, таким образом, сводится к двум этапам6

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

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

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

Приложения к тригонометрическим суммам

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