Подстановки

проверено

Подстановка

Определение 1. Произвольное взаимно однозначное отображение множества первых $n$ натуральных чисел называется подстановкой1) $n$-го порядка.

Замечание 1. Часто подстановки называют перестановками.

Обычно подстановку $\pi$ изображают следующим образом: $\begin{pmatrix}1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}$, что задает образы всех элементов: $\pi(1)=i_1$, $\pi(2)=i_2$ и так далее. Также используют запись $\begin{pmatrix}i_1 & i_2 & \ldots & i_n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}$.

Пример 1. Подстановку $\begin{pmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{pmatrix}$ можно записать также в виде $\begin{pmatrix}2 &1 & 3\\ 2 & 3 & 1\end{pmatrix}$, так как в обоих случаях мы имеем отображение $1\mapsto 3$, $2\mapsto 2$, $3\mapsto 1$.

Определение 2. Элемент $k\in\{1,\ldots,n\}$ подстановки $\pi$ называется действительно перемещаемым, если $k\neq\pi(k)$.

Пример 2. В подстановке $\begin{pmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{pmatrix}$ два действительно перемещаемых символа: 1 и 3.

Операция умножения на подстановках определяется как композиция отображений, причем знак композиции $\circ$ обычно опускают

$\begin{pmatrix}i_1 & i_2 & \ldots & i_n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}\begin{pmatrix}1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}=\begin{pmatrix}i_1 & i_2 & \ldots & i_n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}\circ\begin{pmatrix}1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}=\begin{pmatrix}1 & 2 & \ldots & n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}$.

Транспозиции и циклы

Определение 3. Циклической подстановкой2), или циклом3) называется такая подстановка $\pi\in S_n$, что при повторении ее достаточное число раз всякий из действительно перемещаемых ею символов может быть переведен в любой другой из этих символов. Для обозначения цикла используют запись $(i\quad\pi(i)\quad\ldots\quad\pi^{t-1}(i))$, где $t$ — число действительно перемещаемых символов подстановки, которое называется длиной цикла4).

Пример 3. В подстановке

$\pi=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 3 & 2 & 6 & 5 & 1 & 4 & 7 & 8\end{pmatrix}$

действительно перемещаемыми символами являются 1, 3, 4, 5, 6. Выберем любой из них, например, 3. $\pi(3)=6,\,\pi(6)=4,\,\pi(4)=5$, $\pi(5)=1,\,\pi(1)=3$. Поэтому цикл можно записать как $(3\quad 6\quad 4\quad 5\quad 1)$.

Определение 4. Циклы называются независимыми5), если они не имеют общих действительно перемещаемых символов.

Предложение 1. Любая подстановка $\pi\neq e$ из $S_n$ может быть разлжена в произведение попарно независимых циклов. Такое представление определено однозначно с точностью до порядка перемножения циклов.

Пример 4. $\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 3 & 5 & 1 & 2 & 4\end{pmatrix}=(1\quad 3)(2\quad 5\quad 4)$ — разложение подстановки в произведение попарно независимых циклов.

Определение 5. Цикл длины 2 называется транспозицией6).

Предложение 2. Каждая подстановка может быть представлена в виде произведения транспозиций.

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

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

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

$(i\quad\pi(i)\quad\ldots\quad\pi^{t-1}(i))=(i\quad\pi^{t-1}(i))(i\quad\pi^{t-2}(i))\ldots(i\quad\pi^{2}(i))(i\quad\pi(i))$.

Так как любая подстановка представляется в виде произведения циклов, то достаточно записать каждый цикл в виде произведения транспозиций.

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

Пример 5. Подстановка $\begin{pmatrix}1 & 2 & 3 & 4\\ 2 & 3 & 1 & 4\end{pmatrix}$ может быть разложена в произведение транспозиций $(1\quad 3)(1\quad 2)$ или $(1\quad 3)(2\quad 4)(1\quad 2)(1\quad 4)$.

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

Определение 6. Пусть $\pi=\tau_1\ldots\tau_k$ — разложение подстановки $\pi$ в произведение транспозиций. Тогда число $\varepsilon(\pi)=(-1)^k$ называется знаком7)(четностью) подстановки $\pi$. Подстановка называется четной8), если $\varepsilon(\pi)=1$ и нечетной9) в противном случае.

Предложение 3. Четность подстановки не зависит от способа разложения подстановки в произведение транспозиций.

Предложение 4. Для двух подстановок $\pi_1$ и $\pi_2$ четность их произведения равна произведению четностей:

$\varepsilon(\pi_1\pi_2)=\varepsilon(\pi_1)\varepsilon(\pi_2)$.

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

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

Пусть $\pi_1=\tau_1\ldots\tau_k$, $\pi_2=\tau_{k+1}\ldots\tau_{k+l}$, значит, $\varepsilon(\pi_1)=(-1)^k$ и $\varepsilon(\pi_2)=(-1)^l$. Тогда $\pi_1\pi_2=\tau_1\ldots\tau_k\tau_{k+1}\ldots\tau_{k+l}$ — разложение подстановки в произведение транспозиций. Поэтому

$\varepsilon(\pi_1\pi_2)=(-1)^{k+l}=(-1)^k(-1)^l=\varepsilon(\pi_1)\varepsilon(\pi_2)$.

Предложение 5. Пусть $\pi$ — цикл длины $l$. Тогда его четность равна $\varepsilon_{\pi}=(-1)^{l-1}$.

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

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

Утверждение следует из того, что цикл длины $l$ представим в виде произведения $l-1$-й транспозиции

$(i\quad\pi(i)\quad\ldots\quad\pi^{l-1}(i))=(i\quad\pi^{l-1}(i))(i\quad\pi^{l-2}(i))\ldots(i\quad\pi^{2}(i))(i\quad\pi(i))$.

Определение 7. Пусть $\pi=\pi_1\pi_2\ldots\pi_k$ — разложение подстановки в произведение независимых циклов длин $l_1,l_2,\ldots,l_k$. Число $d_{\pi}=l_1+\ldots+l_k-k$ называется декрементом10) подстановки $\pi$.

Предложение 6. Пусть $\pi=\pi_1\pi_2\ldots\pi_k$ — разложение подстановки в произведение независимых циклов длин $l_1,l_2,\ldots,l_k$. Тогда четность подстановки $\pi$ вычисляется по формуле

$\varepsilon_{\pi}=(-1)^{d_{\pi}}$.

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

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

По предложению 5 $\varepsilon(\pi_i)=(-1)^{l_i-1}$ для $1\leqslant i\leqslant k$. По предложению 4

$\varepsilon(\pi)=\varepsilon(\pi_1)\ldots\varepsilon(\pi_k)=(-1)^{l_1-1}\ldots(-1)^{l_k-1}=(-1)^{l_1+\ldots l_k-k}=(-1)^{d_{\pi}}$.

Пример 6. Любая транспозиция — это нечетная подстановка. Подстановка из примера 4 нечетная, так как декремент $(2-1)+(3-1)$ — нечетное число.

Пример 7. Любая подстановка, в разложении которой на независимые циклы все циклы имеют нечетные длины $l_1,l_2,\ldots,l_k$, четна, так как ее декремент — это сумма $k$ четных чисел $(l_1-1)+(l_2-1)+\ldots+(l_k-1)$.

См. также

Литература

1)
permutation
2)
cyclic permutation
3)
cycle
4)
cycle length
5)
independent
6)
transposition
7)
signature
8)
even
9)
odd
10)
decrement
glossary/group/permutation.txt · Последние изменения: 15.02.2014 12:06:09 — Ладилова Анна
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0