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

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

Определение

Элементарные симметрические многочлены от $п$ переменные $Икс 1, \dots, Икс п$ , написано $е k (Икс 1, \dots, Икс п)$ для $k = 0, 1, \dots, п$ , определяются

{ 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

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

{ 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}

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

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

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

{ 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})}

.

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

Примеры

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

Для $п = 1$ :

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

Для $п = 2$ :

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

Для $п = 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}. , конец {выровнено}}}

Для $п = 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}).}

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

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

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

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

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

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

{ 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 А [Y 1, \dots, Y п]$ . Другой способ сказать то же самое: кольцевой гомоморфизм что посылает $Y k$ к $е k (Икс 1, \dots, Икс п)$ для $k = 1, \dots, п$ определяет изоморфизм между $А [Y 1, \dots, Y п]$ и $А [Икс 1, \dots, Икс п] S п$ .

Доказательство эскиза

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

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

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

{ 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}).}

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

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

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

{ displaystyle { tilde {P}} (X_ {1}, ldots, X_ {n-1}) = { tilde {Q}} ( sigma _ {1, n-1}, ldots, сигма _ {n-1, n-1})}

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

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

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

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

{ 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)}

(первое равенство выполняется, потому что установка $Икс п$ до 0 дюймов $σ j, п$ дает $σ j, п - 1$ , для всех $j < п$ ). Другими словами, коэффициент $р$ перед каждым мономом, содержащим только переменные $Икс 1, \dots, Икс п - 1$ равен соответствующему коэффициенту при $п$ . Как известно, это показывает, что лакунарная часть $р$ совпадает с исходным полиномом $п$ . Поэтому разница $п - р$ не имеет лакунарной части и поэтому делится на произведение $Икс 1 \cdot\cdot\cdot Икс п$ всех переменных, что равно элементарному симметричному многочлену $σ п, п$ . Затем писать $п - р = σ п, п Q$ , частное $Q$ - однородный симметрический многочлен степени меньше $d$ (на самом деле степень не выше $d - п$ ), который по предположению индукции может быть выражен в виде полинома от элементарных симметрических функций. Объединение представлений для $п - р$ и $р$ найти полиномиальное представление для $п$ .

Аналогично индуктивно доказывается единственность представления. (Это равносильно тому, что $п$ многочлены $е 1, \dots, е п$ находятся алгебраически независимый над кольцом $А$ .) Из единственности полиномиального представления следует, что $А [Икс 1, \dots, Икс п] S п$ изоморфен $А [Y 1, \dots, Y п]$ .

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

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

Лемма. Ведущий срок $е λ т (Икс 1, \dots, Икс п)$ является $Икс λ$ .

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

е я (Икс 1, \dots, Икс п)

ясно

Икс 1 Икс 2 \cdot\cdot\cdot Икс я

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

1, \dots, я

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

Икс λ

.

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

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

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

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

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