alexlyk314 20 сен 2023 в 16:08

Знак перестановки: транспозиции vs инверсии

Средний

4 мин

7.8K

В этой статье мы обсудим с разных сторон такое важное понятие, как знак перестановки. Перестановки играют важную роль в разных разделах математики, прежде всего в алгебре и комбинаторике. Знак (чётность) перестановки — это её важнейшая характеристика. На ней, в частности, основана теория определителей.

Перестановкой конечного множества называется любое его биективное (т. е. взаимно однозначное) соответствие на себя. Перестановку часто записывают в виде таблицы: в верхней строке — аргументы, в нижней — значения функции. Например,

$\sigma =\begin{pmatrix} \square & \Diamond & \bigstar &\triangle & \bigcirc \\ \triangle & \bigcirc &\square &\bigstar & \Diamond \end{pmatrix} \;\;\;\;\;\;\; (1)$

— перестановка на множестве $\left\{\square, \Diamond, \bigstar, \triangle, \bigcirc\right\}$ , при которой $\sigma(\square)=\triangle$ , $\sigma(\Diamond)=\bigcirc$
и т. д. Как правило, природа переставляемых элементов не важна, и их считают числами $1,\ldots,n$ . Перестановок элементов всего $n\cdot (n-1)\cdot \ldots\cdot 1=n!$ .

Перестановки можно перемножать в смысле композиции (как обычные функции), справа налево, при этом снова получается перестановка. Все перестановки на элементах образуют группу . Она называется симметрической группой. Кто знает, почему, пишите в комментариях. И заодно про знакопеременную группу . Автор знает :)

Действие перестановки $\sigma\in S_n$ можно наглядно изобразить: отметим вершины $1,\ldots,n$ и нарисуем стрелку от к , если $\sigma(i)=j$ (в случае $i=\sigma(i)$ рисуем петлю). Получим ориентированный граф, в котором из каждой вершины выходит одно ребро и в каждую вершину входит одно ребро. Этот граф распадается на циклы. Тем самым, перестановка $\sigma$ представляется в виде произведения независимых циклов. Неподвижные элементы считаются циклами длины 1 и в записи обычно опускаются. Пример:

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 9 & 8 & 6 & 1 & 4 & 7 & 5 & 2 \end{pmatrix}= (1385)(29)(46) \;\;\;\;\;\;\; (2)$

Все перестановки делятся на чётные и нечётные. По какому принципу? Есть несколько подходов.

Подход через инверсии. Инверсия в перестановке $\sigma$ — это число таких пар $\{i, j\}$ , что , но $\sigma(i)>\sigma(j)$ . Чётность перестановки $\sigma$ — это чётность числа всех её инверсий. Например, для перестановки

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 1 & 3 & 2 \end{pmatrix} \;\;\;\;\;\;\; (3)$

все инверсии суть: $\{1,4\}$ , $\{1,5\}$ , $\{2,3\}$ , $\{2,4\}$ , $\{2,5\}$ , $\{3,4\}$ , $\{3,5\}$ . Всего 7 штук, поэтому перестановка (3) нечётная.

Но как с помощью данного определения найти чётность перестановки (1)? Минус этого подхода в том, что в определении перестановки вовсе не предполагается какой-то порядок на множестве, а понятие инверсии основано на порядке.

Отметим, что если фигурки в (1) занумеровать так, как они идут в первой строке, то (1) превратится в (3). Но, что если фигурки занумеровать как-то по другому? Число инверсий может измениться, хотя можно доказать, что их чётность не изменится. Знатоки, конечно, сразу объяснят, почему: при другой нумерации получится сопряжённая перестановка.

Знак перестановки $\sigma$ — это число , если перестановка чётная, и число , если она нечётная; обозначения: $\operatorname{sgn} \sigma=(-1)^\sigma$ . Вот главное свойство знака:

$\operatorname{sgn} (\sigma\tau)=(\operatorname{sgn} \sigma)(\operatorname{sgn} \tau) \;\;\;\;\;\;\; (4)$

При подходе через инверсии оно не очевидно; доказательство требует некоторой возни.

Наконец отметим, что подсчёт инверсий требует время : их наибольшее число равно

$C_n^2=\dfrac{n(n-1)}{2}$

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

