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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формулировка тождеств[править | править код]

Для переменных и для рассмотрим суммы -тых степеней этих переменных:

Обозначим также через элементарные симметрические многочлены. Многочлен представляет собой сумму всех возможных произведений разных переменных, в частности

Тогда тождества Ньютона могут быть записаны следующим образом:

для всех . В частности, для

Для нескольких первых значений получим:

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

Способы доказательства[править | править код]

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

Ниже мы обозначаем количество переменных через , а номер тождества (количество слагаемых в сумме в правой части) через .

Через специальный случай [править | править код]

По определению,

Следовательно, при имеем

Суммируя по всем , получаем

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

Далее всё выводится из этого факта. При тождество очевидным образом получается из присваивания в тождестве для

Пусть теперь . Обозначим через и соответственно левую и правую части тождества. Из выполнения тождества при следует, что

Однако из этого следует, что разность представима в виде для любого (если бы не была, то при каких-то разность была бы ненулевой и одно из равенств, обозначенных выше, не выполнялось бы). Следовательно, разность представима в виде , однако это невозможно так как полная степень и и равна .

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

Через формальные степенные ряды[править | править код]

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

Обозначая , получаем .

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

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

Через телескопический ряд[править | править код]

Пусть фиксировано некоторое . Обозначим через сумму всех одночленов, состоящих из различных переменных, одна из которых входит в одночлен со степенью , а все другие - со степенью 1. Такие одночлены естественным образом возникают в произведении (переменные со степенью "приходят" из полинома , а остальные, входящие в одночлен с первой степенью - из ).

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

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

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

Связанные тождества[править | править код]

Прямые представления элементарных симметрических многочленов степенными суммами[править | править код]

Раскрывая явно выражение через , получим представления

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

где - многочлен Белла. Такое представление, в частности, приводит к следующему тождеству производящих функций:

Прямое представление степенных сумм через элементарные симметрические многочлены[править | править код]

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

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

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

Приложения[править | править код]

Приложения к корням многочленов[править | править код]

Многочлен с корнями может быть представлен как

,

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

Приложения к характеристическим многочленам матриц[править | править код]

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

Рассмотрим характеристический многочлен некоторой матрицы . Его корни являются собственными числами этой матрицы (каждый корень представлен со своей кратностью). Тогда коэффициенты характеристического многочлена выражаются через симметрические многочлены .

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

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

  • вычисление степеней матрицы и их следа
  • решение системы линейных уравнений с треугольной матрицей

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

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

Приложения к тригонометрическим суммам[править | править код]

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

Примечания[править | править код]

  • Tignol, Jean-Pierre. Galois' theory of algebraic equations. — Singapore : World Scientific, 2001. — ISBN 978-981-02-4541-2.
  • Combinatorial species and tree-like structures. — Cambridge : Cambridge University Press, 1998. — ISBN 978-0-521-57323-8.
  • Cameron, Peter J. Permutation Groups. — Cambridge : Cambridge University Press, 1999. — ISBN 978-0-521-65378-7.
  • Cox, David; Little, John, and O'Shea, Donal. Ideals, Varieties, and Algorithms. — New York : Springer-Verlag, 1992. — ISBN 978-0-387-97847-5.
  • Eppstein, D.; Goodrich, M. T. (2007). "Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters". Algorithms and Data Structures, 10th International Workshop, WADS 2007: 637–648, Springer-Verlag, Lecture Notes in Computer Science 4619. 
  • Littlewood, D. E. The theory of group characters and matrix representations of groups. — Oxford : Oxford University Press, 1950. — P. viii+310. — ISBN 0-8218-4067-3.
  • Macdonald, I. G. Symmetric functions and Hall polynomials. — Oxford : The Clarendon Press, Oxford University Press, 1979. — P. viii+180. — ISBN 0-19-853530-9.
  • Macdonald, I. G. Symmetric functions and Hall polynomials. — Second. — New York : Oxford Science Publications. The Clarendon Press, Oxford University Press, 1995. — P. x+475. — ISBN 0-19-853489-2.
  • Mead, D.G. (1992). «Newton's Identities». The American Mathematical Monthly (Mathematical Association of America) 99 (8): 749–751. DOI:10.2307/2324242.
  • Stanley, Richard P. Enumerative Combinatorics, Vol. 2. — Cambridge University Press, 1999. — ISBN (hardback). (paperback).