Элементарный симметричный многочлен - Elementary symmetric polynomial

В математике , особенно в коммутативной алгебре , элементарные симметричные многочлены являются одним из типов основных строительных блоков для симметричных многочленов в том смысле, что любой симметричный многочлен может быть выражен как многочлен от элементарных симметричных многочленов. То есть любой симметричный многочлен $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)$ , также называемый элементарный симметричный многочлен, по

{\ displaystyle 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$ :

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

Для $n = 2$ :

{\ displaystyle {\ begin {align} e_ {1} (X_ {1}, X_ {2}) & = X_ {1} + X_ {2}, \\ e_ {2} (X_ {1}, X_ { 2}) & = X_ {1} X_ {2}. \, \\\ конец {выровнено}}}

Для $n = 3$ :

{\ displaystyle {\ begin {align} 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}. \, \\\ конец {выровнено}}}

Для $n = 4$ :

{\ displaystyle {\ begin {align} 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}. \, \\\ конец {выровнено}}}

Характеристики

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

{\ displaystyle \ 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 n$ . Таким образом, определитель квадратной матрицы является произведением собственных значений.

Множество элементарных симметрических многочленов от $п$ переменных формирует на кольцо из симметричных полиномов в $п$ переменных. Более конкретно, кольцо симметричных многочленов с целыми коэффициентами равно целочисленному кольцу многочленов $ℤ [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$ имеет единственное представление

{\ Displaystyle 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$ , по степени однородного многочлена. Общий случай затем следует путем разбиения произвольного симметричного многочлена на его однородные компоненты (которые снова являются симметричными).

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

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

{\ Displaystyle 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)$ . По предположению индукции этот многочлен можно записать как

{\ Displaystyle {\ тильда {P}} (X_ {1}, \ ldots, X_ {n-1}) = {\ tilde {Q}} (\ sigma _ {1, n-1}, \ ldots, \ сигма _ {n-1, n-1})}

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

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

{\ Displaystyle R (X_ {1}, \ ldots, X_ {n}): = {\ тильда {Q}} (\ sigma _ {1, n}, \ ldots, \ sigma _ {n-1, n} ) \.}

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

{\ Displaystyle 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 я$ лексически , где отдельные переменные упорядочены $X 1 > ...> Х п$ , иными словами, главный член многочлена с наивысшим произошедшим мощности $X 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.
Стэнли, Ричард П. (1999). Перечислительная комбинаторика, Vol. 2 . Кембридж: Издательство Кембриджского университета. ISBN 0-521-56069-1.

Languages

In other projects