656_Lytkina_D.V._Algebraicheskie_struktury_

3. Циклические группы. Группа подстановок

Циклическая группа – это группа, все элементы которой являются степенями некоторого порождающего элемента:

Порядком элемента циклической группы называется наименьшая степень, в которой он равен единице. В случае, если такой степени не существует, говорят, что элемент имеет бесконечный порядок. Циклическая группа, порожденная элементом a, обозначается как a.

Порядок циклической группы равен порядку порождающего элемента. Циклическая группа может быть бесконечной, например, группа , .

Порядок бесконечной циклической группы равен бесконечности. Порядок конечной циклической группы равен числу элементов носителя. Примером циклической группы является мультипликативная группа 1.

Подстановка – это взаимно однозначное отображение непустого конечного множества на себя, т.е. :M M . Без ограничения общности можно считать, что M 1,2,...,n . Подстановку множества из n элементов

называют подстановкой степени n. Обычно, если множество M конечно, для записи подстановки используется табличная форма

неподвижным. В противном случае элемент называется действительно перемещаемым. Тождественная подстановка – это подстановка, состоящая только из неподвижных элементов, она обычно обозначается как .

Множество всех действительно перемещаемых элементов подстановки

12

Нетрудно убедиться, что система S(M), является группой (упр. 3.6). Для

любой подстановки обратная подстановка определяется как обратное отображение:

число, такое, что ks 1 ks k1 (такое число существует, так как M конечно).

Множество k1,k2,...ks называется нетривиальной орбитой подстановки

длины s. Орбита, состоящая из одного элемента, называется тривиальной. Очевидно, что этот единственный элемент является неподвижным.

Множество M относительно подстановки разбивается на объединение орбит, а supp( ) – на объединение нетривиальных орбит:

1,2,3,4,5,6,7 1,2,4 3,5 6,7 .

орбиты

В соответствие с разбиением множества supp( ) на объединение непересекающихся орбит существует удобная форма записи подстановки в виде произведения независимых циклов.

где i1,i2,...,is,k1,...,kt 1,2,...,n , называется циклом длины s. Цикл длины 2

называется транспозицией. Циклы и называются независимыми, если supp( ) supp( ) . Нетрудно убедиться, что если множество M относительно подстановки разбивается на объединение m орбит

supp( ) i11,i21,...,is11 i12,i22,...,is22 ... i1m,i2m,...,ismm ,

то подстановка представима в виде произведения m независимых циклов:

13

Такое представление подстановки называют разложением в произведение независимых циклов и записывают в виде

i11,i21,...,i1s1 i12,i22,...,is22 ... i1m,i2m,...,ismm

или, если необходимо указать неподвижные элементы, в виде

i11,i21,...,i1s1 i12,i22,...,is22 ... i1m,i2m,...,ismm k1 ... kt ,

где k1 ,k2 ,...,kt M \ m i1j,i2j,...,isjj – неподвижные элементы .

j 1

Каждая подстановка порождает циклическую группу с операцией .

Пример 1. Определить циклическую группу, порожденную подстановкой

Решение. Тождественная подстановка получится как квадрат порождающего элемента, следовательно, порядок группы равен 2, обратный к порождающему элементу равен ему самому:

1 .

Получаем, что ; , . Никаких других элементов мы не получим,

например, при возведении порождающего элемента в третью степень имеем

Запишем результат применения к элементам группы операции в виде таблицы умножения (таблицы Кэли):

Решение. Найдем орбиты подстановки и соответствующие им

15

Упражнения и задачи

3.1. Доказать, что для любого элемента циклической группы верно

3.2.Доказать, что предыдущее утверждение имеет место для любого элемента произвольной группы.

3.3.Доказать, что подгруппа циклической группы также является циклической.

3.4.Доказать, что порядок подгруппы конечной циклической группы является делителем порядка группы.

3.5.Доказать, что любая подгруппа аддитивной группы целых чисел имеет вид

n , , n , где n 0, n, 2n, 3n,... .

3.6.Доказать, что если a,b,c– элементы некоторой группы, то

а) ab и ba имеют одинаковый порядок;

б) aba 1 и b имеют одинаковый порядок;

в) abc,bca,cab имеют одинаковый порядок.

3.7.Доказать, что S(M), – группа.

3.8.Доказать, что каждая нетождественная подстановка разлагается в произведение транспозиций.

3.9.Доказать, что S(M) M !.

3.10.Записать следующие подстановки в виде произведения независимых циклов:

3.11.Записать следующие подстановки в виде произведения независимых циклов:

3.12.В следующих подстановках перейти от записи в виде произведения независимых циклов к записи таблицей:

а) (1,5)(2,3,4);

б) (1,3)(2,5)(4);

в) (1,2)(3,4)...(2n 1,2n).

3.13.Вычислить:

3.14. Найти подстановку, обратную данной:

в) (1,5)(2,3,4);

17

4. Кольца вычетов. Поля Галуа. Кольцо квадратных матриц

Говорят, что числа a и b равны по модулю n (n ), если они имеют одинаковый остаток от деления на n. При этом используется запись a bmodn.

Кольцом вычетов (по модулю n) называется кольцо n, , ,

n {0,1,2,...,(n 1)}, с операциями сложения и умножения по модулю n,

определяемыми следующим образом:

a b: a b modn n;

a b: a b modn n.

Поле Галуа (GF) – это любое конечное поле. В частности, конечным полем, а следовательно, и полем Галуа является кольцо p, , где p –

простое число (упр. 4.2).

отметить, что операции в поле Галуа в общем случае не обязательно являются сложением и умножением по модулю n.

Пример 1. Задать операции сложения и умножения в поле F4 4, , .

Решение. Определим в первую очередь операцию умножения. Умножение в F4 4, , невозможно определить как умножение по модулю

(см. упр. 2.4).

Рассмотрим поочередно все оставшиеся варианты. Допустим, 2 2 1, тогда 2 3 3, т.е. 2=1 – противоречие. Остается вариант 2 3 1, 2 2 3, и, следовательно, 3 3 2. Запишем таблицу Кэли:

Определить операцию сложения как сложение по модулю 4 тоже не получится, так как в этом случае умножение относительно сложения не будет обладать свойством дистрибутивности (проверить самостоятельно). Итак, приступим к последовательному заполнению таблицы Кэли для сложения в F4 4, , .

Так как a 0 0 a a (по определению нуля), то имеем

Сумма 1 2 не может быть равна 2 (или 1), так как это означает, что 1 (или 2) – нейтральный элемент по сложению (нуль). Предположим, 1 2 0 (т.е. 2 – противоположный к 1). Тогда

3 (1 2) 3 0 0.

С другой стороны,

3 (1 2) 3 1 3 2 3 1.

Следовательно, 3+1=0, значит, 3 также является противоположным элементом к 1. Получаем противоречие, так как противоположный элемент должен быть только один. Остается единственный вариант:1 2 3. Рассуждая аналогичным образом, получим, что 1 3 0, 1 3 1, 1 3 3 и 2 3 0, 2 3 2, 2 3 3. Следовательно, 1 3 2 и 2 3 1.

С учетом коммутативности операции, таблица Кэли принимает вид

У каждого элемента поля должен быть противоположный элемент, следовательно, недостающие элементы таблицы – нули.