Тождества Ньютона - Newton's identities

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

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

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

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

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

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

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

Также есть

для всех k  >  n  ≥ 1.

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

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

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

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

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

Также есть

для всех k  >  n  ≥ 1.

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

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

где коэффициенты - это определенные выше симметричные многочлены. Учитывая степенные суммы корней

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

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

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

Если полином выше , является характеристическим полиномом из матрицы А (в частности , когда является спутник матрицы многочлена), корни являются собственными значениями матрицы, подсчитанные с их алгебраической кратностью. Для любого натурального числа к , матрицы к имеют как собственные силы х я K , и каждое собственное значение из A вносит свою кратность тому из собственных значений х я к из A к . Тогда коэффициенты характеристического многочлена A k задаются элементарными симметричными многочленами от этих степеней x i k . В частности, сумма x i k , которая является суммой k -й степени p k корней характеристического многочлена A , задается его следом :

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

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

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

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

Для данного n элементарные симметричные многочлены e k ( x 1 , ..., x n ) для k  = 1, ..., n образуют алгебраический базис пространства симметричных многочленов от x 1 , .... x n : каждое полиномиальное выражение в x i , которое инвариантно относительно всех перестановок этих переменных, задается полиномиальным выражением в этих элементарных симметричных полиномах, и это выражение является уникальным с точностью до эквивалентности полиномиальных выражений. Это общий факт, известный как фундаментальная теорема о симметричных многочленах , и тождества Ньютона предоставляют явные формулы в случае степенных симметричных многочленов. Применительно к моническому полиному со всеми коэффициентами a k, рассматриваемыми как свободные параметры, это означает, что каждое симметричное полиномиальное выражение S ( x 1 , ..., x n ) в его корнях может быть выражено вместо этого как полиномиальное выражение P ( a 1 , ..., a n ) только с точки зрения его коэффициентов, другими словами, не требуя знания корней. Этот факт также следует из общих соображений в теории Галуа (каждый рассматривает a k как элементы базового поля с корнями в поле расширений, группа Галуа которого переставляет их в соответствии с полной симметрической группой, а поле фиксируется под всеми элементами поля Галуа. группа - это базовое поле).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эти выражения в точности соответствуют полиномам индекса цикла симметрических групп , если интерпретировать степенные суммы p i как неопределенные: коэффициент в выражении для h k любого монома p 1 m 1 p 2 m 2 ... p l m l равно доле всех перестановок k, которые имеют m 1 неподвижных точек, m 2 циклов длины 2, ... и m l циклов длины l . Явно этот коэффициент можно записать как где ; это N - количество перестановок, коммутирующих с любой данной перестановкой  π данного типа цикла. Выражения для элементарных симметрических функций имеют коэффициенты с одинаковым абсолютным значением, но знак равен знаком  П , а именно (-1) м 2 + м 4 + ... .

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

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


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

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

Первые четыре формулы были получены Альбертом Жираром в 1629 году (то есть до Ньютона).

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

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

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

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

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

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

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

и так далее. Помимо замены каждого e i на соответствующий h i , единственное изменение по сравнению с предыдущим семейством тождеств заключается в знаках терминов, которые в этом случае зависят только от количества присутствующих факторов: знака мономиальная представляет собой - (- 1) м 1 + м 2 + м 3 + ... . В частности, здесь также применимо приведенное выше описание абсолютных значений коэффициентов.

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

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

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

мы рассматриваем и как неизвестные, и решаем окончательное, давая

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

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

Вывод идентичностей

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

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

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

следующее. Подставляя е J для т дает

Суммирование по всем j дает

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

Сравнение коэффициентов в серии

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

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

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

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

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

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

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

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

что дает 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 ), причем первый и последний случай являются в некоторой степени особенными. Надо

поскольку каждое произведение терминов слева, включающих различные переменные, вносит вклад в r ( i ), а те, в которых переменная из p i уже встречается среди переменных члена из e k - i, вносят вклад в r ( i  + 1), и все условия справа так получаются ровно один раз. При i  =  k умножаем на e 0  = 1, что тривиально дает

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

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

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

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

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

использованная литература

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