Тождества Ньютона (Mk';yvmfg U,Zmkug)

Перейти к навигации Перейти к поиску

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

Формулировка тождеств

[править | править код]

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

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

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

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

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

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

Способы доказательства

[править | править код]

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

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

Через специальный случай

[править | править код]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[править | править код]

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

[править | править код]

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

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

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

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

[править | править код]

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

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

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

Приложения

[править | править код]

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

,

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

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

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

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

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

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

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

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

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

Примечания

[править | править код]
  • Tignol, Jean-Pierre. Galois' theory of algebraic equations (неопр.). — Singapore: World Scientific, 2001. — ISBN 978-981-02-4541-2.
  • Bergeron, F.; Labelle, G.; Leroux, P. 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. Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637—648. arXiv:0704.3313. Bibcode:2007arXiv0704.3313E.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  • 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. — (Oxford Mathematical Monographs). — 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. — (Oxford Mathematical Monographs). — ISBN 0-19-853489-2.
  • Mead, D.G. Newton's Identities (англ.) // The American Mathematical Monthly : journal. — Mathematical Association of America, 1992. — Vol. 99, no. 8. — P. 749—751. — doi:10.2307/2324242. — JSTOR 2324242.
  • Stanley, Richard P. Enumerative Combinatorics, Vol. 2 (неопр.). — Cambridge University Press, 1999. — ISBN 0-521-56069-1.
  • Прасолов В.В. Многочлены. — 3-е изд., испр. — М.: МЦНМО, 2003. — 336 с. — ISBN 5-94057-077-1