Тождества Ньютона - Newtons identities - Wikipedia

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

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

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

Позволять Икс1, ..., Иксп - переменные, обозначим для k ≥ 1 по пk(Икс1, ..., Иксп) k-го сумма мощности:

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

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

действительно для всех п ≥ 1 и п ≥k ≥ 1.

Также есть

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

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

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

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

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

действительно для всех п ≥ 1 и п ≥k ≥ 1.

Также есть

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

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

Многочлен с корнями Икся может быть расширен как

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

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

Подобная формулировка полиномов полезна при использовании метода Делвеса и Лайнесса.[1] найти нули аналитической функции.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и так далее.[2] Общую формулу удобно записать как

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из особого случая п = k

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

следующее. Подстановка Иксj за т дает

Подводя итог всему j дает

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

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

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

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

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

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

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

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

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

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

что дает k-я тождество Ньютона.

Как телескопическая сумма симметричных функциональных тождеств

Следующий вывод, приведенный в основном в (Mead, 1992), сформулирован в кольцо симметричных функций для наглядности (все тождества не зависят от количества переменных). Исправить некоторые k > 0, и определим симметричную функцию р(я) для 2 ≤я ≤ k как сумма всех различных мономы степени k полученный умножением одной переменной в степения с k − я различные другие переменные (это мономиальная симметричная функция мγ где γ - форма крючка (я, 1,1, ..., 1)). Особенно р(k) = пk; за р(1) описание будет соответствовать описанию еk, но этот случай был исключен, так как здесь мономы больше не имеют выделенной переменной. Все продукты пяеkя можно выразить через р(j), причем первый и последний случай несколько особенный. Надо

поскольку каждое произведение терминов слева, включающих различные переменные, способствует р(я), а те, где переменная из пя уже встречается среди переменных члена из еkя способствует р(я + 1), и все члены справа так получаются ровно один раз. За я = k один умножается на е0 = 1, что дает тривиально

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

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

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

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

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

Рекомендации

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

внешняя ссылка