Группа перестановок. Знак перестановки

Напомним, что если – множество из -элементов, , то перестановкой степени называется взаимнооднозначное отображение . – множество всех перестановок степени : .

Лемма 1: Число различных перестановок равно

Лемма 2: Множество перестановок образует группу относительно умножения, так что , обратный элемент получается сменой строк (Не коммутативная группа).

Отметим, что если в перестановке поменять местами любые столбцы, то получится та же перестановка.

Углубим проведенное ранее исследование:

Определение 1: Пусть – перестановка степени , пусть . Тогда пара называется инверсией для , если .

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

Знак перестановки – это ,где – число инверсий.

Обозначается .

Итак, если – четная, то , и если – нечетная, то .

Пример: . Пары . Их них подчеркнутые – инверсии. Таким образом, , т.е. – четная.

Теорема 1:

1. Знак единичной перестановки равен 1.

2. Если .

3. .

Доказательство: 1. В единичной перестановке инверсий нет .

2. Пусть – множество инверсий относительно , а – множество инверсий относительно .

Легко видеть, что если , то . Следовательно, между множествами устанавливается взаимнооднозначное соответствие

.

1. Пусть – множество инверсий относительно ,

– множество инверсий относительно ,

– множество инверсий относительно : .

Тогда надо доказать, что , т.е. – четное число – это надо доказать.

Пусть ,

,

,

.

Введем следующее обозначение: пусть - это множество пар . Тогда справедлива следующая множественная схема:

Между множествами существует взаимнооднозначное соответствие : .

Поэтому из картинки видно , т.е. четное число. ▄

Следствие: .

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

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

Теорема 2: Транспозиция – нечетная перестановка.

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

Замечание: Произведение вида означает, что в нижней строке надо поменять местами и .

? Что означает .

Пример .

Теорема 3: Каждая перестановка является произведением конечного числа транспозиций.

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

Пример:

т.е. .

Аналогично в общем случае.

Пусть на втором шаге поменяются местами . Тогда ввиду замечания .

Упражнение: Каждая перестановка является произведением конечного числа транспозиций вида .

.

Теорема 4: При всех разложениях перестановки в произведения транспозиций, четность числа транспозиций одна и та же; она совпадает с четностью перестановки.

Доказательство: Пусть , где – транспозиция. Тогда знак равен знаку произведения транспозиций – четно, если – четно.

Поиск по сайту: