Личности Ньютона

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

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

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

Пусть x ₁ , ..., x _n — переменные, для k ≥ 1 обозначим p _k ( x ₁ , ..., x _n ) k -й сумму степени :

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

а для k ≥ 0 обозначим через ( _ek x 1 _, ..., x _n ) элементарный симметричный полином (то есть сумму всех различных произведений k различных переменных), поэтому

${\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})&=\sum _{1\leq i<j\leq n}x_{i}x_{j},\\&\;\;\vdots \\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}}$

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

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

справедливо для всех n ≥ k ≥ 1 .

Кроме того, у одного есть

$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 > n ≥ 1 .

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

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

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

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

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

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

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

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

справедливо для всех n ≥ k ≥ 1.

Кроме того, у одного есть

$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 > n ≥ 1.

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

Полином с корнями x _i можно разложить как

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

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

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

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

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

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

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

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

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

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

Это вычисление требует вычисления следов степеней матрицы. $\mathbf {A} ^{k}$ и решение треугольной системы уравнений. И то, и другое можно выполнить в классе сложности NC (решение треугольной системы можно выполнить методом «разделяй и властвуй»). Следовательно, характеристический полином матрицы можно вычислить в NC. По теореме Кэли-Гамильтона каждая матрица удовлетворяет своему характеристическому многочлену, а простое преобразование позволяет найти сопряженную матрицу в NC.

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

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

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

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

Родственные личности

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

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

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

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

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

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

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

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

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

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

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

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

и так далее. Общую формулу удобно выразить как

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

где B _n — полный экспоненциальный полином Белла . Это выражение также приводит к следующему тождеству для производящих функций:

$\sum _{k=0}^{\infty }e_{k}\,t^{k}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k+1}}{k}}p_{k}\,t^{k}\right).$

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

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

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

${\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_{k}&=\sum _{m_{1}+2m_{2}+\cdots +km_{k}=k \atop m_{1}\geq 0,\ldots ,m_{k}\geq 0}\prod _{i=1}^{k}{\frac {p_{i}^{m_{i}}}{m_{i}!\,i^{m_{i}}}}\end{aligned}}$

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

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

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

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

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

По аналогии с выводом производящей функции $e_{n}$, мы также можем получить производящую функцию $h_{n}$, через суммы степеней, как:

$\sum _{k=0}^{\infty }h_{k}\,t^{k}=\exp \left(\sum _{k=1}^{\infty }{\frac {p_{k}}{k}}\,t^{k}\right).$

Таким образом, эта производящая функция представляет собой плетистическую экспоненту $p_{1}t=(x_{1}+\cdots +x_{n})t$.

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

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

${\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 году (то есть раньше Ньютона).

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

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

Это удобно сформулировать в терминах обычных полиномов Белла как

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

или, что эквивалентно, как производящая функция :

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

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

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

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

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

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

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

и так далее. Если не считать замены каждого e _i соответствующим hi _, единственное изменение по отношению к предыдущему семейству тождеств заключается в знаках слагаемых, которые в данном случае зависят только от числа присутствующих факторов: знака моном ${\textstyle \prod _{i=1}^{l}h_{i}^{m_{i}}}$ есть −(−1) ^{м1 + м2 ₂ + м3 ₊ ...} . В частности, здесь также применимо приведенное выше описание абсолютного значения коэффициентов.

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

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

Выражения как определители

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

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

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

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

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

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

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

Вывод тождеств

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

Из частного случая n = k

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

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

следующее. Замена x _j на t дает

$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 дает

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

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

Сравнение коэффициентов в ряду

вывод можно получить путем вычислений в кольце формальных степенных рядов R [[ t ]], где R — Z [ x1 _Другой ,..., xn _] , кольце многочленов от n переменных x1 _, ... , x _n по целым числам.

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

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

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

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

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

Замена сторон местами и выражение a _i в виде элементарных симметричных многочленов, которые они обозначают, дает тождество.

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

Формально дифференцируем обе части по t , а затем (для удобства) умножаем на t , чтобы получить

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

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

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

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

$(-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 и определите симметричную функцию r ( i ) для 2 ⩽ i ⩽ k как сумму всех различных мономов степени k, полученных умножением одной переменной, возведенной в степень i, на k − i различных других переменных (это — мономиальная симметричная функция m _γ , где γ — форма крючка ( i ,1,1,...,1)). В частности р ( k ) знак равно п _k ; для r (1) описание сводилось бы к описанию , _ek но этот случай был исключен, поскольку здесь мономы больше не имеют какой-либо выделенной переменной. Все продукты p _i e _{k − i} могут быть выражены через r ( j ), причем первый и последний случай являются несколько особыми. У одного есть

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

поскольку каждое произведение терминов слева, включающее различные переменные, вносит вклад в r ( i ), а те, в которых переменная из p _i уже встречается среди переменных термина из ek _{вносят − i,} вклад в r ( i + 1), и все члены справа получаются таким образом ровно один раз. Для i = k умножаем на e0 ₌ 1, что тривиально дает

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

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

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

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

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

Краткое комбинаторное доказательство тождеств Ньютона дано в (Zeilberger, 1984).

См. также

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

Ссылки

• Тиньоль, Жан-Пьер (2001). Теория Галуа алгебраических уравнений . Сингапур: World Scientific. ISBN  978-981-02-4541-2 .
• Бержерон, Ф.; Лабелль, Г. и Леру, П. (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, Конспекты лекций по информатике 4619. стр. 637–648. arXiv : 0704.3313 . Бибкод : 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). Симметричные функции и полиномы Холла . Оксфордские математические монографии (второе изд.). Нью-Йорк: Оксфордские научные публикации. Кларендон Пресс, Издательство Оксфордского университета. п. х+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. ISBN  978-0-387-82445-1 .
• Такер, Алан (1980). Прикладная комбинаторика (5/е изд.). Нью-Йорк: Уайли. ISBN  978-0-471-73507-6 .

Внешние ссылки

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