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

UptoLike

ВУЗ: 

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

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

Рубрика: 

180 Теория перестановок Гл. 3
Если j = i
2
, то левая часть дает i
3
. В правой части "срабатыва-
ют" две транспозиции: первая справа переводит i
2
в i
1
, а соседняя
переводит i
1
в i
3
. В последующих транспозициях i
3
отсутствует и
значение "стабилизируется".
Номер j = i
3
левая часть переводит в i
4
. В правой части этот но-
мер сначала [при действии (i
1
, i
2
)] остается на месте, затем [под дей-
ствием (i
1
, i
3
)] переходит в номер i
1
, который [под действием (i
1
, i
4
)]
переходит в i
4
, после чего наступает стабилизация, и т. д.
Последний номер j = i
s
левая часть переводит в i
1
, а в правой
все транспозиции "бездействуют", кроме самой последней [справа]
(i
1
, i
s
), которая переводит j = i
s
в i
1
. ¤
19.2. Разложение произвольной перестановки в произ-
ведение транспозиций. Согласно теореме 17.1, произвольную пе-
рестановку ϕ ∈ S
n
можно разложить в произведение независимых
циклов.
Если ϕ 6= ε, то в разложении можно оставить только нетривиаль-
ные циклы [см. формулу (17.1)].
Каждый из циклов σ
j
(j = 1, .., l) длины s
j
разложим (в соответ-
ствии с предложением 19.1) в произведение s
j
− 1 транспозиций.
Тогда данная перестановка разложится в произведение
l
X
j=1
(s
j
− 1) =
l
X
j=1
s
j
− l
транспозиций. Используя понятие декремента перестановки (см.
определение 17.3 и замечание 17.5), можем сформулировать
Предложение 19.2. Всякую перестановку ϕ ∈ S
n
можно раз-
ложить в произведение δ(ϕ) транспозиций, где δ(ϕ) — декремент
перестановки ϕ.
Доказательство см. выше. ¤
Замечание 19.1. В отличие от разложения на независимые циклы,
которое определено однозначно (с точностью до порядка сомножите-
лей), разложение перестановки на транспозиции определено отнюдь
не однозначно.
Скажем, цикл σ = (1, 2, 3) можно [см. (19.5)] представить в виде
(1, 2, 3) = (1, 3) (1, 2),
180                     Теория перестановок                          Гл. 3

    Если j = i2 , то левая часть дает i3 . В правой части "срабатыва-
ют" две транспозиции: первая справа переводит i2 в i1 , а соседняя
переводит i1 в i3 . В последующих транспозициях i3 отсутствует и
значение "стабилизируется".
    Номер j = i3 левая часть переводит в i4 . В правой части этот но-
мер сначала [при действии (i1 , i2 )] остается на месте, затем [под дей-
ствием (i1 , i3 )] переходит в номер i1 , который [под действием (i1 , i4 )]
переходит в i4 , после чего наступает стабилизация, и т. д.
    Последний номер j = is левая часть переводит в i1 , а в правой
все транспозиции "бездействуют", кроме самой последней [справа]
(i1 , is ), которая переводит j = is в i1 . ¤
   19.2. Разложение произвольной перестановки в произ-
ведение транспозиций. Согласно теореме 17.1, произвольную пе-
рестановку ϕ ∈ Sn можно разложить в произведение независимых
циклов.
   Если ϕ 6= ε, то в разложении можно оставить только нетривиаль-
ные циклы [см. формулу (17.1)].
   Каждый из циклов σj (j = 1, .., l) длины sj разложим (в соответ-
ствии с предложением 19.1) в произведение sj − 1 транспозиций.
   Тогда данная перестановка разложится в произведение

                         l
                         X                  l
                                            X
                               (sj − 1) =         sj − l
                         j=1                j=1


транспозиций. Используя понятие декремента перестановки (см.
определение 17.3 и замечание 17.5), можем сформулировать
  Предложение 19.2. Всякую перестановку ϕ ∈ Sn можно раз-
ложить в произведение δ(ϕ) транспозиций, где δ(ϕ) — декремент
перестановки ϕ.
  Доказательство см. выше. ¤
   Замечание 19.1. В отличие от разложения на независимые циклы,
которое определено однозначно (с точностью до порядка сомножите-
лей), разложение перестановки на транспозиции определено отнюдь
не однозначно.
   Скажем, цикл σ = (1, 2, 3) можно [см. (19.5)] представить в виде

                          (1, 2, 3) = (1, 3) (1, 2),

Страницы