$\begin{pmatrix} 1 & 2 & \ldots & n-1 & n \\ n & n-1 & \ldots & 2 & 1 \end{pmatrix}. \;\;\;\;\;\;\; (5)$

В то же время любой программист скажет, что определить чётность перестановки легко за линейное время .

Всех этих недостатков лишён подход через транспозиции. Транспозицией называется цикл длины 2 — своего рода простейшая перестановка.

Теорема-определение. Любую перестановку можно представить в виде произведения транспозиций. Чётность их числа в любом представлении одинакова и называется чётностью перестановки.

$\lhd$ Всякую перестановку можно представить в виде произведения независимых циклов, а каждый цикл — в виде произведения транспозиций, например, так:

$(i_1i_2\ldots i_k)=\underbrace{(i_1i_2)(i_2i_3)\ldots(i_{k-1}i_k)}_{k-1 \text{ транспозиций}}. \;\;\;\;\;\;\; (6)$

Почему никакую перестановку нельзя одновременно представить в виде произведения чётного и нечётного числа транспозиций? Потому что при умножении перестановки на транспозицию число независимых циклов в её разложении (включая циклы длины 1) меняется на 1. Действительно, если в разложении перестановки $\sigma$ элементы и были в одном цикле, то в перестановке $\sigma(ij)$ этот цикл распадётся на два:

$(ik_1\ldots k_sjl_1\ldots l_t)(ij)=(il_1\ldots l_t)(jk_1\ldots k_s). \;\;\;\;\;\;\; (7)$

(что верно и при ). А если и были в разных циклах, то эти циклы сольются в один, о чём свидетельствует то же равенство (7), только его надо справа умножить на . $\rhd$
Есть и другое красивое доказательство, использующее многочлен

$\prod_{1\leq i<j\leq n} (x_i-x_j).$

Надо показать, что он меняет знак при любой транспозиции переменных. Порядок на элементах (переменных) здесь вводится только в доказательстве. (Знатоки, конечно, узнали определитель Вандермонда, но помнят, что обычно определители строятся через перестановки, а не наоборот. Впрочем, можно извратиться...)

Пример. Перестановка (5) есть произведение транспозиций: $(1\;n)(2\;n-1)(3\;n-2)\ldots$

Согласно (6) чётность цикла противоположна его длине. Кстати, цикл длины нельзя представить в виде произведения транспозиций. Попробуйте это доказать, модифицировав приведённое выше доказательство. Более общо, перестановку из , которая раскладывается в произведение независимых циклов, можно представить в виде произведения транспозиций и никак не меньше. Это число называется декрементом перестановки. Его преимущество над числом в том, что декремент не зависит от приписывания неподвижных элементов. Так, декремент транспозиции равен 1 при любом .

Итак, вот преимущества подхода через транспозиции.

$\bullet$ Грамотное определение, не зависящее от порядка. Например,

$\begin{pmatrix} \square & \Diamond & \bigstar &\triangle & \bigcirc \\ \triangle & \bigcirc &\square &\bigstar & \Diamond\end{pmatrix}=\left(\square\; \triangle \; \bigstar \right)\left( \Diamond\;\bigcirc\right)=\left(\square\; \triangle \right) \left(\triangle \; \bigstar \right)\left(\Diamond\; \bigcirc\right)$

— нечётная перестановка.

$\bullet$ Разложение в произведение транспозиций (равно как и разложение на независимые циклы) требует линейное время .

$\bullet$ Основное свойство знака (4) очевидно!

P.S. По-видимому, понятие чётности перестановки возникло при решении известной игры "Пятнашки" (почему нельзя переставить 14 и 15 по правилам).

P.P.S. Не говорите "подстановки". Это явно не подходящий в данном контексте термин применяется только в некоторой русскоязычной литературе, причём, в основном, учебной. В англоязычной литературе — только permutations и никаких substitutions. Подстановка (substitution) — это $f(x)|_{x=5}\;=f(5)$ .

Автор: Андрей Канунников, к. ф.-м. н., мехмат МГУ, преподаватель ШАД Хелпер

Теги:

Хабы:

Математика

Знак перестановки: транспозиции vs инверсии

Публикации

Истории

Ближайшие события