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

редактировать

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

Содержание

1 Определение
2 Примеры
3 Свойства
4 Основная теорема о симметричных многочленах
- 4.1 Схема доказательства
- 4.2 Альтернативное доказательство
5 См. Также
6 Ссылки

Определение

Элементарные симметричные многочлены от n переменных X 1,…, X n, записанные e k(X1,…, X n) для k = 0, 1,…, n, определяются как

e 0 (X 1, X 2,…, X n) = 1, e 1 (X 1, X 2,…, X n) = ∑ 1 ≤ j ≤ n X j, e 2 (X 1, X 2,…, X n) = ∑ 1 ≤ j < k ≤ n X j X k, e 3 ( X 1, X 2, …, X n) = ∑ 1 ≤ j < k < l ≤ n X j X k X l, {\displaystyle {\begin{aligned}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 {\ 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}, \\\ конец {выровнено}}}

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

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

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

В общем, для k ≥ 0 мы определяем

ek (X 1,…, X n) = ∑ 1 ≤ j 1 < j 2 < ⋯ < j k ≤ n X j 1 ⋯ X j k, {\displaystyle e_{k}(X_{1},\ldots,X_{n})=\sum _{1\leq j_{1}

{\ displaystyle e_ } (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(X1,…, X n) = 0, если k>п.

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

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

e λ (X 1,…, X n) = e λ 1 (X 1,…, X n) ⋅ е λ 2 (Икс 1,…, Икс N) ⋯ е λ м (Икс 1,…, Икс 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})}

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 используется вместо e k.

Примеры

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

Для n = 1:

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

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

Для n = 2:

e 1 (X 1, X 2) = X 1 + X 2, e 2 ( Х 1, Х 2) = Х 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}. \, \\\ конец {выровнено}}}

\ begin {align} e_1 (X_1, X_2) = X_1 + X_2, \\ e_2 (X_1, X_2) = X_1X_2. \, \\ \ end {align}

Для n = 3:

e 1 (X 1, X 2, X 3) = X 1 + Х 2 + Х 3, е 2 (Х 1, Х 2, Х 3) = Х 1 Х 2 + Х 1 Х 3 + Х 2 Х 3, е 3 (Х 1, Х 2, Х 3) = Х 1 х 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}. \, \\\ конец {выровнено}}}

\ 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_1X_2 + X_1X_3 + X_2X_3, \\ e_3 (X_1, X_2, X_3) = X_1X_2X_3. \, \\ \ end {align}

Для n = 4:

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) = Х 1 Х 2 + Х 1 Х 3 + Х 1 Х 4 + Х 2 Х 3 + Х 2 Х 4 + Х 3 Х 4, е 3 (Х 1, Х 2, Х 3, Х 4) = Х 1 Х 2 Икс 3 + Х 1 Х 2 Х 4 + Икс 1 Х 3 Х 4 + Х 2 Х 3 Х 4, е 4 (Х 1, Х 2, Х 3, Х 4) = Х 1 Х 2 Х 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}. \, \\\ end {align}}}

\ 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_1X_2 + X_1X_3 + X_1X_4 + X_2X_3 + X_2X_4 + X_3X_4, \\ e_3 (X3_1, X_2, X_3, X_4) = X_1X_2X_3 + X_1X_2X_4 + X_1X_3X_4 + X_2X_3X_4, \\ e_4 (X_1, X_2, X_3, X_4) = X_1X_2X_3X_4. \, \\ \ end {align}

Свойства

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

∏ j = 1 n (λ - X j) = λ n - e 1 (X 1,…, X n) λ n - 1 + e 2 (X 1,…, X n) λ n - 2 + ⋯ + (- 1) nen (X 1,…, X n). {\ 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}).}

\ 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,…, X n, мы получаем монический одномерный многочлен (с переменной λ), корни которого являются значениями, замененными на X 1, X 2,…, X n, и коэффициенты которых от до являются их знаком элементарных симметричных многочленов. Эти отношения между корнями и коэффициентами многочлена называются формулами Виета.

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

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

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

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

