Элементарный симметричный многочлен

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

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

Определение [ править ]

Элементарные симметричные полиномы от $n$ переменных $X 1,\dots, X n$ , записанные $e k (X 1,\dots, X n)$ для $k = 0, 1,\dots, n$ , определяются следующим образом:

{\ displaystyle {\ begin {align} e_ {0} (X_ {1}, X_ {2}, \ dots, X_ {n}) & = 1, \\ [10pt] e_ {1} (X_ {1} , X_ {2}, \ dots, X_ {n}) & = \ sum _ {1 \ leq j \ leq n} X_ {j}, \\ e_ {2} (X_ {1}, X_ {2}, \ dots, X_ {n}) & = \ sum _ {1 \ leq j <k \ leq n} X_ {j} X_ {k}, \\ e_ {3} (X_ {1}, X_ {2}, \ dots, X_ {n}) & = \ sum _ {1 \ leq j <k <l \ leq n} X_ {j} X_ {k} X_ {l}, \\\ конец {выровнено}}}

и так далее, заканчивая

{\ displaystyle e_ {n} (X_ {1}, X_ {2}, \ dots, X_ {n}) = X_ {1} X_ {2} \ cdots X_ {n}.}

Вообще говоря, при $k \geq 0$ определим

{\ displaystyle e_ {k} (X_ {1}, \ ldots, X_ {n}) = \ sum _ {1 \ leq j_ {1} <j_ {2} <\ cdots <j_ {k} \ leq n} X_ {j_ {1}} \ dotsm X_ {j_ {k}},}

так что $e k (X 1,\dots, X n) = 0,$ если $k > n$ .

Таким образом, для каждого неотрицательного числа $к$ меньше или равно $п$ существует ровно один элементарный симметричный полином степени $к$ в $п$ переменных. Чтобы сформировать тот, который имеет степень $k$ , мы берем сумму всех произведений $k$ -подмножеств $n$ переменных. (Напротив, если выполнить ту же операцию с использованием мультимножеств переменных, т. Е. Взять переменные с повторением, то получатся полные однородные симметричные многочлены .)

Для целочисленного разбиения (то есть конечной невозрастающей последовательности натуральных чисел) $λ = (λ 1,\dots, λ m)$ определяется симметричный многочлен $e λ (X 1,\dots, X n)$ , также называемый элементарный симметричный многочлен, по

e_{\lambda }(X_{1},\dots ,X_{n})=e_{\lambda _{1}}(X_{1},\dots ,X_{n})\cdot e_{\lambda _{2}}(X_{1},\dots ,X_{n})\cdots e_{\lambda _{m}}(X_{1},\dots ,X_{n})

.

Иногда в обозначениях $сг к$ используется вместо $е к$ .

Примеры [ править ]

Ниже перечислены $n$ элементарных симметричных многочленов для первых четырех положительных значений $n$ . (В любом случае $e 0 = 1$ также является одним из многочленов.)

Для $n = 1$ :

e_{1}(X_{1})=X_{1}.

Для $n = 2$ :

{\begin{aligned}e_{1}(X_{1},X_{2})&=X_{1}+X_{2},\\e_{2}(X_{1},X_{2})&=X_{1}X_{2}.\,\\\end{aligned}}

Для $n = 3$ :

{\begin{aligned}e_{1}(X_{1},X_{2},X_{3})&=X_{1}+X_{2}+X_{3},\\e_{2}(X_{1},X_{2},X_{3})&=X_{1}X_{2}+X_{1}X_{3}+X_{2}X_{3},\\e_{3}(X_{1},X_{2},X_{3})&=X_{1}X_{2}X_{3}.\,\\\end{aligned}}

Для $n = 4$ :

{\begin{aligned}e_{1}(X_{1},X_{2},X_{3},X_{4})&=X_{1}+X_{2}+X_{3}+X_{4},\\e_{2}(X_{1},X_{2},X_{3},X_{4})&=X_{1}X_{2}+X_{1}X_{3}+X_{1}X_{4}+X_{2}X_{3}+X_{2}X_{4}+X_{3}X_{4},\\e_{3}(X_{1},X_{2},X_{3},X_{4})&=X_{1}X_{2}X_{3}+X_{1}X_{2}X_{4}+X_{1}X_{3}X_{4}+X_{2}X_{3}X_{4},\\e_{4}(X_{1},X_{2},X_{3},X_{4})&=X_{1}X_{2}X_{3}X_{4}.\,\\\end{aligned}}

