11.1. Определение. Пусть M -- некоторое множество. Подстановкой на M назовем взаимно однозначное отображение множества M на себя. Обозначим через S(M) множество всех подстановок на M.
11.2. Группа подстановок
Пусть a и b -- две подстановки из S(M). Назовем произведением ab этих подстановок композицию отображений a, b, то есть ab -- такой элемент из S(M), что m(ab)=(ma)b для всех
Теорема. Множество S(M) является группой относительно введенной операции умножения, то есть в S(M) есть единичный элемент e со свойством: ex=xe=x для любого ; для любого есть , что xy=yx=e, и операция умножения ассоциативна.
Доказательство. Нам необходимо проверить три аксиомы. В S(M)
имеется единичный элемент -- это тождественное отображение, которое обозначим
буквой e. Известно также, что для всякого взаимно однозначного
отображения x множества M на M существует обратное отображение
x-1, для которого xy=yx=e. Осталось проверить аксиому ассоциативности.
Пусть a, b, c
-- подстановки из
-- элемент множества M. Вычисляя образ
элемента m при отображениях (ab)c и a(bc), мы убеждаемся, что эти
отображения совпадают:
11.3. Изображение подстановок. Число элементов в Sn
В дальнейшем мы будем рассматривать только ситуацию, когда
M -- конечное множество, состоящее из натуральных чисел 1,2,...,n.
Элемент множества M часто называют символом. В этом случае принято
группу подстановок на множестве
обозначать через Sn
и называть симметрической группой степени n.
Пусть .
Подстановке a мы сопоставим табличку
Упражнение. Доказать, что группа подстановок Sn при n>2 некоммутативна, то есть найти две такие подстановки a,b, что .
11.4. Независимые подстановки. Разложение в циклы
Пусть
.
Для данной подстановки
обозначим через
множество
действительно перемещаемых подстановкой a символов, т.е. множество
всех таких элементов ,
для
которых .
Пусть
и
j1,...,jn-r --
остальные символы множества M. Тогда
Определение. Подстановки a, b называются независимыми, если они не имеют общих действительно перемещаемых символов, т.е. если .
Лемма. Пусть a,b -- независимые подстановки, тогда ab=ba и . Если i -- символ из M, то i(ab)=i, когда ; i(ab)=ia, когда ; i(ab)=ib, когда .
Доказательство. Разберем три имеющиеся возможности для данного символа i. 1) . Тогда , откуда . 2) . Тогда . Из представления (3) для подстановки a вытекает, что множества и совпадают. Поэтому . Так как , то jb=j, откуда . 3) . Тогда , поэтому ja=j. Имеем . Из этих рассмотрений вытекает утверждение леммы.
Пусть a - неединичная подстановка из Sn и . Тогда . Пусть - такое максимальное множество различных символов, что i1a=i2,...,ir-1a=ir. Ввиду условия максимальности . Можно утверждать, что ira=i1, так как символы i2,...,ir имеют своими прообразами символы i1,...,ir-1. Множество назовем нетривиальной орбитой подстановки a (тривиальная орбита состоит из неподвижного элемента). Отметим, что все элементы орбиты получаются из любого ее символа с помощью действий отображением a. Отсюда следует, что любые две орбиты подстановки a либо не пересекаются, либо совпадают, и что множество разбивается в объединение непересекающихся нетривиальных орбит.
Определение. Подстановка называется циклом, если она имеет точно одну нетривиальную орбиту. Другими словами, найдутся такие различные символы i1,...,ir, что i1a=i2,...,ir-1a=ir и . Число r называется длиной цикла c.
Данный цикл c принято для краткости изображать в виде одной
строки
Теорема. Любая неединичная подстановка однозначно с точностью до перестановки множителей разлагается в произведение независимых циклов.
Доказательство. Ранее мы отмечали, что множество разбивается в объединение непересекающихся нетривиальных орбит. Пусть -- такое разбиение, где и . Рассмотрим циклы с1=(i1,...,ir),..., сp=(j1,...,js). По построению эти циклы независимы. Покажем, что . Рассмотрим произвольный символ i из M. Если , то . Тогда . Пусть , например, . По лемме . Мы установили, что отображения a и совпадают. Перестановочность элементов c1,...,cp следует из леммы. Докажем единственность разложения. Пусть подстановка a разложена некоторым другим способом в произведение независимых циклов: . Из леммы следует, что для каждого цикла подстановка a действует на множестве также, как и dq. Поэтому будет нетривиальной орбитой для a (все символы этого множества получаются из одного с помощью действия a) и -- разбиение множества на нетривиальные орбиты. Такого сорта разбиение однозначно. Поэтому p=l и, с точностью до переиндексации, . Так как на множестве L1 действие циклов c1 и d1 равносильно действию a, то c1=d1. Аналогично c2=d2,...,cp=dp. Теорема доказана.
Упражнение. Произведение m подстановок, каждая из которых равна a, обозначим через am. Доказать, что am= e тогда и только тогда, когда число m делится на наименьшее общее кратное длин независимых циклов, на которые разлагается подстановка a.
11.5. Разложение на транспозиции. Четность
Транспозицией называется цикл длины 2, т.е. цикл вида (ij).
Пусть
c=(i1,...,ir) -- цикл длины r. Непосредственно
проверяется,
что цикл c разлагается в следующее произведение (r-1)-ой транспозиции:
Теорема. При различных разложениях подстановки в произведение транспозиций четность числа множителей одна и та же.
Доказательство. Нам потребуются следующие соотношения для
транспозиций, которые проверяются непосредственно.
1)
(ij)-1=(ij)=(ji);
2)
(ij)(kl)=(kl)(ij), если i,j,k,l -- различные символы;
3)
(ij)(ik)=(ik)(kj), если i,j,k -- различные символы.
Переходим к доказательству теоремы. Пусть подстановка a
разлагается двумя способами в произведение транспозиций:
.
Тогда получаем следующее разложение единичной
подстановки
в произведение r+s транспозиций. Нужно
доказать, что число r+s четное.
Итак, достаточно установить, что в произвольном разложении
единичной подстановки на транспозиции
Доказанная теорема позволяет ввести следующее
Определение. Подстановка называется четной, если она разлагается в произведение четного числа транспозиций. В противном случае подстановка называется нечетной.
Выше мы замечали, что всякая подстановка разлагается в произведение транспозиций, число которых равно декременту. Поэтому четность подстановки совпадает с четностью декремента. Введем функцию -- знак подстановки a. По определению полагаем , если a - четная подстановка, и , если a -- нечетная подстановка. Эта функция удовлетворяет соотношению .
Упражнение. Доказать, что число четных подстановок на множестве из n символов равняется n!/2.
11.6. Явная форма для определителя матрицы.
Полученные результаты о подстановках позволяют выписать явную формулу для определителя квадратной матрицы.
Теорема. Пусть
. Тогда
Доказательство. Воспользуемся индукцией по n.
При n=1 теорема очевидным
образом верна. Пусть n>1. Разложим det A по последнему столбцу и
воспользуемся индукцией для вычисления алгебраических дополнений: