Введение

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

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

Когда указанный выше многочлен является характеристическим многочленом матрицы (в частности, когда является компаньон-матрицей этого многочлена), корни являются собственными значениями матрицы, с учетом их алгебраической кратности. Для любого положительного целого числа , матрица имеет в качестве собственных значений степени , и каждое собственное значение of вносит свой вклад в кратность собственного значения of в . Тогда коэффициенты характеристического многочлена of задаются элементарными симметричными многочленами, построенными из этих степеней. В частности, сумма , которая является суммой степеней корней характеристического многочлена , равна его следу:

Тождества Ньютона связывают следы степеней с коэффициентами характеристического многочлена. Используя их в обратном порядке для выражения элементарных симметричных многочленов через суммы степеней, можно найти характеристический многочлен, вычисляя только степени и их следы. Это вычисление требует вычисления следов матричных степеней и решения треугольной системы уравнений. Оба этих процесса могут быть выполнены в классе сложности NC (решение треугольной системы может быть выполнено методом «разделяй и властвуй»). Следовательно, характеристический многочлен матрицы может быть вычислен в NC. По теореме Кейли-Гамильтона, каждая матрица удовлетворяет своему характеристическому многочлену, и простое преобразование позволяет найти присоединенную матрицу в NC. Переупорядочивание вычислений в эффективную форму приводит к алгоритму Фадеева — ЛеВерье (1840), быстрой параллельной реализации которого обязан Л. Чанки (1976). Его недостаток заключается в том, что он требует деления на целые числа, поэтому в общем случае поле должно иметь характеристику 0.

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

Для данного n элементарные симметричные многочлены ek(x1, …, xn) для k = 1, …, n образуют алгебраическую базу для пространства симметричных многочленов в x1, …, xn: любое многочленное выражение в xi, инвариантное относительно всех перестановок этих переменных, представляется многочленным выражением в этих элементарных симметричных многочленах, и это представление единственно с точностью до эквивалентности многочленных выражений. Это общеизвестный факт, известный как фундаментальная теорема о симметричных многочленах, а тождества Ньютона предоставляют явные формулы в случае степенных сумм симметричных многочленов. Применительно к моноческому многочлену с коэффициентами ak, рассматриваемыми как свободные параметры, это означает, что любое симметричное выражение S(x1, …, xn) в его корнях может быть выражено вместо этого как многочленное выражение P(a1, …, an) только через его коэффициенты, то есть без необходимости знания корней. Этот факт также следует из общих соображений теории Галуа (коэффициенты ak рассматриваются как элементы базового поля, корни – в расширенном поле, группа Галуа которого переставляет их в соответствии с полной симметрической группой, а поле, фиксированное всеми элементами группы Галуа, является базовым полем). Тождества Ньютона также позволяют выражать элементарные симметричные многочлены через степенные суммы симметричных многочленов, показывая, что любой симметричный многочлен также может быть выражен через степенные суммы. Фактически, первые n степенных сумм также образуют алгебраическую базу для пространства симметричных многочленов.

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

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

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

Как уже упоминалось, тождества Ньютона могут использоваться для рекурсивного выражения элементарных симметричных многочленов через степени сумм. Для этого требуется введение целочисленных знаменателей, поэтому это можно сделать в кольце ΛQ симметричных функций с рациональными коэффициентами: и так далее. Общую формулу удобно представить как, где Bn — полный экспоненциальный полином Белла. Это выражение также приводит к следующему тождеству для порождающих функций: При применении к моному, эти формулы выражают коэффициенты через степени сумм корней: замените каждое ei на ai и каждое pk на sk.

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

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