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

UptoLike

ВУЗ: 

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

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

Рубрика: 

166 Теория перестановок Гл. 3
17.2. Теорема о разложении перестановки на независи-
мые циклы. Докажем теперь, что всякую перестановку можно раз-
ложить в произведение независимых циклов.
Теорема 17.1. Для любой перестановки ϕ ∈ S
n
существует пред-
ставление в виде
ϕ = σ
1
σ
2
. . . σ
m
, (17.5)
где перестановки σ
j
(j = 1, ..., m) являются попарно независимыми
(частичными) циклами.
Представление (17.5) определено однозначно с точностью до по-
рядка сомножителей.
Доказательство.
Возьмем любой номер
i
1
∈
X
(на практике есте-
ственно брать i
1
= 1). Под действием ϕ этот номер перейдет в эле-
мент ϕ(i
1
) ∈ X. Если ϕ(i
1
) = i
1
, то первым циклом, входящим в
разложение (17.5), будет тривиальный цикл
σ
1
= (i
1
) = ε.
Если же ϕ(i
1
) = i
2
6= i
1
, то начинается нетривиальный цикл
σ
1
= (i
1
, i
2
, . . . , i
s
1
) (17.6)
некоторой длины s
1
6 n.
Этот цикл образуется следующим образом. Рассмотрим бесконеч-
ную последовательность элементов
i
1
ϕ
7→ i
2
ϕ
7→ i
3
ϕ
7→ · · ·
ϕ
7→ i
k− 1
ϕ
7→ i
k
ϕ
7→ i
k+1
ϕ
7→ · · · (17.7)
Так как множество X конечно, то в последовательности (17.7)
неизбежны повторения. Рассмотрим первое из них. Пусть, скажем,
i
k+s
1
= i
k
; k, s
1
> 1; (17.8)
а все элементы
i
1
, i
2
, . . . , i
k− 1
, i
k
, i
k+1
, . . . , i
k+s
1
−1
попарно различны. (Другими словами, на шаге с номером k + s
1
об-
наруживается первое повторение, т. е. совпадение с одним из преды-
дущих элементов, номер которого равен k.)
Так возникает цикл (может быть, "с хвостиком")
166                       Теория перестановок                                 Гл. 3

  17.2. Теорема о разложении перестановки на независи-
мые циклы. Докажем теперь, что всякую перестановку можно раз-
ложить в произведение независимых циклов.
   Теорема 17.1. Для любой перестановки ϕ ∈ Sn существует пред-
ставление в виде
                       ϕ = σ1 σ2 . . . σm ,               (17.5)
где перестановки σj (j = 1, ..., m) являются попарно независимыми
(частичными) циклами.
   Представление (17.5) определено однозначно с точностью до по-
рядка сомножителей.
   Доказательство. Возьмем любой номер i1 ∈ X (на практике есте-
ственно брать i1 = 1). Под действием ϕ этот номер перейдет в эле-
мент ϕ(i1 ) ∈ X. Если ϕ(i1 ) = i1 , то первым циклом, входящим в
разложение (17.5), будет тривиальный цикл

                                  σ1 = (i1 ) = ε.

  Если же ϕ(i1 ) = i2 6= i1 , то начинается нетривиальный цикл

                             σ1 = (i1 , i2 , . . . , is1 )                    (17.6)

некоторой длины s1 6 n.
  Этот цикл образуется следующим образом. Рассмотрим бесконеч-
ную последовательность элементов
              ϕ       ϕ       ϕ        ϕ           ϕ         ϕ            ϕ
           i1 7→ i2 7→ i3 7→ · · · 7→ ik−1 7→ ik 7→ ik+1 7→ · · ·             (17.7)

  Так как множество X конечно, то в последовательности (17.7)
неизбежны повторения. Рассмотрим первое из них. Пусть, скажем,

                            ik+s1 = ik ; k, s1 > 1;                           (17.8)

а все элементы

                  i1 , i2 , . . . , ik−1 , ik , ik+1 , . . . , ik+s1 −1

попарно различны. (Другими словами, на шаге с номером k + s1 об-
наруживается первое повторение, т. е. совпадение с одним из преды-
дущих элементов, номер которого равен k.)
  Так возникает цикл (может быть, "с хвостиком")

Страницы