Свойства [ править ]

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

\prod _{j=1}^{n}(\lambda -X_{j})=\lambda ^{n}-e_{1}(X_{1},\ldots ,X_{n})\lambda ^{n-1}+e_{2}(X_{1},\ldots ,X_{n})\lambda ^{n-2}+\cdots +(-1)^{n}e_{n}(X_{1},\ldots ,X_{n}).

То есть, когда мы подставляем числовые значения для переменных $X 1, X 2,\dots, X n$ , мы получаем однозначный одномерный многочлен (с переменной $λ$ ), корни которого являются значениями, замененными на $X 1, X 2,\dots, X n$ и коэффициенты которых с точностью до знака являются элементарными симметричными многочленами. Эти соотношения между корнями и коэффициентами многочлена называются формулами Виета .

Характеристический многочлен из квадратной матрицы является примером применения формул Виеты. Корни этого многочлена являются собственными значениями матрицы. Подставляя эти собственные значения в элементарные симметричные многочлены, мы получаем с точностью до знака коэффициенты характеристического многочлена, которые являются инвариантами матрицы. В частности, след (сумма элементов диагонали) является значением $e 1$ и, следовательно, суммой собственных значений. Точно так же определитель с точностью до знака является постоянным членом характеристического многочлена; точнее определитель - это значение $e п$ . Таким образом, определитель квадратной матрицы является произведением собственных значений.

Множество элементарных симметрических многочленов от $п$ переменных формирует на кольцо из симметричных полиномов в $п$ переменных. Более конкретно, кольцо симметричных многочленов с целыми коэффициентами равно целочисленному кольцу многочленов $ℤ [e 1 (X 1,\dots, X n),\dots, e n (X 1,\dots, X n)]$ . (См. Ниже более общее утверждение и доказательство.) Этот факт является одной из основ теории инвариантов.. Для других систем симметричных многочленов с аналогичным свойством см. Степенные суммы симметрических многочленов и полные однородные симметрические многочлены .

Основная теорема симметричных многочленов [ править ]

Для любого коммутативного кольца $A$ обозначим кольцо симметрических многочленов от переменных $X 1,\dots, X n$ с коэффициентами в $A$ через $A [X 1,\dots, X n] S n$ . Это кольцо многочленов от n элементарных симметричных многочленов $e k (X 1,\dots, X n)$ для $k = 1,\dots, n$ . (Обратите внимание, что $e 0$ не входит в число этих многочленов; так как $e 0 = 1$ , он не может быть членом какого- либо набора алгебраически независимых элементов.)

Это означает, что каждый симметричный многочлен $P (X 1,\dots, X n) \in A [X 1,\dots, X n] S n$ имеет единственное представление

P(X_{1},\ldots ,X_{n})=Q{\big (}e_{1}(X_{1},\ldots ,X_{n}),\ldots ,e_{n}(X_{1},\ldots ,X_{n}){\big )}

для некоторого полинома $Q \in A [Y 1,\dots, Y n]$ . Другими словами, гомоморфизм колец , переводящий $Y k$ в $e k (X 1,\dots, X n)$ для $k = 1,\dots, n,$ определяет изоморфизм между $A [Y 1,\dots, Y n]$ и $A [X 1,\dots, X n] S п$ .

Доказательство [ править ]

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

В случае $n = 1$ результат очевиден, потому что каждый многочлен от одной переменной автоматически симметричен.

Предположим, что теорема доказана для всех многочленов от $m < n$ переменных и всех симметричных многочленов от $n$ переменных со степенью $< d$ . Каждый однородный симметрический многочлен $P$ из $A [X 1,\dots, X n] S n$ может быть разложен как сумма однородных симметрических многочленов

