Подстановки

Представлены понятия подстановки, умножения подстановок, единичной подстановки, четной и нечетной подстановок, транспозиции, лемма о нечетности транспозиции, знак подстановки, теорема о знаке произведения, свойства знаков подстановок

п.1. Симметрическая группа степени n.

Обозначим , где .

Определение. Симметрическая группа, определённая на множестве , называется симметрической группой степени . Элементами этой группы являются биекции, которые множество , которые называются подстановками степени .

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

Определение. Умножением подстановок называется их композиция.

Определение. Единичной (тождественной) подстановкой называется подстановка . Единичная подстановка все элементы оставляет на месте. Для каждой подстановки  определена обратная подстановка

Теорема 1. Алгебра, определенная на множестве  есть группа, которая называется группой подстановок степени , порядок группы равен .

п.2. Чётные и нечётные подстановки.

Пусть ,

Определение. Пусть - упорядоченная пара такая, что . Пара  называется инверсией подстановки , если

Определение. Подстановка  называется чётной, если она содержит чётное число инверсий .

- чётные подстановки.

Подстановка  называется нечётной, если она содержит нечётное число инверсий

- не чётные подстановки.

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

Пример.

 является транспозицией.

 не является транспозицией.

Лемма 1. Любая транспозиция есть нечётная подстановка.

Доказательство. Рассмотрим транспозицию , имеющую вид     .

Рассмотрим пару , где .

Если , то  - не инверсия,

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

Пусть ,  (так как - транспозиция). Тогда для пары

 имеем   пары  не образуют инверсию.

Пусть , . Для пары , где  возможны случаи:

а) пусть ,     пары , где  инверсии не образуют.

б) ,  имеем, если , то пара - инверсия.

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

Мы подсчитали число инверсий  таких, что  или .

Подсчитаем теперь число инверсий  таких, что  и , возможны случаи:

IV. ,  имеем   . Все такие пары образуют инверсию, число таких инверсий равно числу целых чисел в интервале , поэтому число таких инверсий равно

V. , ,  , значит такие пары не образуют инверсии.

VI.  имеем   , значит такие пары не образуют инверсии.

Следовательно, общее число инверсий в транспозиции - это число нечётное, значит транспозиция  нечётная подстановка. Лемма доказана.

п.3. Знак подстановки.

Пусть , - множество всех подстановок степени .

Определение. Функция  и  называется знаком числа .

 

Теорема 1.  . Знак произведения равен произведению знаков.

Доказательство.

если  или , то  и знак числа равен 0

пусть  и . Возможны случаи:

а)   

б)    

в)   

г)    

Определение. Функцией знак подстановки называется функция  .

Свойства знаков подстановок.

Пусть

1) . Знак подстановки  равен произведению знаков чисел

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

2) знак произведения двух подстановок равен произведению знаков этих подстановок, то есть  .

Доказательство. Запишем , тогда

Теорема 2. Функция знак подстановки обладает свойствами:

1)  

2) если - транспозиция, то

3)  

4)  если - транспозиция, то знак подстановки

Доказательство.

Пусть , - единичная подстановка, . Справедливо равенство:  (- должны быть одного знака) .

Следствие 1. Произведение подстановок одинаковой чётности – чётная подстановка.

Следствие 2. Произведение подстановок разной чётности – не чётная подстановка.

Следствие 3. Множество чётных подстановок относительно операций - единичные подстановки образуют группу – группу чётных подстановок.

п.4. Разложение подстановок. Произведение циклов.

Определение. Подстановка  называется циклом, если существует : , ,  а остальные элементы  остаются на месте. Цикл записывается в виде , - длина цикла. Каждая транспозиция является циклом длины 2.

Определение. Два цикла называются независимыми, если они не имеют общих действительно перемещаемых символов.  , - независимые циклы.

Свойства циклов.

каждая подстановка единственным образом с точностью до порядка сомножителей раскладывается произведением независимых циклов

независимые циклы попарно коммутируют, то есть если  и - независимые циклы, то

каждая подстановка есть произведение транспозиции:  или

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

Доказательство.

Докажем равенство  . Транспозиция- это цикл длины 2. Равенство  - это равенство функций.

Область определения функций в левой и правой частях равенства равны. Проверим, что эти функции принимают одинаковые значения на одинаковых элементах. Значение левой подстановки от  равно  по определению цикла. В правой части – композиция. Сначала на  действует внутренняя подстановка – она переводит  в , в следующих подстановках нет , поэтому они оставляют  на месте, значит подстановка в правой части  перевела в . Рассмотрим как действует подстановка на элемент . Левая подстановка  переводит в  по определению цикла. В правой подстановке последняя внутренняя подстановка  переводит в , так как подстановка - биекция. Предпоследняя внутренняя  переводит в . Следующие подстановки (транспозиции)  оставляют на месте, так как в них нет , значит правая подстановка  переводит в . Таким образом, значения левой и правой подстановок в равенстве равны. Рассмотрим как действуют подстановки на элемент . Левая подстановка  переводит в  (по определению цикла). Последняя внутренняя  оставляет на месте, вторая внутренняя  переводит в , третья внутренняя  переводит в . Значит правая внутренняя подстановка  переводит в . Таким образом, значения левой и правой подстановок равенства на элементе  равны.

Рассмотрим, как действуют подстановки на элемент . Левая подстановка  переводит в  (по определению цикла), правая подстановка  переводит в . Получили, что числа  правая и левая подстановки в равенстве  переводят одинаково, остальные числа они оставляют на месте. То есть все одинаковые элементы подстановки в равенстве   переводят одинаково.

Вывод: функции в равенстве   равны.

знак цикла  

Доказательство. В формуле   все транспозиции в правой части – нечётные подстановки. Их , тогда знак .

Пример.

получить из перестановки  другую перестановку  последовательно переставляя по два элемента.

Решение.

Составим подстановку: первую перестановку- в первую строку, вторую перестановку- во вторую строку. Разложим эту подстановку произведением циклов

.

В перестановке  поменяем местами символы 6 и 8. Получим ; меняем 4 и 5, получаем перестановку ; меняем 3 и 4, получим ; меняем 1 и 2, получим .

Получить из перестановки  другую перестановку , последовательно переставляя по два элемента  

Список литературы

Е.Е. Маренич, А.С. Маренич. Вводный курс математики. Учебно-методическое пособие. 2002

В.Е. Маренич. Журнал «Аргумент». Задачи по теории групп.

Кострикин А.И. Введение в алгебру. Ч.1 Основы алгебры. – М.: Физмат лит-ра, 2000

Кострикин А.И. Введение в алгебру. Ч.2 Основы алгебры. – М.: Физмат лит-ра, 2000

Кострикин А.И. Введение в алгебру. Ч.3 Основные структуры алгебры. – М.: Физмат лит-ра, 2000

Кострикин А.И. Сборник задач по алгебре. Изд. третье – М.: Физмат лит-ра, 2001

Для подготовки данной работы были использованы материалы с сайта http://referat.ru/

Дата добавления: 05.10.2011