11. Подстановки

11.1. Определение. Пусть M -- некоторое множество. Подстановкой на M назовем взаимно однозначное отображение $a:M\rightarrow M$ множества M на себя. Обозначим через S(M) множество всех подстановок на M.

11.2. Группа подстановок

Пусть a и b -- две подстановки из S(M). Назовем произведением ab этих подстановок композицию отображений a, b, то есть ab -- такой элемент из S(M), что m(ab)=(ma)b для всех $m\in M$

Теорема. Множество S(M) является группой относительно введенной операции умножения, то есть в S(M) есть единичный элемент e со свойством: ex=xe=x для любого $x\in S(M)$; для любого $x\in S(M)$ есть $y\in S(M)$, что xy=yx=e, и операция умножения ассоциативна.

Доказательство. Нам необходимо проверить три аксиомы. В S(M) имеется единичный элемент -- это тождественное отображение, которое обозначим буквой e. Известно также, что для всякого взаимно однозначного отображения x множества M на M существует обратное отображение x^-1, для которого xy=yx=e. Осталось проверить аксиому ассоциативности. Пусть a, b, c -- подстановки из $S(M),\ m$ -- элемент множества M. Вычисляя образ элемента m при отображениях (ab)c и a(bc), мы убеждаемся, что эти отображения совпадают:

m((ab)c)=(m(ab))c=((ma)b)c,

m(a(bc))=(ma)(bc)=((ma)b)c.

Теорема доказана.

11.3. Изображение подстановок. Число элементов в S_n

В дальнейшем мы будем рассматривать только ситуацию, когда M -- конечное множество, состоящее из натуральных чисел 1,2,...,n. Элемент множества M часто называют символом. В этом случае принято группу подстановок на множестве $M=\{1,2,...,n\}$ обозначать через S_n и называть симметрической группой степени n. Пусть $a\in S_n$. Подстановке a мы сопоставим табличку

$$\left( \begin{array}{llll} 1&2&...&n\\ i_1&i_2&...&i_n \end{array} \right) ,\hspace{3 cm} (1)$$

где $i_1=1a,\ i_2=2a,...,i_n=na$ -- образы элементов 1,2,...,n при отображении a. Очевидно, что такая табличка содержит полную информацию об отображении a, поскольку она определяет образ каждого элемента из M. Поэтому множество подстановок S_n можно отождествить с множеством табличек вида (1). При таком отождествлении

$$e= \left( \begin{array}{llll} 1&2&...&n\\ 1&2&...&n \end{array} \right) .$$

Можно также изображать подстановку p произвольной табличкой вида

$$\left( \begin{array}{llll} i_1&i_2&...&i_n\\ j_1&j_2&...&j_n \end{array} \right) ,\hspace{3 cm} (2)$$

где $\{i_1,i_2,...,i_n\}= \{j_1,j_2,...,j_n\}= \{1,2,...,n\},\ i_1p=j_1,\ i_2p=j_2,...,i_np=j_n$, т.е. в первой строке числа 1,2,...,n могут стоять не обязательно в естественном порядке. При этом две таблички вида (2) определяют одну и ту же подстановку, если одна из них получается из другой перестановкой столбцов. Используя такое представление, легко находить обратный элемент к данной подстановке

$$p=\left( \begin{array}{llll} i_1&i_2&...&i_n\\ j_1&j_2&...&j_n \end{array} \right).$$

Для этого нужно просто поменять местами строки соответствующей таблички:

$$p^{-1}=\left( \begin{array}{llll} j_1&j_2&...&j_n\\ i_1&i_2&...&i_n \end{array} \right).$$

Посчитаем число элементов в S_n. Очевидно, что при всевозможных подстановках элемент 1 может отображаться в любой из элементов множества $\{1,2,...,n\}$, т.е. для образов этого элемента существует n возможностей. Если мы зафиксируем одну из этих возможностей, скажем, 1 отображается в $k\ (1\leq k\leq n)$, то элемент 2 может отображаться в любой из элементов множества $\{1,...,k-1,k+1,...,n\}$, состоящего из k-1 элементов. То есть для образов пары $\{1,2\}$ мы имеем n(n-1) возможностей. Продолжая это рассуждение, убеждаемся, что число различных подстановок на множестве $\{1,2,...,n\}$ равно n!.

Упражнение. Доказать, что группа подстановок S_n при n>2 некоммутативна, то есть найти две такие подстановки a,b, что $ab\neq ba$.

11.4. Независимые подстановки. Разложение в циклы

