Тождества Ньютона - Newtons identities - Wikipedia

В математика, Личности Ньютона, также известный как Формулы Жирара-Ньютона, зададим отношения между двумя типами симметричные многочлены, а именно между суммы мощности и элементарные симметричные полиномы. Оценивается на корни моника многочлен п в одной переменной они позволяют выразить суммы k-го полномочия всех корней п (считая с их кратностью) через коэффициенты п, фактически не найдя этих корней. Эти личности были обнаружены Исаак Ньютон около 1666 г., очевидно, из-за незнания более ранней работы (1629 г.) Альбер Жирар. У них есть приложения во многих областях математики, в том числе Теория Галуа, теория инвариантов, теория групп, комбинаторика, а также другие приложения за пределами математики, в том числе общая теория относительности.

Математическое утверждение

Формулировка в терминах симметричных многочленов

Позволять Икс₁, ..., Икс_п - переменные, обозначим для k ≥ 1 по п_k(Икс₁, ..., Икс_п) k-го сумма мощности:

${\displaystyle p_{k}(x_{1},\ldots ,x_{n})=\sum \nolimits _{i=1}^{n}x_{i}^{k}=x_{1}^{k}+\cdots +x_{n}^{k},}$

и для k ≥ 0 обозначим через е_k(Икс₁, ..., Икс_п) элементарный симметричный многочлен (то есть сумма всех различных произведений k различные переменные), поэтому

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

Тогда тождества Ньютона можно сформулировать как

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

действительно для всех п ≥ 1 и п ≥k ≥ 1.

Также есть

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

для всех k > п ≥ 1.

Конкретно, для первых нескольких значений k:

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

Форма и справедливость этих уравнений не зависят от количества п переменных (хотя точка, где левая часть становится равной 0, имеет значение, а именно после п-й тождество), что позволяет заявить их как тождества в кольцо симметричных функций. В этом кольце

${\displaystyle {\begin{aligned}e_{1}&=p_{1},\\2e_{2}&=e_{1}p_{1}-p_{2}=p_{1}^{2}-p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+p_{3}={\tfrac {1}{2}}p_{1}^{3}-{\tfrac {3}{2}}p_{1}p_{2}+p_{3},\\4e_{4}&=e_{3}p_{1}-e_{2}p_{2}+e_{1}p_{3}-p_{4}={\tfrac {1}{6}}p_{1}^{4}-p_{1}^{2}p_{2}+{\tfrac {4}{3}}p_{1}p_{3}+{\tfrac {1}{2}}p_{2}^{2}-p_{4},\\\end{aligned}}}$

и так далее; здесь левые части никогда не обращаются в нуль. Эти уравнения позволяют рекурсивно выразить е_я с точки зрения п_k; чтобы иметь возможность сделать обратное, их можно переписать как

${\displaystyle {\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}p_{1}-2e_{2}=e_{1}^{2}-2e_{2},\\p_{3}&=e_{1}p_{2}-e_{2}p_{1}+3e_{3}=e_{1}^{3}-3e_{1}e_{2}+3e_{3},\\p_{4}&=e_{1}p_{3}-e_{2}p_{2}+e_{3}p_{1}-4e_{4}=e_{1}^{4}-4e_{1}^{2}e_{2}+4e_{1}e_{3}+2e_{2}^{2}-4e_{4},\\&{}\ \ \vdots \end{aligned}}}$

В общем, у нас есть

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

действительно для всех п ≥ 1 и п ≥k ≥ 1.

Также есть

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

для всех k > п ≥ 1.

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

Многочлен с корнями Икс_я может быть расширен как

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

где коэффициенты ${\displaystyle e_{k}(x_{1},\ldots ,x_{n})}$ - симметричные многочлены, определенные выше. суммы мощности корней

${\displaystyle p_{k}(x_{1},\ldots ,x_{n})=\sum _{i=1}^{n}x_{i}^{k},}$

коэффициенты полинома с корнями ${\displaystyle x_{1},\ldots ,x_{n}}$ можно рекурсивно выразить через степенные суммы как

