Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 450 стр.

UptoLike

ВУЗ: 

ИвГУ | Иваново

Составители: 

Рубрика: 

450 Алгебра многочленов Гл. 6
они имеют единичную норму и упорядочены следующим образом:
E
1
 E
2
 ...  E
n
. (48.5)
Замечание 48.3. Поясним происхождение термина лексикографи-
ческий (= словарный) порядок. Этот термин уже встречался нам:
в примере 16.1 мы лексикографически упорядочивали перестанов-
ки степени n. В качестве "букв" фигурировали номера от 1 до n; в
качестве "слов" — нижние строки в двустрочной записи перестано-
вок. Все "слова" имели длину n, и все "буквы" в них были попарно
различны. "Буквы" естественным образом упорядочены (как чис-
ла). Мы считали, что перестановка с нижней строкой (i
1
i
2
... i
n
)
идет раньше перестановки с нижней строкой (j
1
j
2
... j
n
), если для
некоторой позиции s справедливо:
— первые s − 1 соответствующих "букв" в двух "словах" одина-
ковы: i
1
= j
1
; ...; i
s−1
= j
s−1
;
— "буква" с номером s из первого "слова" идет в "алфавите" рань-
ше, нежели "буква" с номером s из второго "слова", т. е. выполняется
неравенство i
s
< j
s
.
Именно так располагаются слова в обычных словарях. [Самым
ранним "словом" будет (1 2 ... n), самым поздним — (n n − 1 ... 1).]
Теперь у нас работает иная версия лексикографического поряд-
ка: хотя "слова" по-прежнему имеют фиксированную длину n, но
"алфавит" уже бесконечен: он состоит из всех неотрицательных це-
лых чисел и естественным образом упорядочен. Отношение "рань-
ше" определяется точно так же, как и для перестановок, но, в силу
бесконечности "алфавита", отсутствует "последняя буква" и среди
"слов" нет самого позднего.
В следующем предложении будет установлена согласованность ле-
ксикографического порядка для мультииндексов с их сложением.
Предложение 48.2. 1. Для любых мультииндексов I, J, K ∈ Z
n
+
справедливо:
( I ≺ J ) ⇒ ( I + K ≺ J + K ); (48.6)
2. Для любых четырех мультииндексов I, J, K, L ∈ Z
n
+
справедли-
во:
( I ≺ J ) ∧ ( K ≺ L ) ⇒ ( I + K ≺ J + L ). (48.7)
Доказательство. 1. Если первые s − 1 номеров в I совпадают с
соответствующими номерами в J и i
s
< j
s
, то первые s − 1 номеров
450                  Алгебра многочленов                      Гл. 6

они имеют единичную норму и упорядочены следующим образом:
                        E1 Â E2 Â ... Â En .                  (48.5)
   Замечание 48.3. Поясним происхождение термина лексикографи-
ческий (= словарный) порядок. Этот термин уже встречался нам:
в примере 16.1 мы лексикографически упорядочивали перестанов-
ки степени n. В качестве "букв" фигурировали номера от 1 до n; в
качестве "слов" — нижние строки в двустрочной записи перестано-
вок. Все "слова" имели длину n, и все "буквы" в них были попарно
различны. "Буквы" естественным образом упорядочены (как чис-
ла). Мы считали, что перестановка с нижней строкой (i1 i2 ... in )
идет раньше перестановки с нижней строкой (j1 j2 ... jn ), если для
некоторой позиции s справедливо:
   — первые s − 1 соответствующих "букв" в двух "словах" одина-
ковы: i1 = j1 ; ...; is−1 = js−1 ;
   — "буква" с номером s из первого "слова" идет в "алфавите" рань-
ше, нежели "буква" с номером s из второго "слова", т. е. выполняется
неравенство is < js .
   Именно так располагаются слова в обычных словарях. [Самым
ранним "словом" будет (1 2 ... n), самым поздним — (n n − 1 ... 1).]
   Теперь у нас работает иная версия лексикографического поряд-
ка: хотя "слова" по-прежнему имеют фиксированную длину n, но
"алфавит" уже бесконечен: он состоит из всех неотрицательных це-
лых чисел и естественным образом упорядочен. Отношение "рань-
ше" определяется точно так же, как и для перестановок, но, в силу
бесконечности "алфавита", отсутствует "последняя буква" и среди
"слов" нет самого позднего.
  В следующем предложении будет установлена согласованность ле-
ксикографического порядка для мультииндексов с их сложением.
  Предложение 48.2. 1. Для любых мультииндексов I, J, K ∈ Zn+
справедливо:
               ( I ≺ J ) ⇒ ( I + K ≺ J + K );          (48.6)
   2. Для любых четырех мультииндексов I, J, K, L ∈ Zn+ справедли-
во:
             ( I ≺ J ) ∧ ( K ≺ L ) ⇒ ( I + K ≺ J + L ).      (48.7)


   Доказательство. 1. Если первые s − 1 номеров в I совпадают с
соответствующими номерами в J и is < js , то первые s − 1 номеров

Страницы