P(X_{1},\ldots ,X_{n})=P_{\text{lacunary}}(X_{1},\ldots ,X_{n})+X_{1}\cdots X_{n}\cdot Q(X_{1},\ldots ,X_{n}).

Здесь «лакунарная часть» $P лакунарная$ определяется как сумма всех мономов в $P,$ которые содержат только собственное подмножество $n$ переменных $X 1,\dots, X n$ , то есть, где по крайней мере одна переменная $X j$ отсутствует.

Поскольку $P$ симметрична, лакунарная часть определяется ее термами, содержащими только переменные $X 1,\dots, X n - 1$ , т.е. которые не содержат $X n$ . Точнее: если $A$ и $B$ - два однородных симметричных многочлена от $X 1,\dots, X n,$ имеющих одинаковую степень, и если коэффициент при $A$ перед каждым одночленом, содержащим только переменные $X 1,\dots, X n - 1,$ равен соответствующий коэффициент при $B$ , то $A$ и $B$ имеют равные лакунарные части. (Это связано с тем, что каждый моном, который может появиться в лакунарной части, должен не иметь по крайней мере одной переменной, и, таким образом, может быть преобразован путем перестановки переменных в одночлен, содержащий только переменные $X 1,\dots, X n - 1.$ )

Но члены $P,$ которые содержат только переменные $X 1,\dots, X n - 1,$ являются в точности членами, которые выживают после операции установки $X n$ в 0, поэтому их сумма равна $P (X 1,\dots, X n - 1, 0)$ , который является симметричным многочленом от переменных $X 1,\dots, X n - 1,$ который мы обозначим через $P̃ (X 1,\dots, X n - 1)$ . По предположению индукции этот многочлен можно записать как

{\tilde {P}}(X_{1},\ldots ,X_{n-1})={\tilde {Q}}(\sigma _{1,n-1},\ldots ,\sigma _{n-1,n-1})

для некоторого $Q̃$ . Здесь дважды индексированные $σ j, n - 1$ обозначают элементарные симметрические многочлены от $n - 1$ переменных.

Рассмотрим теперь многочлен

R(X_{1},\ldots ,X_{n}):={\tilde {Q}}(\sigma _{1,n},\ldots ,\sigma _{n-1,n})\ .

Тогда $R (X 1,\dots, X n)$ является симметричным многочленом от $X 1,\dots, X n$ той же степени, что и $лакунар$ $P$ , который удовлетворяет

R(X_{1},\ldots ,X_{n-1},0)={\tilde {Q}}(\sigma _{1,n-1},\ldots ,\sigma _{n-1,n-1})=P(X_{1},\ldots ,X_{n-1},0)

(первое равенство выполняется, потому что установка $X n$ равным 0 в $σ j, n$ дает $σ j, n - 1$ , для всех $j < n$ ). Другими словами, коэффициент $R$ перед каждым одночлене , который содержит только переменные $X 1, ..., Х п - 1$ равно соответствующий коэффициент $P$ . Как мы знаем, это показывает , что лакунарная часть $R$ совпадает с оригинальным многочленом $P$ . Следовательно, разность $P - R$ не имеет лакунарной части и, следовательно, делится на произведение $X 1 \cdot\cdot\cdot X n$ всех переменных, что равно элементарному симметрическому многочлену $σ n, n$ . Тогда записывая $P - R = σ n, n Q$ , фактор $Q$ представляет собой однородный симметричный многочлен степени меньше $d$ (на самом деле степени не выше $d - n$ ), который по предположению индукции может быть выражен как многочлен от элементарной симметрии функции. Комбинируя представления для $P - R$ и $R$ каждый находит полиномиальное представление для $P$ .

Аналогично индуктивно доказывается единственность представления. (Это эквивалентно тому , что $п$ полиномы $E 1, ..., е п$ являются алгебраически независимы над кольцом $А$ .) Тот факт , что полиномиальное представление единственно следует , что $[$ $X$ $1$ $, ...,$ $X$ $п$ $]$ $S$ $п$ является изоморфна $A$ $[$ $Y$ $1$ $,\dots,$ $Y$ $n$ $]$ .