${\displaystyle {\begin{aligned}e_{0}&=1,\\[4pt]-e_{1}&=-p_{1},\\[4pt]e_{2}&={\frac {1}{2}}(e_{1}p_{1}-p_{2}),\\[4pt]-e_{3}&=-{\frac {1}{3}}(e_{2}p_{1}-e_{1}p_{2}+p_{3}),\\[4pt]e_{4}&={\frac {1}{4}}(e_{3}p_{1}-e_{2}p_{2}+e_{1}p_{3}-p_{4}),\\&{}\ \ \vdots \end{aligned}}}$

Подобная формулировка полиномов полезна при использовании метода Делвеса и Лайнесса.^[1] найти нули аналитической функции.

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

Когда полином выше является характеристический многочлен из матрица А (в частности, когда А это сопутствующая матрица полинома) корни ${\displaystyle x_{i}}$ являются собственные значения матрицы, считая с их алгебраической кратностью. Для любого положительного целого числа k, матрица А^k имеет в качестве собственных значений полномочия Икс_я^k, и каждое собственное значение ${\displaystyle x_{i}}$ из А вносит свой вклад в кратность собственного значения Икс_я^k из А^k. Тогда коэффициенты характеристического полинома А^k задаются элементарными симметричными многочленами в этих силах Икс_я^k. В частности, сумма Икс_я^k, какой k-й степени сумма p_k корней характеристического многочлена А, дается его след:

${\displaystyle p_{k}=\operatorname {tr} (A^{k})\,.}$

Тождества Ньютона теперь связывают следы сил А^k коэффициентам характеристического полинома А. Используя их в обратном порядке, чтобы выразить элементарные симметричные полиномы через суммы степеней, их можно использовать для нахождения характеристического полинома путем вычисления только степеней А^k и их следы.

Это вычисление требует вычисления следов степеней матрицы А^k и решение треугольной системы уравнений. Оба могут быть выполнены в классе сложности. NC (Решить треугольную систему можно, разделяя и властвуй). Следовательно, характеристический полином матрицы может быть вычислен в NC. Посредством Теорема Кэли – Гамильтона, каждая матрица удовлетворяет своему характеристическому многочлену, и простое преобразование позволяет найти сопряженная матрица в NC.

Преобразование вычислений в эффективную форму приводит к Алгоритм Фаддеева – Леверье (1840), его быстрая параллельная реализация принадлежит L. Csanky (1976). Его недостаток в том, что он требует деления на целые числа, поэтому обычно поле должно иметь характеристику 0.

Связь с теорией Галуа

Для данного п, элементарные симметрические полиномы е_k(Икс₁,...,Икс_п) за k = 1,..., п образуют алгебраический базис пространства симметрических многочленов от Икс₁,.... Икс_п: каждое полиномиальное выражение в Икс_я который инвариантен относительно всех перестановок этих переменных, задается многочлен выражение в этих элементарных симметричных полиномах, и это выражение является уникальным с точностью до эквивалентности полиномиальных выражений. Это общий факт, известный как основная теорема симметрических многочленов, а тождества Ньютона дают явные формулы в случае степенных симметрических многочленов. Применительно к моническому многочлену ${\displaystyle \textstyle t^{n}+\sum _{k=1}^{n}(-1)^{k}a_{k}t^{n-k}}$ со всеми коэффициентами а_k рассматриваются как свободные параметры, это означает, что каждое симметричное полиномиальное выражение S(Икс₁,...,Икс_п) в его корнях можно вместо этого выразить как полиномиальное выражение п(а₁,...,а_п) только с точки зрения его коэффициентов, другими словами, не требуя знания корней. Этот факт также следует из общих соображений Теория Галуа (просматривается а_k как элементы базового поля с корнями в поле расширения, группа Галуа которого переставляет их в соответствии с полной симметричной группой, а поле, фиксированное под всеми элементами группы Галуа, является базовым полем).

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

Связанные личности

Существует ряд (семейств) идентичностей, которые, хотя их следует отличать от идентичностей Ньютона, очень тесно с ними связаны.

Вариант с использованием полных однородных симметрических многочленов

