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

Соотношения между степенными суммами и элементарными симметричными функциями

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

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

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

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

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

и для k  ≥ 0 обозначим через e _k ( x ₁ , ..., x _n ) элементарный симметрический многочлен (то есть сумму всех различных произведений 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})&=\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}}}$

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

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

справедливо для всех n ≥ 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 > n ≥ 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}}}$

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

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

и так далее; здесь левые части никогда не обращаются в ноль. Эти уравнения позволяют рекурсивно выразить e _i через p _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}),}$

справедливо для всех n  ≥ 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  >  n  ≥ 1.

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

Многочлен с корнями x _i можно разложить как

${\displaystyle \prod _{i=1}^{n}(x-x_{i})=\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 \mathbf {A} }$ ${\displaystyle \mathbf {A} }$ ${\displaystyle x_{i}}$ ${\displaystyle k}$ ${\displaystyle \mathbf {A} ^{k}}$ ${\displaystyle x_{i}^{k}}$ ${\displaystyle x_{i}}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle x_{i}^{k}}$ ${\displaystyle \mathbf {A} ^{k}}$ ${\displaystyle \mathbf {A} ^{k}}$ ${\displaystyle x_{i}^{k}}$ ${\displaystyle x_{i}^{k}}$ ${\displaystyle k}$ ${\displaystyle p_{k}}$ ${\displaystyle \mathbf {A} }$

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

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

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

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

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

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

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

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

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

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

Обозначая через h _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_{k}={\frac {(-1)^{k}}{k!}}B_{k}(-p_{1},-1!\,p_{2},-2!\,p_{3},\ldots ,-(k-1)!\,p_{k}),}$

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

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

Применительно к моническому многочлену эти формулы выражают коэффициенты через степенные суммы корней: заменим каждый e _i на a _i и каждый p _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_{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}}}$

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

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

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

${\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 e_{n}}$ ${\displaystyle h_{n}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из особого случаян = к

Можно получить 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}}$

следующим образом. Подстановка x _j вместо t дает

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

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

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

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

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

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

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

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

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

Меняя стороны местами и выражая a _i как элементарные симметричные многочлены, которые они обозначают, получаем тождество

${\displaystyle \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 , чтобы получить

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

• Тиньоль, Жан-Пьер (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, Lecture Notes in Computer Science 4619. стр. 637–648. arXiv : 0704.3313 . Bibcode : 2007arXiv0704.3313E.
• Литтлвуд, Д. Э. (1950). Теория групповых характеров и матричных представлений групп . Оксфорд: Oxford University Press. viii+310. ISBN 0-8218-4067-3.
• Macdonald, IG (1979). Симметричные функции и многочлены Холла . Oxford Mathematical Monographs. Oxford: The Clarendon Press, Oxford University Press. viii+180. ISBN 0-19-853530-9. МР  0553598.
• Macdonald, IG (1995). Симметричные функции и многочлены Холла . Oxford Mathematical Monographs (Второе изд.). Нью-Йорк: Oxford Science Publications. The Clarendon Press, Oxford University Press. стр. x+475. ISBN 0-19-853489-2. МР  1354144.
• Мид, Д. Г. (1992). «Тождества Ньютона». The American Mathematical Monthly . 99 (8). Математическая ассоциация Америки: 749–751. doi :10.2307/2324242. JSTOR  2324242.
• Стэнли, Ричард П. (1999). Перечислительная комбинаторика, т. 2. Cambridge University Press. ISBN 0-521-56069-1. (твердый переплет). (мягкая обложка).
• Штурмфельс, Бернд (1992). Алгоритмы в теории инвариантов . Нью-Йорк: Springer-Verlag. ISBN 978-0-387-82445-1.
• Такер, Алан (1980). Прикладная комбинаторика (5-е изд.). Нью-Йорк: Wiley. ISBN 978-0-471-73507-6.

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

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