Альтернативное доказательство [ править ]

Следующее доказательство также является индуктивным, но не включает других многочленов, кроме тех, которые симметричны по $X 1,\dots, X n$ , а также приводит к довольно прямой процедуре для эффективной записи симметричного многочлена как многочлена от элементарных симметричных. Предположим, что симметричный многочлен однороден степени $d$ ; различные однородные компоненты можно разложить по отдельности. Заказывайте одночленов в переменных $X I$ лексикографически , где отдельные переменные упорядочены $X 1 > ...> Х п$ , иными словами, главный член многочлена с наивысшим произошедшим мощности $Х 1$ , а среди теходин с самой высокой мощностью $X 2$ и т.д. Кроме того параметризовать все продукты элементарных симметрических многочленовкоторые имеют степень $д$ (они фактически однородный)как следует из перегородок из $г$ . Упорядочите отдельные элементарные симметричные многочлены $e i (X 1,\dots, X n)$ в произведении так, чтобыпервыми былите, у которых индексы $i$ больше, затем постройте для каждого такого множителя столбец из $i$ блоков и расположите эти столбцы слева направо сформировать диаграмму Юнга, содержащую $d$ коробки во всем. Форма этой диаграммы разбиение $D$ , и каждый раздел $λ$ из $D$ возникает ровно один произведение элементарных симметрических полиномов, которые мы будем обозначать через $е λ т (X 1, ..., Х п$ ) (далее $т$ только присутствует потому что традиционно это произведение связано с транспонированным разбиением $λ$ ). Существенным элементом доказательства является следующее простое свойство, использующее многоиндексную запись для мономов от переменных $X i$ .

Лемма . Главный член $e λ t (X 1,\dots, X n)$ равен $X λ$ .

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

e i (X 1,\dots, X n)

, очевидно, есть

X 1 X 2 \cdot\cdot\cdot X i

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

1,\dots, i.

переменных, то все поля в первой строке содержат 1, во второй строке - 2 и т. д., что означает, что главный член -

X λ

.

Теперь индукцией по старшему одночлену в лексикографическом порядке доказывается, что любой ненулевой однородный симметрический многочлен $P$ степени $d$ может быть записан как многочлен от элементарных симметрических многочленов. Так как $Р$ является симметричным, ее ведущим мономиальным имеет слабо уменьшая показатели, так что некоторое $Х λ$ с $λ$ разбиение $д$ . Пусть коэффициент при этом члене равен $c$ , тогда $P - ce λ t (X 1,\dots, X n)$ является либо нулем, либо симметричным многочленом со строго меньшим старшим мономом. Написание этой разницы индуктивно как многочлен от элементарных симметрических многочленов и добавления назад $с Л т (X 1, ..., X п)$ к нему, получает искомое выражение для полинома $P$ .

Тот факт, что это выражение единственно, или, что то же самое, что все произведения (одночлены) $e λ t (X 1,\dots, X n)$ элементарных симметрических многочленов линейно независимы, также легко доказывается. Лемма показывает, что все эти произведения имеют разные старшие мономы, и этого достаточно: если нетривиальная линейная комбинация $e λ t (X 1,\dots, X n)$ была равна нулю, фокусируется на вкладе в линейной комбинации с ненулевым коэффициентом и с (как полином от переменных $X i$ ) наибольший ведущий моном; главный член этого вклада не может быть отменен никаким другим вкладом линейной комбинации, что дает противоречие.

См. Также [ править ]

Симметричный полином
Полный однородный симметричный многочлен
Полином Шура
Личности Ньютона
Теорема Мак-Магона Мастер
Симметричная функция
Теория представлений

Ссылки [ править ]

Макдональд, И.Г. (1995). Симметричные функции и многочлены Холла (2-е изд.). Оксфорд: Clarendon Press. ISBN 0-19-850450-0. CS1 maint: discouraged parameter (link)
Стэнли, Ричард П. (1999). Перечислительная комбинаторика, Vol. 2 . Кембридж: Издательство Кембриджского университета. ISBN 0-521-56069-1. CS1 maint: discouraged parameter (link)