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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§
§
§ 19 Разложение перестановки на транспозиции 179
§
§
§ 19. Разложение перестановки
в произведение транспозиций
19.1. Разложение циклической перестановки в произведе-
ние транспозиций. Напомним (см. определение 17.2), что транс-
позиция — это частичный цикл вида
τ = (i
1
, i
2
), (19.1)
где i
1
, i
2
— различные номера из множества X = {1, 2, ..., n}.
Как уже отмечалось, запись (i
2
, i
1
) задает ту же самую транспо-
зицию (19.1). Кроме того, очевидна самообратность транспозиций
τ
−1
= τ, (19.2)
которая может быть выражена и иначе — с помощью понятия по-
рядка перестановки:
o(τ) = 2. (19.3)
Рассмотрим теперь произвольный частичный цикл
σ = (i
1
, i
2
, i
3
, . . . , i
s−1
, i
s
) (19.4)
длины s > 2.
Предложение 19.1. Цикл (19.4) разлагается в произведение
s − 1 транспозиций:
(i
1
, i
2
, i
3
, . . . , i
s−1
, i
s
) = (i
1
, i
s
) (i
1
, i
s−1
) . . . (i
1
, i
3
) (i
1
, i
2
). (19.5)
Доказательство. Не забыли ли вы, что произведение перестано-
вок мы "читаем" справа налево [т. е. сначала применяется самая
правая из транспозиций-сомножителей в правой части (19.5)]?
Равенство (19.5) подлежит проверке на произвольном элементе
j ∈ X.
Если этот номер j /∈ D
σ
= {i
1
, i
2
, ..., i
s
}, то все участвующие в
(19.5) перестановки оставляют j на месте, и значит, равенство спра-
ведливо.
Если j = i
1
, то левая часть переводит j в i
2
. В правой части транс-
позиция (i
1
, i
2
) тоже переводит j в i
2
, а все последующие транспози-
ции не содержат i
2
и, значит, оставляют i
2
на месте. Таким образом,
значение правой части равно i
2
.
§ 19               Разложение перестановки на транспозиции                                           179

                     § 19. Разложение перестановки
                       в произведение транспозиций
  19.1. Разложение циклической перестановки в произведе-
ние транспозиций. Напомним (см. определение 17.2), что транс-
позиция — это частичный цикл вида

                                               τ = (i1 , i2 ),                                      (19.1)

где i1 , i2 — различные номера из множества X = {1, 2, ..., n}.
   Как уже отмечалось, запись (i2 , i1 ) задает ту же самую транспо-
зицию (19.1). Кроме того, очевидна самообратность транспозиций

                                                 τ −1 = τ,                                          (19.2)

которая может быть выражена и иначе — с помощью понятия по-
рядка перестановки:
                         o(τ ) = 2.                   (19.3)
   Рассмотрим теперь произвольный частичный цикл

                                    σ = (i1 , i2 , i3 , . . . , is−1 , is )                         (19.4)

длины s > 2.
   Предложение 19.1. Цикл (19.4) разлагается в произведение
s − 1 транспозиций:

       (i1 , i2 , i3 , . . . , is−1 , is ) = (i1 , is ) (i1 , is−1 ) . . . (i1 , i3 ) (i1 , i2 ).   (19.5)


   Доказательство. Не забыли ли вы, что произведение перестано-
вок мы "читаем" справа налево [т. е. сначала применяется самая
правая из транспозиций-сомножителей в правой части (19.5)]?
   Равенство (19.5) подлежит проверке на произвольном элементе
j ∈ X.
   Если этот номер j ∈    / Dσ = {i1 , i2 , ..., is }, то все участвующие в
(19.5) перестановки оставляют j на месте, и значит, равенство спра-
ведливо.
   Если j = i1 , то левая часть переводит j в i2 . В правой части транс-
позиция (i1 , i2 ) тоже переводит j в i2 , а все последующие транспози-
ции не содержат i2 и, значит, оставляют i2 на месте. Таким образом,
значение правой части равно i2 .

Страницы