Обозначается час_k то полный однородный симметричный многочлен это сумма всех мономы степениk, полиномы степенной суммы также удовлетворяют тождествам, аналогичным тождествам Ньютона, но без каких-либо знаков минус. Выражается как личности в кольцо симметричных функций, они читают

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

справедливо для всех n ≥k ≥ 1. В отличие от тождеств Ньютона, левые части не обращаются в нуль при большихk, а в правых частях все больше ненулевых членов. Для первых нескольких значений k, надо

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

Эти соотношения могут быть обоснованы аргументом, аналогичным рассуждению при сравнении коэффициентов в степенных рядах, приведенных выше, в данном случае на основе тождества производящей функции

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

Доказательства тождеств Ньютона, подобные приведенным ниже, нелегко адаптировать для доказательства этих вариантов этих тождеств.

Выражение элементарных симметричных многочленов через степенные суммы

Как уже упоминалось, тождества Ньютона можно использовать для рекурсивного выражения элементарных симметрических многочленов в терминах степенных сумм. Для этого необходимо ввести целочисленные знаменатели, поэтому это можно сделать в кольце Λ_Q симметричных функций с рациональными коэффициентами:

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

и так далее.^[2] Общую формулу удобно записать как

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

где B_п полная экспонента Полином Белла. Это выражение также приводит к следующему тождеству для генерации функций:

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

Применительно к моническому многочлену эти формулы выражают коэффициенты через степенные суммы корней: замените каждый е_я к а_я и каждый п_k к s_k.

Выражение полных однородных симметрических многочленов через степенные суммы

Аналогичные соотношения, включающие полные однородные симметрические многочлены, могут быть развиты аналогичным образом, давая уравнения

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

и так далее, в которых есть только знаки плюса. В терминах полного полинома Белла

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

Эти выражения в точности соответствуют индекс цикла полиномы от симметричные группы, если интерпретировать степенные суммы п_я как неопределенные: коэффициент в выражении для час_k любого монома п₁^м₁п₂^м₂...п_л^м_л равна доле всех перестановок k который имеет м₁ фиксированные точки, м₂ циклы длины 2, ..., и м_л циклы длины л. Явно этот коэффициент можно записать как ${\displaystyle 1/N}$ куда ${\displaystyle N=\prod _{i=1}^{l}(m_{i}!\,i^{m_{i}})}$; это N это количество перестановок, коммутирующих с любой данной перестановкойπ данного типа цикла. Выражения для элементарных симметричных функций имеют коэффициенты с одинаковым модулем, но знак равен знакуπ, а именно (−1)^{м₂+м₄+...}.

Это можно доказать, рассмотрев следующий индуктивный шаг:

${\displaystyle {\begin{aligned}mf(m;m_{1},\ldots ,m_{n})&=f(m-1;m_{1}-1,\ldots ,m_{n})+\cdots +f(m-n;m_{1},\ldots ,m_{n}-1)\\m_{1}\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}+\cdots +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}}}$

Выражение степенных сумм через элементарные симметричные полиномы

Можно также использовать тождества Ньютона для выражения степенных сумм в терминах симметричных многочленов, при этом знаменатели не вводятся:

