Четность перестановок и подстановок

Posted by admin on 23 Июль 2010 | Subscribe
in Лекции по алгебре
as , , , ,

Будем говорить, что числа i и j в перестановке (…,i,…,j,…) образуют инверсию, если число i расположено левее, чем j, но i>j (в противном случае будем говорить, что числа i и j расположены в правильном порядке). Ясно, что сумма числа всех инверсией и числа всех порядков в любой перестановке из n чисел 1,2,…,n равна C_n^2=\frac{n(n-1)}{2}.

Пример 5.4.1. Число инверсий в перестановке (1,2,…,n) равно нулю, в перестановке (n,n-1,…,2,1) равно \frac{n(n-1)}{2}.

Удобный алгоритм подсчета числа инверсий: считаем, сколько инверсий образует 1 (все числа, находящиеся левее), после чего вычеркиваем 1 и переходим к 2 и т. д.

Теорема 5.4.2. Транспозиция в перестановке меняет четность числа инверсий.

Доказательство. Рассмотрим транспозицию элементов i и j:

(...,i,...,j,...)\mapsto (...,j,...,i,...).

Сначала рассмотрим случай «соседей»:

(...,i,j,...)\mapsto (...,j,i,...).

Так как при перестановке чисел i и j их отношение с числами, расположенными левее (как и правее) не изменяется, то число инверсий изменяется на единицу (т. е. \pm 1), следовательно, четность числа инверсий изменяется.

Если же между числами i и j находится k элементов, то последовательно переставляя i с правыми соседними элементами k раз, потом с j, затем переставляяk раз элемент j с левыми соседними элементами, мы, проведя k+1+k=2k+1 транспозиций соседних элементов, осуществим транспозицию чисел i и j. Таким образом, четность изменилась.

Следствие 5.4.3. Число четных перестановок при n \geq 2 равно числу нечетных перестановок и равно \frac{n!}{2}.

Доказательство. Расположив все n! перестановок, начиная, например, с (1,2,…,n), в список, в котором каждая следующая перестановка получается из предыдущей одной транспозицией, мы видим, что четные перестановки чередуются с нечетными, поэтому число четных перестановок равно числу нечетных и равно \smash[b]{\frac{n!}{2}}.

Четность подстановки

\begin{pmatrix} i_1 & ... & i_n\\ j_1 & ... & j_n \end{pmatrix}

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

Предложение 5.4.4. Четность подстановки \sigma\in S_n не зависит от ее записи.

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

\sigma= \begin{pmatrix} i_1 & ... & i_n\\ \sigma(i_1) & ... & \sigma(i_n) \end{pmatrix} = \begin{pmatrix} i'_1 & ... & i'_n\\ \sigma(i'_1) & ... & \sigma(i'_n) \end{pmatrix}\text{ -}

две записи подстановки \sigma\in S_n, то, переходя конечным числом транспозиций от перестановки (i_1,…,i_n) к перестановке (i’1,…,i’n), переставляя при этом соответствующие «столбики»

\begin{pmatrix} i\\ \sigma(i) \end{pmatrix},

приходим от нижней строчки (\sigma(i_1),...,\sigma(i_n)) к строчке (\sigma(i'_1),...,\sigma(i'_n)). Перестановка двух «столбиков» является транспозицией в верхней и в нижней строчках, следовательно, меняется четность в верхней и в нижней строчках, в итоге четность суммы числа транспозиций в верхней и в нижней строчке при перестановке двух «столбиков» не изменится.

Замечание 5.4.5. Подстановка, обратная к четной подстановке, четная. Действительно, если

\sigma = \begin{pmatrix} i_1 & i_2 & ... & i_n\\ j_1 & j_2 & ... & j_n \end{pmatrix}

четная, то

\sigma^{-1} = \begin{pmatrix} j_1 & ... & j_n\\ i_1 & ... & i_n \end{pmatrix}

четная.

Четность произведения подстановок

Возможность использовать произвольную запись подстановки удобна для рассмотрения произведения:

\begin{pmatrix} i_1 & ... & i_n\\ j_1 & ... & j_n \end{pmatrix} \begin{pmatrix} 1 & 2 & ... & n\\ i_1 & i_2 & ... & i_n \end{pmatrix} = \begin{pmatrix} 1 & 2 & ... & n\\ j_1 & j_2 & ... & j_n \end{pmatrix},

откуда следует

Лемма 5.5.1 (о четности произведения).

\begin{array}[b]{|c|c|c|} \sigma & \tau & \sigma\tau\\ \hline \textup{ч} & \textup{ч} & \textup{ч}\\ \hline \textup{н} & \textup{ч} & \textup{н}\\ \hline \textup{ч} & \textup{н} & \textup{н}\\ \hline \textup{н} & \textup{н} & \textup{ч}\\ \end{array}\;.

Рассмотрим отображение

\begin{align*} & \varepsilon\colon \mS_n \to \{1,-1\},\\ & \varepsilon(\sigma) = \begin{cases} 1, & \text{если $\sigma$"--- чётная подстановка},\\ -1, & \text{если $\sigma$"--- нечётная подстановка}. \end{cases} \end{align*}

Замечание 5.5.2. Напомним, что {1,-1} — коммутативная группа относительно операции произведения. Действительно, произведение является операцией на {1,-1}; эта операция ассоциативна и коммутативна; 1 — нейтральный элемент; (1)-1=1, (-1)-1=-1.

Следствие 5.5.3. Если \sigma,\tau\in S_n, то:

\varepsilon(\sigma\tau)=\varepsilon(\sigma)\varepsilon(\tau)

(т. е. \sigma: S_n\to \{1,-1\} — гомоморфизм групп);

\varepsilon(\sigma)=\varepsilon(\sigma^{-1}).

Следствие 5.5.4. Если \sigma=\tau_1...\tau_k — разложение подстановки \sigma\in S_n в произведение транспозиций \tau_1,...,\tau_k, то \varepsilon(\sigma)=(-1)^k.

Доказательство. Отметим только, что если \tau=(i\quad j) — транспозиция, то \varepsilon((i\quad j))=-1.

Упражнение 5.5.5. \varepsilon((i_1\quad...\quad i_r))=(-1)^{r-1} для цикла (i_1… i_r) длины r, r \geq 2.

Теорема 5.5.6. Четные подстановки An являются группой (подгруппой в группе подстановок Sn) |A_n|=\frac{n!}{2} при n \geq 2.

Доказательство. Так как произведение \sigma\tau четных подстановок \sigma,\tau\in A_n является четной подстановкой, то имеем операцию произведения на множестве An, которая ассоциативна. Тождественная подстановка четная и является нейтральным элементом в An. Если \sigma\in A_n, то мы уже отметили, что \sigma^{-1}\in A_n.

Задача 5.5.7.Найти разбиение в классы сопряженных элементов групп A4, A5.

Задача 5.5.8. Группа An, n \geq 3, порождается тройными циклами (любой элемент группы An является произведением тройных циклов и обратных к ним; обратный элемент к тройному циклу сам является тройным циклом).

Указание Четная подстановка может быть представлена в виде произведения четного числа транспозиций, при различных i,j, k (i k)(i j)=(i j k), при различных i, j, k, l (i j)(k l)=(j k l)(i l j).