Пусть $M=\{1,2,...,n\}$. Для данной подстановки $a\in S_n$ обозначим через $\mu (a)$ множество действительно перемещаемых подстановкой a символов, т.е. множество всех таких элементов $i\in M$, для которых $ia\neq i$. Пусть $\mu (a)= \{i_1,...,i_r\}$ и j₁,...,j_n-r -- остальные символы множества M. Тогда

$$a=\left( \begin{array}{lllllll} i_1&...&i_r&j_1&j_2&...&j_{... ..._r&j_1&j_2&...&j_{n-r} \end{array} \right).\hspace {1cm} (3)$$

Здесь $i_1\neq k_1,...,i_r\neq k_r$ и множество $\{k_1,k_2,...,k_r\}$ совпадает с $\mu (a)$. Мы видим, что $\mu (a^{-1})=\mu (a)$. Легко также проверяется включение $\mu (ab)\subseteq\mu (a)\cup\mu (b)$.

Определение. Подстановки a, b называются независимыми, если они не имеют общих действительно перемещаемых символов, т.е. если $\mu (a)\cap\mu (b)= \emptyset$.

Лемма. Пусть a,b -- независимые подстановки, тогда ab=ba и $\mu (ab)=\mu (a)\cup\mu (b)$. Если i -- символ из M, то i(ab)=i, когда $i\notin\mu (a)\cup\mu (b)$; i(ab)=ia, когда $i\in\mu (a)$; i(ab)=ib, когда $i\in \mu (b)$.

Доказательство. Разберем три имеющиеся возможности для данного символа i. 1) $i\notin\mu (a)\cup\mu (b)$. Тогда $ia=i,\ ib=i$, откуда $i(ab)=(ia)b=i,\ i(ba)=(ib)a=i$. 2) $i\in\mu (a)$. Тогда $j=ia\neq i$. Из представления (3) для подстановки a вытекает, что множества $\mu (a)a$ и $\mu (a)$ совпадают. Поэтому $j\in\mu (a)$. Так как $j\notin\mu (b)$, то jb=j, откуда $i(ab)=(ia)b=jb=j=ia,\ i(ba)=(ib)a=ia$. 3) $i\in \mu (b)$. Тогда $j=ib\in\mu (b)$, поэтому ja=j. Имеем $i(ab)=(ia)b=ib,\ i(ba)=(ib)a=ja=j=ib$. Из этих рассмотрений вытекает утверждение леммы.

Пусть a - неединичная подстановка из S_n и $i_1\in\mu (a)$. Тогда $i_2=i_1a\neq i_1$. Пусть $\{i_1,...,i_r\}$ - такое максимальное множество различных символов, что i₁a=i₂,...,i_r-1a=i_r. Ввиду условия максимальности $i_ra\in\{i_1,...,i_r\}$. Можно утверждать, что i_ra=i₁, так как символы i₂,...,i_r имеют своими прообразами символы i₁,...,i_r-1. Множество $\{i_1,...,i_r\}$ назовем нетривиальной орбитой подстановки a (тривиальная орбита состоит из неподвижного элемента). Отметим, что все элементы орбиты получаются из любого ее символа с помощью действий отображением a. Отсюда следует, что любые две орбиты подстановки a либо не пересекаются, либо совпадают, и что множество $\mu (a)$ разбивается в объединение непересекающихся нетривиальных орбит.

Определение. Подстановка $c\in S_n$ называется циклом, если она имеет точно одну нетривиальную орбиту. Другими словами, найдутся такие различные символы i₁,...,i_r, что i₁a=i₂,...,i_r-1a=i_r и $\mu (a)= \{i_1,...,i_r\}$. Число r называется длиной цикла c.

Данный цикл c принято для краткости изображать в виде одной строки

c=(i₁,...,i_r).

Эта запись означает, что каждый символ строки, за исключением последнего, при отображении c переходит в последующий символ, последний символ -- в первый, а остальные символы остаются неподвижными. Более естественно (но технически неудобно) было бы изображать цикл не в виде строки (i₁,...,i_r), а замкнуть эту строку в окружность (каждый символ отображается в следующий по часовой стрелке). Обратно, из окружности строка получается разрезанием окружности между некоторыми двумя символами. В частности, запись цикла в виде строки можно начинать с любого перемещаемого символа. Один и тот же цикл можно изобразить разными строками, например:

(1,2,3,4,5)=(2,3,4,5,1)=(3,4,5,1,2)=...