${\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 г. (то есть до Ньютона).^[3]

Общая формула (для всех неотрицательных целых чисел м) является:

${\displaystyle p_{m}=(-1)^{m}m\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,\ldots ,r_{m}\geq 0}{\frac {(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},\ldots ,-e_{m-k+1}),}$

или эквивалентно как производящая функция:^[4]

${\displaystyle {\begin{aligned}\sum _{k=1}^{\infty }(-1)^{k-1}p_{k}{\frac {t^{k}}{k}}&=\ln \left(1+e_{1}t+e_{2}t^{2}+e_{3}t^{3}+\cdots \right)\\&=e_{1}t-{\frac {1}{2}}\left(e_{1}^{2}-2e_{2}\right)t^{2}+{\frac {1}{3}}\left(e_{1}^{3}-3e_{1}e_{2}+3e_{3}\right)t^{3}+\cdots ,\end{aligned}}}$

что аналогично Полином Белла экспоненциальный производящая функция, указанная в предыдущий подраздел.

Приведенная выше формула множественного суммирования может быть доказана с помощью следующего индуктивного шага:

${\displaystyle {\begin{aligned}f(m;\;r_{1},\ldots ,r_{n})={}&f(m-1;\;r_{1}-1,\cdots ,r_{n})+\cdots +f(m-n;\;r_{1},\ldots ,r_{n}-1)\\[8pt]={}&{\frac {1}{(r_{1}-1)!\cdots r_{n}!}}(m-1)(r_{1}+\cdots +r_{n}-2)!+\cdots \\&\cdots +{\frac {1}{r_{1}!\cdots (r_{n}-1)!}}(m-n)(r_{1}+\cdots +r_{n}-2)!\\[8pt]={}&{\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]!\\[8pt]={}&{\frac {1}{r_{1}!\cdots r_{n}!}}\left[m(r_{1}+\cdots +r_{n})-m\right]\left[r_{1}+\cdots +r_{n}-2\right]!\\[8pt]={}&{\frac {m(r_{1}+\cdots +r_{n}-1)!}{r_{1}!\cdots r_{n}!}}\end{aligned}}}$

Выражение степенных сумм через полные однородные симметрические многочлены

Наконец, можно использовать различные тождества, включающие полные однородные симметрические многочлены, аналогично для выражения степенных сумм через них:

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

и так далее. Помимо замены каждого е_я соответствующими час_я, единственное изменение по сравнению с предыдущим семейством тождеств заключается в знаках членов, которые в данном случае зависят только от количества присутствующих факторов: знак одночлена ${\displaystyle \Pi _{i=1}^{l}h_{i}^{m_{i}}}$ это - (- 1)^{м₁+м₂+м₃+...}. В частности, здесь также применимо приведенное выше описание абсолютных значений коэффициентов.

Общая формула (для всех неотрицательных целых чисел м) является:

${\displaystyle p_{m}=-\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,\ldots ,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}}}$

Выражения как детерминанты

Можно получить явные формулы для приведенных выше выражений в виде определителей, рассматривая первые п тождеств Ньютона (или его эквивалентов для полных однородных многочленов) как линейные уравнения, в которых элементарные симметричные функции известны, а степенные суммы неизвестны (или наоборот), и применяются Правило Крамера найти решение последнего неизвестного. Например, взяв тождества Ньютона в форме

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

мы считаем ${\displaystyle p_{1},-p_{2},p_{3},\ldots ,(-1)^{n}p_{n-1}}$ и ${\displaystyle p_{n}}$ как неизвестные, и решите для последнего, давая

${\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}\\[7pt]={(-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}}\\[7pt]={}&{\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}}}$

Решение для ${\displaystyle e_{n}}$ вместо ${\displaystyle p_{n}}$ аналогично аналогичным вычислениям для полных однородных симметрических многочленов; в каждом случае детали несколько сложнее, чем окончательные результаты (Macdonald 1979, стр. 20):

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

Обратите внимание, что использование определителей приводит к тому, что формула для ${\displaystyle h_{n}}$ имеет дополнительные знаки минус по сравнению с ${\displaystyle e_{n}}$, в то время как для приведенной ранее развернутой формы ситуация обратная. Как отмечено в (Littlewood 1950, p. 84), можно альтернативно получить формулу для ${\displaystyle h_{n}}$ взяв постоянный матрицы для ${\displaystyle e_{n}}$ вместо определителя, и в более общем смысле выражение для любого Полином Шура можно получить, взяв соответствующий имманентный этой матрицы.

Вывод идентичностей

Каждое из тождеств Ньютона легко проверить элементарной алгеброй; однако их действительность в целом требует доказательства. Вот несколько возможных выводов.

Из особого случая п = k

Можно получить kтождество Ньютона в k переменные путем подстановки в

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

следующее. Подстановка Икс_j за т дает

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

Подводя итог всему 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}),}$