Это означает что каждый симметричный многочлен P (X 1,…, X n) ∈ A [X 1,…, X n ] имеет уникальное представление

P (X 1,…, X n) = Q (e 1 (X 1,…, X n),…, en (X 1,…, X 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)}}

{\ 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 ∈ A [Y 1,…, Y n ]. Другим способом сказать то же самое является то, что гомоморфизм колец, который отправляет Y k в e k(X1,…, X n) для k = 1, …, N определяет изоморфизм между A [Y 1,…, Y n ] и A [X 1,…, X n ].

Схема доказательства

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

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

Предположим теперь, что теорема доказана для всех многочленов для m < n variables and all symmetric polynomials in n variables with degree < d. Every homogeneous symmetric polynomial P in A[X1,…, X n ], которые можно разложить как сумму однородных симметрических многочленов

P (X 1,…, X n) = P лакунарный (X 1,…, X n) + X 1 ⋯ X n ⋅ Q (X 1,…, X 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}).}

{\ 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,…, X n, то есть, где по крайней мере одна переменная X j отсутствует.

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

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

P ~ (X 1,…, X n - 1) = Q ~ (σ 1, n - 1,…, σ n - 1, n - 1) { \ Displaystyle {\ тильда {P}} (X_ {1}, \ ldots, X_ {n-1}) = {\ tilde {Q}} (\ sigma _ {1, n-1}, \ ldots, \ sigma _ {n-1, 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,…, X n): = Q ~ (σ 1, n,…, σ n - 1, n). {\ Displaystyle R (X_ {1}, \ ldots, X_ {n}): = {\ тильда {Q}} (\ sigma _ {1, n}, \ ldots, \ sigma _ {n-1, n}) \.}

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

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

R (X 1,…, X n - 1, 0) = Q ~ (σ 1, n - 1,…, σ N - 1, N - 1) знак равно п (Икс 1,…, Икс N - 1, 0) {\ Displaystyle R (X_ {1}, \ ldots, X_ {n-1}, 0) = {\ тильда {Q}} (\ sigma _ {1, n-1}, \ ldots, \ sigma _ {n-1, n-1}) = P (X_ {1}, \ ldots, X_ {n-1}, 0)}

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, для all j < n). In other words, the coefficient of R before each monomial which contains only the variables X1,…, X n - 1 равняется соответствующему коэффициенту в P. Как известно, это показывает, что лакунарная часть R совпадает с лакунарной частью исходного многочлена P. Следовательно, разность P - R не имеет лакунарной части и, следовательно, делится на произведение X 1 ··· X n всех переменных, что равно элементарному симметричному многочлену σ n, n. Тогда записываем P - R = σ n, n Q, фактор Q представляет собой однородный симметричный многочлен степени меньше d (на самом деле степени не выше d - n), который по предположению индукции может быть выражен как многочлен от элементарных симметрических функций. Комбинируя представления для P - R и R, можно найти полиномиальное представление для P.

Единственность представления можно доказать индуктивно аналогичным образом. (Это эквивалентно тому факту, что n многочленов e 1,…, e n являются алгебраически независимыми над кольцом A.) Тот факт, что многочлен представление уникально означает, что A [X 1,…, X n ] изоморфно A [Y 1,…, Y n ].

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

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

Лемма . Главный член e λ(X1,…, X n) - это X.

Доказательство. Главный член продукта - это произведение ведущих членов каждого фактора (это верно, когда используется мономиальный порядок, например, лексикографический порядок, используемый здесь), и главный член фактора e i(X1,…, X n), очевидно, представляет собой X 1X2··· X i. Чтобы подсчитать вхождения отдельных переменных в результирующий моном, заполните столбец диаграммы Юнга, соответствующий рассматриваемому фактору, числами 1,…, i переменных, затем все поля в первой строке содержат 1, а те, что в вторая строка 2 и т. д., что означает, что главный член - X.

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

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

См. Также

Ссылки

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