Алгебра. Ткач Л.И. - 61 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Найдем образы элементов
(
)
qji
j
...,,1= при действии подстановки γ (напомним, что если элемент x при отображении
f переходит в элемент y, то одно из обозначений для этой ситуации: yx
f
→ ):
21222221
12
4
3
2
... iiiiiiii
qqq
→⇒→→→→→→
γ
γγγ
γ
γ
γ
−−
;
32333312
12
4
3
2
... iiiiiiii
qqq
→⇒→→→→→→
γ
γγγ
γ
γ
γ
−−
;
…
qqqqqqq
iiiiiiii
qqq
→⇒→→→→→→
γ
−
γγ
−
γ
γ
−
γ
−
γ
−
−−
111111
12
432
... ;
11
12
432
... iiiiiiii
qqqqqq
qqq
→⇒→→→→→→
γ
γγγ
γγγ
−−
.
Следовательно,
(
)
qq
iiiii
1321
...
−
=γ
. Теорема доказана.
Примеры.
1. Разложим цикл (1342) на множестве
{}
4;3;2;1=X в произведение транспозиций: (1342) = (12) (14) (13). Проверим
это равенство:
()()() ( )
1342
24
43
13
21
41
43
23
21
13
43
24
21
43
43
12
21
131412 =
=
=
.
2. Разложим подстановку
=α
9
9
85
87
76
65
12
43
43
21
в произведение транспозиций. Сначала разложим подстанов-
ку
α в произведение независимых циклов: α = (1324)(567)(8)(9) или
α
= (1324)(567), если циклы длины 1, т.е. (8) и (9), ото-
ждествить с тождественной подстановкой на множестве
{
}
9;8;7;6;5;4;3;2;1
=
X . Далее, разложив каждый из циклов в про-
изведение транспозиций, получим:
α
= (14) (12) (13) (57) (56).
Теорема 9.4.2. Любая подстановка α на множестве X представляется в виде произведения n – s транспозиций, где n –
количество элементов в множестве
X; s – количество циклов в представлении подстановки
α
в виде произведения независи-
мых циклов (включая циклы длины 1).
Доказательство. Подстановку α можно разложить в произведение независимых циклов (среди которых могут быть
циклы длины 1):
() ( ) () ( )
()( )
()
s
kkk
lljjii
n
n
............
...3
...3
21
21
111
21
=
αααα
=α
.
Оставим в данном представлении циклы длины 1, и поэтому nkkk
s
=
+
+
+
...
21
. Далее, каждый цикл представляется в
виде произведения
1−
i
k транспозиций
()
si ...,,2,1= . Действительно, если цикл длины
i
k не менее 2, то это вытекает из
теоремы 9.4.1, если же цикл длины
1=
i
k , то он никакого влияния на количество транспозиций не оказывает (при разложе-
нии подстановки в произведение независимых циклов или транспозиций мы такие циклы не указываем, отождествляя их с
тождественной подстановкой на множестве
X) – что соответствует 0111
=
−
=
−
i
k транспозициям. Подсчитаем общее коли-
чество транспозиций в данном разложении:
(
)( )
(
)
(
)
snskkkkkk
ss
−
=
−
+
+
+
=
−
+
+−+− ...1...11
2121
.
Теорема доказана .
Определение 9.4.1. Число n – s, где n – число элементов в множестве X, s – количество циклов, включая циклы длиной
1, в разложении подстановки α в произведение независимых циклов, называется
декрементом подстановки
α
.
Теорема 9.4.3. Четность подстановки α совпадает с четностью декремента подстановки α:
() ( )
sn−
−=α 1sgn .
Доказательство. По теореме 9.4.2 подстановку
α
можно представить в виде произведения n – s транспозиций:
sn−
τττ=α ...
21
, где
i
τ – транспозиция
()
sni
−
= ...,,2,1 . По теоремам 9.2.1 и 9.2.3 получим:
(
)( )
(
)
(
)
(
)
(
)
sn
snsn
−
−−
−=τττ=τττ=α 1sgn...sgnsgn...sgnsgn
2121
.
Теорема доказана.
Пример. Определим четность подстановки
=α
9
9
85
87
76
65
12
43
43
21
.
Как мы уже знаем, α = (1324) (567) (8) (9). Таким образом, n = 9, s = 4, n – s = 5 – нечетное число, следовательно, подста-
новка
α
нечетная.
Обратим внимание на то, что в теоремах 9.4.1 и 9.4.2 ничего не говорится о единственности представления подстановки
в виде произведения транспозиций. Легко убедиться, что представление подстановки в виде произведения транспозиций не
является единственным. В одном из предыдущих примеров мы могли бы написать для цикла (1342) = (12)
(14) (13) и другое

Страницы