ВУЗ:
Составители:
Рубрика:
() ()
...,,,
2
iii αα , так как в множестве
i
X содержится конечное число элементов, то эта последовательность будет периодиче-
ски повторяться. Обозначим
i
l – такое наименьшее положительное число, что
(
)
ii
i
l
=α . Тогда, удаляя повторяющиеся эле-
менты
i
X , получим
() () () () ()
{}
iiiiiiX
i
l
i
1
212
...,,,,,,...,
−
−−
ααααα= . Далее, образ i при действии любой отрицательной степени
подстановки α совпадет с образом
i при действии некоторой неотрицательной степени подстановки α . Действительно, для
любого числа
k < 0 найдется такое натуральное число n, что
(
)
ii
nlkln ≤<−1 . Следовательно,
ii
lnlk
<
+≤0 . Поэтому
()
=α i
k
()
()
() ()
iii
p
nlknl
k
ii
α=α=αα=
+
, где p – некоторое неотрицательное число,
i
lp <
≤
0 . Таким образом, записывая
только различные элементы
i
X , получим
() () ()
{}
iiiiX
i
l
i
1
2
...,,,,
−
ααα= , где
i
l – некоторое положительное число. Обозначим
() () ()
(
)
iiii
i
l
i
1
2
...
−
ααα=α – цикл длиной
i
l (или
()
()
∈α
∉
=α
i
i
i
Xjj
Xjj
j
если,
;если,
). Так как классы эквивалентности не пересека-
ются, то циклы (типа
i
α ), им соответствующие, будут независимыми. Далее, подстановка
α
на множестве X может быть
представлена в виде
t
ααα=α ...
21
. Если опустить циклы длины 1 (как соответствующие тождественной подстановке), то
()
tp
p
≤ααα=α ...
21
. Причем, любой из циклов
p
ααα ...,,,
21
имеет длину не менее 2. Возможность представления под-
становки α в виде произведения независимых циклов длины не менее 2 доказана.
Докажем единственность (с точностью до перестановки циклов в их произведении) такого представления. Допустим,
что есть еще одно такое представление подстановки
α
:
m
β
β
β
=
α
...
21
. Пусть i ∈ X действительно перемещаемый элемент
подстановкой
α . Так как циклы в представлениях
=
α
α
α
=
α
p
...
21
m
β
β
β
...
21
независимы, то i является действительно пере-
мещаемым элементом только для одного цикла для каждого из представлений. Учитывая, что независимые циклы в произве-
дениях можно переставлять, считаем, что это циклы
11
и
β
α
, тогда
(
)
(
)
(
)
(
)
(
)
(
)
......
22
111
iiiiii αα=αα=α
и
(
)
(
)
(
)
(
)
(
)
(
)
......
22
111
iiiiii αα=ββ=β .
Следовательно, циклы
11
и
β
α состоят из одних и тех же элементов и поэтому
11
β
=
α
. Аналогично доказывается, что
qq
β=αβ=α ...,,
22
, где q – меньшее из чисел p и m. Отсюда вытекает, что p = m, и подстановка α может иметь представле-
ния в виде произведения независимых циклов, отличающиеся только порядком множителей. Теорема доказана.
9.4. РАЗЛОЖЕНИЕ ПОДСТАНОВКИ В ПРОИЗВЕДЕНИЕ
ТРАНСПОЗИЦИЙ И ЧЕТНОСТЬ ПОДСТАНОВКИ
Доказанная теорема 9.3.1 позволяет любую подстановку свести к подстановкам «простой структуры» – независимым
циклам длины не менее 2. Оказывается, что подстановки можно представлять как результат произведения «самых простых»
(не считая тождественной) подстановок – транспозиций. Уточним это утверждение.
Теорема 9.4.1. Пусть множество X содержит не менее 2 элементов. Тогда любая подстановка α на множестве X пред-
ставляется в виде произведения транспозиций.
Доказательство. Заметим сразу, что теорема верна для тождественной подстановки:
ijij
e ττ=
, где i ∈ X, j ∈ X. Для ос-
тальных подстановок, в силу теоремы 9.3.1, достаточно доказать, что цикл длины не менее 2 представляется в виде произве-
дения транспозиций.
Пусть нам дан цикл длиной
q:
(
)
qq
iiiii
1321
...
−
. Докажем справедливость равенства
(
)
(
)
(
)
()
(
)
21311111321
...... iiiiiiiiiiiii
qqqq −−
=
. Напомним, что транспозиции в правой части равенства – это подстановки следующего
вида:
()
==γ
n
n
i
i
i
i
ii
...
...
...
...
...1
...1
1
2
2
1
212
;
()
==γ
n
n
i
i
i
i
ii
...
...
...
...
...1
...1
1
3
3
1
313
;
…
()
==γ
−
−
−−
n
n
i
i
i
i
ii
q
q
qq
...
...
...
...
...1
...1
1
1
1
1
111
;
()
==γ
n
n
i
i
i
i
ii
q
q
qq
...
...
...
...
...1
...1
1
1
1
.
Рассмотрим произведение транспозиций
(
)
(
)
(
)
(
)
γ
=
γ
γ
γ
γ
=
−− 2312131111
......
qqqq
iiiiiiii
.
Страницы
- « первая
- ‹ предыдущая
- …
- 58
- 59
- 60
- 61
- 62
- …
- следующая ›
- последняя »