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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§
§
§ 17 Разложение перестановки на независимые циклы 167
i
1
ϕ
7→ · · ·
ϕ
7→ i
k−1
ϕ
7→ i
k
ϕ
7→ · · ·
ϕ
7→ i
k +s
1
−1
↑ ϕ |
Легко, однако, убедиться в том, что на самом деле "хвостика" не
будет, т. е. обязательно будет k = 1. Действительно, в противном
случае (k > 1) в элемент i
k
под действием ϕ будут переходить два
(различных по предположению) элемента i
k −1
и i
k+s
1
−1
, что проти-
воречит биективности ϕ.
Итак, "зацикливание" происходит начиная с элемента i
1
:
i
1+s
1
= i
1
;
далее образы i
k
= ϕ
k
(i
1
) повторяются с периодом s
1
:
i
k +s
1
= i
k
(для любого натурального k); возникает цикл (17.6) с областью дей-
ствия
D
1
= {i
1
, i
2
, . . . , i
s
1
}.
Эта область действия инвариантна относительно ϕ, и на ней ϕ
действует так же, как и циклическая перестановка σ
1
.
Важно заметить, что если бы мы начали цикл с какого-то другого
номера i
0
1
, но по ходу построения цикла в него попал бы элемент i
1
,
то цикл, начинающийся с i
0
1
, и цикл, начинающийся с i
1
, были бы
одинаковыми (это вытекает из замечания 17.1).
Иначе говоря, каждый элемент множества X содержится в одном
и только одном (частичном) цикле относительно перестановки ϕ.
Образуем множество G
1
для учета просмотренных элементов. Ес-
ли первый цикл σ
1
не тривиален, то положим G
1
= D
1
, если же
σ
1
= (i
1
), то возьмем G
1
= {i
1
}, хотя область действия D
1
в этом
случае пуста. (Используется такой термин: множество G
1
называ-
ется орбитой элемента i
1
под действием перестановки ϕ.)
Если длина первого цикла s
1
= n, то разложение (17.5) получено
(и содержит всего один множитель). Если же s
1
< n, то выберем
любой номер j
1
/∈ G
1
. (На практике, т. е. при алгоритмической ор-
ганизации процесса, можно в качестве j
1
выбирать наименьший из
номеров, не вошедших в G
1
.)
§ 17        Разложение перестановки на независимые циклы                  167



             ϕ          ϕ          ϕ             ϕ          ϕ
       i1    7→   ···   7→ ik−1   7→     ik      7→ · · ·   7→ ik+s1 −1
                                          ↑            ϕ          |

   Легко, однако, убедиться в том, что на самом деле "хвостика" не
будет, т. е. обязательно будет k = 1. Действительно, в противном
случае (k > 1) в элемент ik под действием ϕ будут переходить два
(различных по предположению) элемента ik−1 и ik+s1 −1 , что проти-
воречит биективности ϕ.
   Итак, "зацикливание" происходит начиная с элемента i1 :

                                  i1+s1 = i1 ;

далее образы ik = ϕk (i1 ) повторяются с периодом s1 :

                                  ik+s1 = ik

(для любого натурального k); возникает цикл (17.6) с областью дей-
ствия
                      D1 = {i1 , i2 , . . . , is1 }.

   Эта область действия инвариантна относительно ϕ, и на ней ϕ
действует так же, как и циклическая перестановка σ1 .
   Важно заметить, что если бы мы начали цикл с какого-то другого
номера i01 , но по ходу построения цикла в него попал бы элемент i1 ,
то цикл, начинающийся с i01 , и цикл, начинающийся с i1 , были бы
одинаковыми (это вытекает из замечания 17.1).
   Иначе говоря, каждый элемент множества X содержится в одном
и только одном (частичном) цикле относительно перестановки ϕ.
   Образуем множество G1 для учета просмотренных элементов. Ес-
ли первый цикл σ1 не тривиален, то положим G1 = D1 , если же
σ1 = (i1 ), то возьмем G1 = {i1 }, хотя область действия D1 в этом
случае пуста. (Используется такой термин: множество G1 называ-
ется орбитой элемента i1 под действием перестановки ϕ.)
   Если длина первого цикла s1 = n, то разложение (17.5) получено
(и содержит всего один множитель). Если же s1 < n, то выберем
любой номер j1 ∈   / G1 . (На практике, т. е. при алгоритмической ор-
ганизации процесса, можно в качестве j1 выбирать наименьший из
номеров, не вошедших в G1 .)

Страницы