ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 3457
Скачиваний: 14
42
Глава 2. Алгебраические объекты; Алгебра многочленов
графов вида
Рис. 10
Так граф, рассмотренной в примере 1 перестановки
ϕ,
имеет вид
Рис. 11
Определение 6.
Две перестановки
ϕ, ψ
∈
S
n
называются
взаимно про-
стыми,
если их множества подвижных элементов не пересекаются.
Например, взаимно простыми будут перестановки
1 2 3 4
3 2 1 4
,
1 2 3 4
1 4 3 2
.
Лемма.
Взаимно простые перестановки перестановочны.
Доказательство.
Пусть
f, ϕ
– две взаимно простые перестановки из
S
(
A
n
)
и
a
∈
A
n
. Если
a
– неподвижная точка обеих перестановок
f
и
ϕ
, то
(
f
◦
ϕ
)(
a
) =
f
(
ϕ
(
a
)) =
f
(
a
) =
a
и аналогично
(
ϕ
◦
f
)(
a
) =
a.
Пусть теперь
b
=
f
(
a
)
6
=
a
и, значит,
f
(
b
)
6
=
b
(иначе отображение
f
не
инъективно). Следовательно,
ϕ
(
a
) =
a
и
ϕ
(
b
) =
b.
Тогда
(
f
◦
ϕ
)(
a
) =
f
(
ϕ
(
a
)) =
f
(
a
) =
b,
(
ϕ
◦
f
)(
a
)) =
ϕ
(
f
(
a
)) =
ϕ
(
b
) =
b,
т.е.
f
◦
ϕ
=
ϕ
◦
f.
Лемма доказана.
Т е о р е м а 5.
Каждую перестановку
f
∈
S
(
A
n
)
можно однозначно
(с точностью до порядка сомножителей) представить в виде произведения
взаимно простых циклов.
§
6
.
Группы перестановок
43
Доказательство.
Каждому элементу
a
из
A
n
поставим в соответствие
множество
{
f
(
a
)
, f
2
(
a
)
, . . .
}
, которое называется
орбитой
элемента
a
. То-
гда множество
A
подвижных точек из
A
n
представляется в виде объедине-
ния
m
S
j
=1
M
j
взаимно непересекающихся множеств
M
j
,
1
≤
j
≤
m
, каждое
из которых является орбитой некоторого элемента из
A
n
, содержит более
одной точки и поэтому
f
(
b
)
∈
M
j
∀
b
∈
M
j
(см. упражнение 3). Суже-
ние
f
j
:
M
j
→
M
j
перестановки
f
на каждое множество
M
j
(напомним
f
j
(
b
) =
f
(
b
)
∀
b
∈
M
j
;
см. определение 8 из
§
3) является циклом и однознач-
но определяется перестановкой
f
. Каждую из перестановок
f
j
расширим до
некоторой перестановки
f
j
:
A
n
→
A
n
,
положив
f
j
(
b
) =
f
j
(
b
)
∀
b
∈
M
j
и
f
j
(
b
) =
b
∀
b
∈
M
i
, i
6
=
j
(
f
j
называется
расширением
перестановки
f
j
на
A
n
).
Перестановки
f
j
,
1
≤
j
≤
m
будут циклическими, и множество подвижных
точек для
f
j
совпадает с множеством
M
j
. Поскольку
f
j
(
b
)
∈
M
j
∀
b
∈
M
j
,
1
≤
j
≤
m,
то перестановки
f
j
,
1
≤
j
≤
m
взаимно просты, причем
f
=
f
1
◦
f
2
◦ · · · ◦
f
m
(порядок их не играет роли ввиду перестановочности сомножи-
телей; см. лемму). Теорема доказана.
Пример 2.
Для перестановки
ϕ
=
1 2 3 4 5 6 7 8
2 3 1 6 7 4 5 8
найдем разные орбиты. Имеем
ϕ
(1) = 2
, ϕ
(2) = 3
, ϕ
(3) = 1;
ϕ
(4) = 6
,
ϕ
(6) = 4;
ϕ
(5) = 7
, ϕ
(7) = 5;
ϕ
(8) = 8
.
Таким образом, орбиты переста-
новки
ϕ
имеют вид:
M
1
=
{
1
,
2
,
3
}
, M
2
=
{
4
,
6
}
, M
3
=
{
5
,
7
}
.
Сужения
перестановки
ϕ
на эти множества являются перестановками вида
ϕ
1
=
1 2 3
2 3 1
, ϕ
2
=
4 6
6 4
, ϕ
3
=
5 7
7 5
.
Расширениями этих перестановок на множество
A
8
(см. доказательство тео-
ремы 5) являются перестановки
ϕ
1
=
1 2 3 4 5 6 7 8
2 3 1 4 5 6 7 8
, ϕ
2
=
1 2 3 4 5 6 7 8
1 2 3 6 5 4 7 8
,
ϕ
3
=
1 2 3 4 5 6 7 8
1 2 3 4 7 6 5 8
.
Поэтому
ϕ
=
ϕ
1
◦
ϕ
2
◦
ϕ
3
.
Теорему 5 можно сформулировать по-иному, используя следующее
44
Глава 2. Алгебраические объекты; Алгебра многочленов
Определение 7.
Подмножество
G
0
из группы
G
называется
системой
образующих
группы
G
, если каждый элемент из
G
можно представить в виде
произведения элементов из
G
◦
.
Таким образом, имеет место
Т е о р е м а 6.
Множество всех циклических перестановок является
системой образующих группы перестановок
S
(
A
n
)
.
Пусть
ϕ
=
a
1
. . . a
k
−
1
a
k
a
k
+1
. . . a
n
a
2
. . .
a
k
a
1
a
k
+1
. . . a
n
– некоторая циклическая перестановка. Тогда ее можно представить в виде
произведения транспозиций
ϕ
2
◦ · · · ◦
ϕ
k
, где
ϕ
j
∈
S
(
A
n
)
– транспозиция,
переставляющая элементы
a
j
−
1
и
a
j
,
2
≤
j
≤
k
. Отсюда, используя теорему 2,
получаем, что
sign
(
ϕ
) = (
−
1)
k
−
1
,
где
k
– длина цикла
ϕ
. Применяя теорему
4, получаем, что имеет место
Т е о р е м а 7.
Транспозиции из группы
S
(
A
n
)
являются системой
образующих этой группы, и для любой перестановки
ϕ
имеет место формула
sign
(
ϕ
) = (
−
1)
k
1
+
···
+
k
m
−
m
,
где
k
1
, . . . , k
m
– длины взаимно простых циклов,
произведением которых является перестановка
ϕ, m
– их число.
Пусть
ϕ
– перестановка из
S
(
A
n
)
. Тогда множество перестановок ви-
да
ϕ, ϕ
2
, . . .
конечно, и поэтому существуют такие числа
m, k, m < k,
что
ϕ
k
=
ϕ
m
.
Тогда
e
=
ϕ
−
k
ϕ
k
=
ϕ
−
k
ϕ
m
=
ϕ
m
−
k
, т.е.
ϕ
m
−
k
=
e.
Таким образом,
для любой перестановки
ϕ
существует такое натуральное
s
, что
ϕ
s
=
e.
Этот
факт оправдывает следующее
Определение 8.
Пусть
ϕ
∈
S
(
A
n
)
. Наименьшее из натуральных чисел
m
таких, что
ϕ
m
=
e,
называется
порядком перестановки
.
Пример 3.
Для циклической перестановки вида
ϕ
=
a
1
. . . , a
k
−
1
, a
k
, a
k
+1
. . . , a
n
a
2
. . . ,
a
k
, a
1
, a
k
+1
. . . , a
n
порядок ее равен
k
, т.е. длине цикла.
Т е о р е м а 8.
Порядок перестановки
ϕ
∈
S
(
A
n
)
, раскладывающейся
в произведение взаимно простых циклов длины
k
1
, . . . , k
m
соответственно,
есть наименьшее общее кратное чисел
k
1
, . . . , k
m
.
Доказательство.
Согласно теореме 5, перестановку
ϕ
можно предста-
вить в виде взаимно простых циклов:
ϕ
=
ϕ
1
◦· · ·◦
ϕ
m
. В силу леммы взаимно
простые циклы перестановочны и поэтому имеет место равенство
ϕ
k
= (
ϕ
1
◦
ϕ
2
◦ · · · ◦
ϕ
m
)
◦ · · · ◦
(
ϕ
1
◦
ϕ
2
◦ · · · ◦
ϕ
m
)
|
{z
}
k
раз
=
ϕ
k
1
◦
ϕ
k
2
◦ · · · ◦
ϕ
k
m
.
§
6
.
Группы перестановок
45
Из этого равенства следует (проверьте !), что
ϕ
k
=
e
тогда и только тогда,
когда
ϕ
k
j
=
e
∀
j
= 1
, . . . , m
. Если перестановки
ϕ
1
, . . . , ϕ
m
есть циклы длины
k
1
, . . . , k
m
, соответственно, т.е. имеют порядок
k
1
, . . . , k
m
, то наименьшее чис-
ло
k
, для которого выполняются все равенства
ϕ
k
j
=
e,
1
≤
j
≤
m
, равняется
наименьшему общему кратному чисел
k
1
, . . . , k
m
. Теорема доказана.
Т е о р е м а 9 (теорема Кэли).
Каждая конечная группа
G
изо-
морфна некоторой подгруппе группы перестановок
S
(
G
)
группы
G
.
Доказательство.
Пусть
G
=
{
g
0
=
e, g
1
, . . . , g
n
−
1
}
.
Каждому элементу
g
группы
G
поставим в соответствие перестановку
ϕ
= Φ(
g
)
∈
S
(
G
)
этой
группы, определенную таблицей
ϕ
= Φ(
g
) =
g
0
g
1
g
2
. . . ,
g
n
gg
0
gg
1
gg
2
. . . , gg
n
.
Ясно, что
Φ(
g
1
g
2
) = Φ(
g
1
)
◦
Φ(
g
2
)
,
т.е. построенное отображение
Φ :
G
→
S
(
G
)
является гомоморфизмом групп. Поскольку образ
Φ(
G
)
го-
моморфизма
Φ
является подгруппой в
S
(
G
)
(см. упражнение 21 из
§
5) и
поскольку
Φ
– инъективное отображение (докажите !), то
Φ
устанавливает
биективное отображение между
G
и подгруппой
Φ(
G
)
группы
S
(
G
)
. Теорема
доказана.
Т е о р е м а 10 (теорема Лагранжа).
Пусть
G
– конечная группа.
Тогда для любой нормальной подгруппы
H
из
G
имеет место равенство
|
G
|
=
|
H
| |
G/H
|
,
где
|
S
|
обозначает число элементов конечного множества
S
.
Доказательство.
Из леммы 2
§
5
следует, что имеет место равенство
m
S
i
=1
g
i
H
=
G,
причем классы эквивалентности
g
1
H, . . . , g
m
H
взаимно непе-
ресекаются, имеют одно и то же число элементов, равное
|
H
|
, и
m
=
|
G/H
|
.
Поэтому
|
G
|
=
|
H
| |
G/H
|
. Теорема доказана.
Замечание.
Нами сформулирован
"ослабленный" вариант теоремы
Лагранжа. В действительности в теореме Лагранжа (см., например, [9]) усло-
вия нормальности подгруппы
H
нет. В частности, отсюда следует, что число
|
G
|
делится на число
|
H
|
.
Определение 9.
Группа
G
называется
циклической
, если существует
элемент
a
∈
G
такой, что для всякого элемента
g
∈
G
существует целое
число
n
∈
Z
такое, что
g
=
a
n
.
Примером циклической группы являются группы
Z
и
Z
m
.
Ясно, что
всякая циклическая группа абелева.
46
Глава 2. Алгебраические объекты; Алгебра многочленов
Упражнения к § 6
1. Докажите, что подгруппа из
S
6
, состоящая из перестановок вида
1 2 3 4 5 6
1 2 3 4 5 6
,
1 2 3 4 5 6
2 3 1 6 4 5
,
1 2 3 4 5 6
3 1 2 5 6 4
,
1 2 3 4 5 6
4 5 6 1 2 3
,
1 2 3 4 5 6
5 6 4 3 2 1
,
1 2 3 4 5 6
6 4 5 2 3 1
,
изоморфна группе
S
3
.
2. Разложите следующие перестановки в произведение простых циклов и
проверьте их четность (постройте графы этих перестановок)
ϕ
1
=
1 2 3 4 5
4 3 2 5 1
, ϕ
2
=
1 2 3 4 5 6
5 6 1 4 3 2
,
ϕ
3
=
1 2 3 4 5 6 7 8 9
7 9 3 1 5 8 4 2 6
.
3. Докажите указанные при доказательстве теоремы 5 три свойства
разложения
A
n
=
m
S
j
=1
M
j
.
4. На стенах круглого зала картинной галереи висели картины. Как-то ре-
шили разместить их в другом порядке, меняя картины, которые висят
рядом. Всегда ли можно с помощью таких перемещений разместить кар-
тины как задумано ?
5. Докажите, что перестановка
ϕ
четная, если ее порядок – нечетное число.
6. Найдите порядок следующих перестановок
a
)
1 2 3 4 5 6 7 8 9
3 5 7 9 6 8 1 2 4
,
b
)
1 2 3 4 5 6 7 8 9 10
3 5 4 6 7 8 9 2 1 10
.
7. Какой наивысший порядок могут иметь перестановки на множестве, со-
стоящем из а) пяти элементов, б) десяти элементов ?
8. Сколько существует перестановок 15-го порядка на множестве из 8 эле-
ментов ?