Теорема. Любая неединичная подстановка $a\in S_n$ однозначно с точностью до перестановки множителей разлагается в произведение независимых циклов.

Доказательство. Ранее мы отмечали, что множество $\mu (a)$ разбивается в объединение непересекающихся нетривиальных орбит. Пусть $\mu (a)= L_1\cup ...\cup L_p$ -- такое разбиение, где $L_1=\{i_1,...,i_r\} ,..., L_p=\{j_1,...,j_s\}$ и $i_1a=i_2,...,i_{r-1}a=i_r,\ i_ra=i_1,..., j_1a=j_2,...,j_{s-1}a=j_s,\ j_sa=j_1$. Рассмотрим циклы с₁=(i₁,...,i_r),..., с_p=(j₁,...,j_s). По построению эти циклы независимы. Покажем, что $a=c_1\cdots c_p$. Рассмотрим произвольный символ i из M. Если $i\notin\mu (a)$, то $i\notin L_1,..., i\notin L_p$. Тогда $ia=i,\ ic_1\cdots c_p=i$. Пусть $i\in\mu (a)$, например, $i\in L_q,\ 1\leq q\leq p$. По лемме $i(c_1\cdots c_p)=ic_q=ia$. Мы установили, что отображения a и $c_1\cdots c_p$ совпадают. Перестановочность элементов c₁,...,c_p следует из леммы. Докажем единственность разложения. Пусть подстановка a разложена некоторым другим способом в произведение независимых циклов: $a=d_1\cdots d_l$. Из леммы следует, что для каждого цикла $d_q\ (1\leq q\leq l)$ подстановка a действует на множестве $\mu (d_q)$ также, как и d_q. Поэтому $\mu (d_q)$ будет нетривиальной орбитой для a (все символы этого множества получаются из одного с помощью действия a) и $\mu (d_1)\cup ...\cup\mu (d_l)$ -- разбиение множества $\mu (a)$ на нетривиальные орбиты. Такого сорта разбиение однозначно. Поэтому p=l и, с точностью до переиндексации, $L_1=\mu (d_1),...,L_p=\mu (d_p)$. Так как на множестве L₁ действие циклов c₁ и d₁ равносильно действию a, то c₁=d₁. Аналогично c₂=d₂,...,c_p=d_p. Теорема доказана.

Упражнение. Произведение m подстановок, каждая из которых равна a, обозначим через a^m. Доказать, что a^m= e тогда и только тогда, когда число m делится на наименьшее общее кратное длин независимых циклов, на которые разлагается подстановка a.

11.5. Разложение на транспозиции. Четность

Транспозицией называется цикл длины 2, т.е. цикл вида (ij). Пусть c=(i₁,...,i_r) -- цикл длины r. Непосредственно проверяется, что цикл c разлагается в следующее произведение (r-1)-ой транспозиции:

$$c=(i_1i_2)(i_1i_3)\cdots (i_1i_r).$$

Рассмотрим произвольную неединичную подстановку a и разложим ее в произведение независимых циклов $a=c_1c_2\cdots c_s$ длин r₁,...,r_s. Далее, разлагая циклы c₁,...,c_s на транспозиции, мы получим разложение подстановки a в произведение транспозиций в количестве r₁-1+...+r_s-1 штук. Это число называется декрементом подстановки a, оно равно разности чисел r₁+...+r_s и s. Первое есть число действительно перемещаемых подстановкой a символов, а второе -- число независимых циклов, на которые разлагается подстановка. Ниоткуда не следует, что подстановка разлагается однозначно в произведение транспозиций. Более того, число множителей в различных таких разложениях может быть различным. Однако, имеет место следующий факт.

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

Доказательство. Нам потребуются следующие соотношения для транспозиций, которые проверяются непосредственно. 1) (ij)^-1=(ij)=(ji); 2) (ij)(kl)=(kl)(ij), если i,j,k,l -- различные символы; 3) (ij)(ik)=(ik)(kj), если i,j,k -- различные символы. Переходим к доказательству теоремы. Пусть подстановка a разлагается двумя способами в произведение транспозиций: $a=b_1\cdots b_r= c_1\cdots c_s$. Тогда получаем следующее разложение единичной подстановки $e=b_1\cdots b_r(c_1\cdots c_s)^{-1}= b_1\cdots b_rc_s\cdots c_1$ в произведение r+s транспозиций. Нужно доказать, что число r+s четное. Итак, достаточно установить, что в произвольном разложении единичной подстановки на транспозиции

