алгебра от Галины Валентиновны / Лексикографический порядок
В случае полиномов возникает потребность записи слагаемых многочлена в каком-то порядке. Обычно при этом используют так называемый лексикографический (то есть как в словаре) порядок. При лексикографическом упорядочении вначале сравниваются показатели при x 1 , затем, если они равны, то сравнивают показатели при x 2 и т.д.
Итак, рассматриваются мономы вида ax 1 k 1 x 2 k 2 . x n k n . Мономы можно умножать друг на друга, например, моном u 2 x 1 x 2 x 4 3 и моном v 3 x 2 3 x 3 после перемножения дадут uv 6 x 1 x 2 4 x 3 x 4 3 .
Если моном u лексикографически старше монома v , то будем писать это так u v или v u . Согласно определению это означает, что имеется хотя бы одна переменная, которая входит в u и v с разными показателями; и первая из переменных (считая слева направо), которая входит в u и v с разными показателями, входит в u с большим показателем, чем в v .
Следующие свойства позволяют использовать лексикографическое упорядочение для доказательства теорем по индукции.
Теорема (свойства лексикографического порядка).
Отношение лексикографического упорядочения обладает следующими свойствами:
1) любые два монома с коэффициентом 1 сравнимы, то есть либо u v либо v u либо v u .
2) если u v и v w , то u w (транзитивность; рефлексивности и симметричности нет);
3) если u v , то uw vw для любого монома w («неравенство можно умножать справа или слева на любой моном»); Точно так же wu wv .
4) если u 1 v 1 и u 2 v 2 , то u 1 u 2 v 1 v 2 («неравенство одинакового
смысла можно перемножать»).
1) Если мономы не одинаковы, то найдется переменная, по которой показатели этих мономов различаются, рассмотрим первую, считая слева направо, такую переменную. Если показатель по этой переменной больше у монома u , то u v , если наоборот, то v u .
2) Пусть u v и v w . Если u , v имеют разные показатели по x 1 , то как легко видеть u w . Пусть x i первая переменная, по которой показатели мономов u , v различаются. Пусть показатели мономов u , v , w есть соответственно k i , l i , m i . Очевидно, что возможны три случая
a. Первая переменная, показатели по которой отличаются у мономов v , w имеет номер j , меньший i . Тогда пер-
вой переменной с различными показателями у мономов v , w будет x j , для которой k j l j m j и поэтому
b. Первая переменная, показатели по которой отличаются у мономов v , w имеет номер j , равный i . Тогда первой
переменной с различными показателями у мономов v , w будет x i , для которой k i l i m i и поэтому u w .
c. Первая переменная, показатели по которой отличаются у мономов v , w имеет номер j , больший i . Тогда пер-
вой переменной с различными показателями у моно-
мов v , w будет x i , для которой k i l i
3) При умножении на w к показателям, с которыми каждая переменная входит в u и v , добавляется одно и то же число, и знак неравенства (или равенства) между этими показателями сохраняется. Поэтому uw vw .
4) Пользуясь предыдущим свойством, получим u 1 u 2 v 1 u 2 v 1 v 2 . Далее по транзитивности u 1 u 2 v 1 v 2 .
Пример . Следующий полином расположен по лексикографическому убыванию членов x 1 2 x 2 x 1 x 2 2 x 3 2 x 1 x 3 2 x 2 x 3 2 x 2 x 3 2 3 . Заметим, что моном x 1 x 2 2 x 3 лексикографически младше чем x 1 2 x 2 , хотя его степень больше.
Среди ненулевых мономов любого ненулевого полинома
f K x 1 . x n имеется единственный, который лексикографически
старше всех остальных. Он называется старшим мономом полинома f .
Теорема (о старшем мономе произведения). Старший моном произведения ненулевых полиномов равен произведению их старших мономов.
Запишем полиномы f и g в следующем виде. f старший моном u младшие мономы( u i )
g старший моном w младшие мономы( w j )
Тогда u u i , w w j . Поэтому в произведении fg входят мономы ви-
да uw j , u i w j , u i w , uw .
Ясно, что uw uw j , uw u i w , uw u i w j (проверьте самостоятельно). По-
этому uw есть старший моном.
Определение . Полином f K x 1 . x n называется симметрическим,
если он не изменяется ни при каких перестановках переменных. Поскольку любая перестановка есть произведение транспозиций, и даже более того, порождается транспозициями вида 12 , 13 . 1 n ,
то достаточно проверять неизменность полинома при перестановке двух индексов.
Очевидно, что любая однородная компонента симметрического полинома является симметрическим полиномом.
1. Элементарные симметрические полиномы являются симметрическими полиномами.
2. Степенные суммы S n x 1 n . x k n , n 1,2. являются симметрическими полиномами.
3. Определитель Вандермонда
V x 1 . x n x i x j
не является симметрическим полиномом. Он меняет знак при нечетной подстановке. Но его квадрат является симметрическим полиномом.
4. При любых перестановках переменных x 1 , x 2 , x 3 , x 4 полиномы
h 1 x 1 x 2 x 3 x 4 , h 2 x 1 x 3 x 2 x 4 , h 3 x 1 x 4 x 2 x 3 переходят друг в друга. Поэтому h 1 h 2 h 3 является симметрическим полиномом.
Очевидно, что сумма и произведение симметрических полиномов а также произведение симметрического полинома на число являются симметрическими полиномами. Иными словами, симметрические полиномы образуют подалгебру в алгебре всех полиномов.
Следовательно, если F K x 1 . x m – произвольный полином от m переменных и f 1 . f m K x 1 . x n – симметрические по-
линомы, то F f 1 . f m – также симметрический полином от x 1 . x n .Оказывается, что если взять в качестве
f 1 . f m K x 1 . x n элементарные симметрические полиномы,
то любой симметрический полином можно выразить в таком виде.
Теорема (основнаятеорема о симметрических полиномах). Всякий симметрический полином единственным образом представим в виде полинома от элементарных симметрических полиномов.
Лемма (о старшем мономе симметрического полинома).
Пусть u ax 1 k 1 x 2 k 2 . x n k n старший моном симметрического поли-
нома. Тогда k n k n 1 . k 1 .
Доказательство . Предположим, что k i k i 1 для некоторого числа i . Наряду с мономом u полином должен содержать моном