где условия для я = 0 были исключены из суммы, поскольку п₀ (обычно) не определяется. Это уравнение сразу дает kтождество Ньютона в k переменные. Поскольку это тождество симметричных многочленов (однородных) степени k, его справедливость для любого числа переменных следует из его справедливости для k переменные. Конкретно тождества в п < k переменные можно вывести, установив k − п переменные к нулю. В kтождество Ньютона в п > k переменные содержат больше членов с обеих сторон уравнения, чем одно в k переменных, но его достоверность будет гарантирована, если коэффициенты любого одночлена совпадают. Поскольку ни один отдельный моном не включает в себя более чем k переменных, моном переживет замену нуля на некоторый набор п − k (другие) переменные, после которых равенство коэффициентов возникает в kтождество Ньютона в k (правильно подобранные) переменные.

Сравнение коэффициентов в серии

Другой вывод может быть получен вычислениями в кольце формальный степенной ряд р[[т]], куда р является Z[Икс₁,..., Икс_п], кольцо многочленов в п переменные Икс₁,..., Икс_п над целыми числами.

Начиная снова с основного отношения

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

и «перевернуть многочлены», подставив 1 /т за т а затем умножая обе части на т^п убрать отрицательные силы т, дает

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

(приведенное выше вычисление должно выполняться в поле дробей из р[[т]]; в качестве альтернативы, идентичность можно получить, просто оценив продукт слева)

Поменять местами и выразить а_я в качестве элементарных симметричных многочленов, которые они обозначают, дает тождество

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

Один формально различает обе стороны по отношению к т, а затем (для удобства) умножается на т, чтобы получить

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

где полином в правой части впервые был переписан как рациональная функция чтобы иметь возможность исключить произведение из суммирования, дробь в слагаемом разлагалась как ряд т, используя формулу

${\displaystyle {\frac {X}{1-X}}=X+X^{2}+X^{3}+X^{4}+X^{5}+\cdots ,}$

и, наконец, коэффициент каждого т ^j был собран, дав энергетическую сумму. (Сериал в т является формальным степенным рядом, но может также рассматриваться как расширение ряда для т достаточно близко к 0, для тех, кому это удобнее; на самом деле здесь не интересует функция, а только коэффициенты ряда.) Сравнение коэффициентов т^k с обеих сторон получается

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

что дает k-я тождество Ньютона.

Как телескопическая сумма симметричных функциональных тождеств

Следующий вывод, приведенный в основном в (Mead, 1992), сформулирован в кольцо симметричных функций для наглядности (все тождества не зависят от количества переменных). Исправить некоторые k > 0, и определим симметричную функцию р(я) для 2 ≤я ≤ k как сумма всех различных мономы степени k полученный умножением одной переменной в степения с k − я различные другие переменные (это мономиальная симметричная функция м_γ где γ - форма крючка (я, 1,1, ..., 1)). Особенно р(k) = п_k; за р(1) описание будет соответствовать описанию е_k, но этот случай был исключен, так как здесь мономы больше не имеют выделенной переменной. Все продукты п_яе_k−я можно выразить через р(j), причем первый и последний случай несколько особенный. Надо

${\displaystyle p_{i}e_{k-i}=r(i)+r(i+1)\quad {\text{for }}1<i<k}$

поскольку каждое произведение терминов слева, включающих различные переменные, способствует р(я), а те, где переменная из п_я уже встречается среди переменных члена из е_k−я способствует р(я + 1), и все члены справа так получаются ровно один раз. За я = k один умножается на е₀ = 1, что дает тривиально

${\displaystyle p_{k}e_{0}=p_{k}=r(k).}$

Наконец продукт п₁е_k−1 за я = 1 дает вклады в р(я + 1) = р(2) как для других значений я < k, но остальные вклады производят k умножить на каждый моном из е_k, поскольку любая из переменных может происходить из фактора п₁; таким образом

${\displaystyle p_{1}e_{k-1}=ke_{k}+r(2).}$

В k-я тождество Ньютона теперь получается взятием альтернативной суммы этих уравнений, в которой все члены вида р(я) отменяет.

Комбинаторное доказательство

Короткое комбинаторное доказательство идентичностей Ньютона приведено в (Zeilberger, 1984)^[5]