$$e=t_1\cdots t_p\hspace{4cm} (4)$$

число p множителей четное. Доказательство проводим индукцией по p. Пусть $p>0,\ t_1=(i_1i_2)$. Так как i₁e=i₁, то разложение (4) имеет вид

$$e=(i_1i_2)\cdots (i_2i_3)\cdots (i_{r-1}i_r)\cdots (i_ri_1)\cdots ,$$

где i₁,...,i_r -- некоторые (не обязательно различные) символы из M. Соотношения 2) и 3) позволяют в произведении двух транспозиций переставлять правый множитель влево, при этом соседняя транспозиция может замениться на другую. При помощи таких перестановок мы, не меняя числа множителей, приходим к разложению

$$e=(i_1i_2)\cdots (i_2i_3)\cdots (i_{r-1}i_r)(i_ri_1)\cdots .$$

Так как (i_r-1i_r)(i_ri₁)=(i_ri₁)(i_r-1i₁), то получаем разложение

$$e=(i_1i_2)\cdots (i_2i_3)\cdots (i_{r-2}i_{r-1})\cdots (i_{r-1}i_1)\cdots$$

вида (5) с тем же числом множителей, но с меньшим набором выделенных транспозиций

(i₁i₂),...,(i_r-2i_r-1),(i_r-1i₁).

Продолжая этот процесс, получим разложение $e=(i_1i_2)(i_2i_1)\cdots$. Так как e=(i₁i₂)(i₂i₁), то число множителей можно сократить на 2. Путем таких сокращений получим либо тривиальное разложение с числом сомножителей, равным 0, либо разложение с одним множителем. Последнее невозможно, т.к. единичная подстановка не равна транспозиции. Из этого делаем вывод, что число p четное. Теорема доказана.

Доказанная теорема позволяет ввести следующее

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

Выше мы замечали, что всякая подстановка разлагается в произведение транспозиций, число которых равно декременту. Поэтому четность подстановки совпадает с четностью декремента. Введем функцию $\sigma (a)$ -- знак подстановки a. По определению полагаем $\sigma (a)=1$, если a - четная подстановка, и $\sigma (a)=-1$, если a -- нечетная подстановка. Эта функция удовлетворяет соотношению $\sigma (ab)= \sigma (a)\sigma (b)$.

Упражнение. Доказать, что число четных подстановок на множестве из n символов равняется n!/2.

11.6. Явная форма для определителя матрицы.

Полученные результаты о подстановках позволяют выписать явную формулу для определителя квадратной матрицы.

Теорема. Пусть $A=(a_{ij})\in M_n(k)$. Тогда

$$det A=\sum_{s\in S_n}\sigma (s) a_{1\ 1s}a_{2\ 2s}\cdots a_{n\ ns}.$$

Доказательство. Воспользуемся индукцией по n. При n=1 теорема очевидным образом верна. Пусть n>1. Разложим det A по последнему столбцу и воспользуемся индукцией для вычисления алгебраических дополнений:

$$detA=\sum_{i=1}^na_{in}A_{in}=$$

$$=\sum_{i=1}^n\sum_{s\in S_{n-1}} \sigma (s)a_{1\ 1s}\cdots a_{i-1\ (i-1)s}a_{in}a_{i+1\ is}\cdots a_{n\ (n-1)s}.$$

В этой двойной сумме n! слагаемых и каждое из них ровно один раз встречается (если не учитывать его знак) в доказываемой формуле. Поэтому достаточно сравнить знаки. Слагаемое

$$a_{1\ 1s}\cdots a_{i-1\ (i-1)s}a_{in}a_{i+1\ is}\cdots a_{n\ (n-1)s}$$

соответствует в доказываемой формуле подстановке

$$s_1=\left( \begin{array}{lllllll} 1&...&i-1&i&i+1&...&n\\ 1s&...&(i-1)s&n&is&...&(n-1)s \end{array} \right)=$$

$$=(i,i+1,...,n) \left( \begin{array}{llll} 1&...&n-1&n\\ 1s&...&(n-1)s&n \end{array} \right)$$

и $\sigma (s_1)=\sigma ((i,i+1,...,n))\cdot\sigma ( \left( \begin{array}{llll} ... ...igma ((i,i+1,...,n))\cdot\sigma (s)=(-1)^{n-i}\sigma (s)=(-1)^{n+1} \sigma (s)$ -- коэффициент при соответствующем слагаемом в каждой из рассматриваемых сумм. Теорема доказана.