Смотрите также

• Симметричный полином по степенной сумме
• Элементарный симметричный многочлен
• Симметричная функция
• Жидкие растворы, статья, в которой дается применение тождеств Ньютона к вычислению характеристического многочлена Тензор Эйнштейна в случае идеальная жидкость, и аналогичные статьи о других типах точные решения в общей теории относительности.

Рекомендации

1. Дельвес, Л. М. (1967). «Численный метод нахождения нулей аналитической функции». Математика вычислений. 21 (100): 543–560. Дои:10.2307/2004999. JSTOR  2004999.
2. N.b., коэффициенты при взвешивании продуктов в сумме, заданной тождеством выше, связаны с M2 числа в разделе 26.4 DLMF и / или коэффициенты, участвующие в разложениях Формула Фаа ди Бруно
3. Тиньоль, Жан-Пьер (2004). Теория Галуа алгебраических уравнений (Перепечатано под ред.). Ривер Эдж, штат Нью-Джерси: World Scientific. стр.37 –38. ISBN  981-02-4541-6.
4. Вайсштейн, Эрик В. «Симметричный полином». MathWorld.
5. Зейлбергер, Дорон (1984). «Комбинаторное доказательство тождества Ньютона». Дискретная математика. 49 (3): 319. Дои:10.1016 / 0012-365X (84) 90171-7.

• Тиньоль, Жан-Пьер (2001). Теория Галуа алгебраических уравнений. Сингапур: World Scientific. ISBN  978-981-02-4541-2.
• Bergeron, F .; Labelle, G. & Leroux, P. (1998). Комбинаторные виды и древовидные структуры. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-57323-8.
• Кэмерон, Питер Дж. (1999). Группы перестановок. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-65378-7.
• Кокс, Дэвид; Литтл, Джон и О'Ши, Донал (1992). Идеалы, разновидности и алгоритмы. Нью-Йорк: Springer-Verlag. ISBN  978-0-387-97847-5.
• Эппштейн, Д.; Гудрич, М. Т. (2007). «Компактная идентификация отставших в потоках данных туда и обратно с помощью идентификаторов Ньютона и обратимых фильтров Блума». Алгоритмы и структуры данных, 10-й международный семинар, WADS 2007. Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637–648. arXiv:0704.3313. Bibcode:2007arXiv0704.3313E.
• Литтлвуд, Д. Э. (1950). Теория групповых характеров и матричные представления групп. Оксфорд: Издательство Оксфордского университета. viii + 310. ISBN  0-8218-4067-3.
• Макдональд, И. Г. (1979). Симметричные функции и многочлены Холла. Оксфордские математические монографии. Оксфорд: Clarendon Press, Oxford University Press. viii + 180. ISBN  0-19-853530-9. МИСТЕР  0553598.
• Макдональд, И. Г. (1995). Симметричные функции и многочлены Холла. Оксфордские математические монографии (второе изд.). Нью-Йорк: Oxford Science Publications. Clarendon Press, Oxford University Press. п. х + 475. ISBN  0-19-853489-2. МИСТЕР  1354144.
• Мид, Д. (1992). «Тождества Ньютона». Американский математический ежемесячник. Математическая ассоциация Америки. 99 (8): 749–751. Дои:10.2307/2324242. JSTOR  2324242.
• Стэнли, Ричард П. (1999). Перечислительная комбинаторика, Vol. 2. Издательство Кембриджского университета. ISBN  0-521-56069-1. (переплет). (мягкая обложка).
• Штурмфельс, Бернд (1992). Алгоритмы в теории инвариантов. Нью-Йорк: Springer-Verlag. ISBN  978-0-387-82445-1.
• Такер, Алан (1980). Прикладная комбинаторика (5 / е изд.). Нью-Йорк: Вили. ISBN  978-0-471-73507-6.

внешняя ссылка

• Формулы Ньютона – Жирара на MathWorld
• Матричное доказательство тождественности Ньютона в математическом журнале
• Заявка на количество настоящих корней
• Комбинаторное доказательство тождеств Ньютона Дорон Зейлбергер