Группа перестановок

Определение:

Группой называется непустое множество $G$ с определенной на нем бинарной операцией $\diamond$, которая не выводит из множества $G$ и удовлетворяет трем аксиомам:

$1^a$ ассоциативность: для любых $a,b,c\in G$ верно, что $(a\diamond b)\diamond c = a\diamond (b\diamond c)$.

$2^a$ наличие нейтрального элемента: существует такой элемент $e\in G$, что для любого $a\in G$ справедливо $a\diamond e = e\diamond a = a$.

$3^a$ наличие обратного элемента: для любого элемента $a\in G$ найдется такой элемент $a^{-1}\in G$, что $a^{-1}\diamond a = a\diamond a^{-1} = e$.

Произведение перестановок ассоциативно: $((\pi_3 \circ \pi_2) \circ \pi_1) (i) = (\pi_3 \circ \pi_2) (\pi_1 (i)) = \pi_3 (\pi_2 (\pi_1 (i))) = = \pi_3 ((\pi_2 \circ \pi_1) (i)) = (\pi_3 \circ (\pi_2 \circ \pi_1))(i)$

Нейтральным элементом для множества $\sigma_n$ будет служить тождественная перестановка $e = \left(\begin{array}{cccc} 1 & 2 & ... & n \\ 1 & 2 & ... & n \end{array}\right)$. Легко заметить, что для любой перестановки $\pi\in\sigma_n$ верно $\pi\circ e = e\circ \pi = \pi$.

Для любой перестановки $\pi\in\sigma_n$, как для любой биективной функции, существует обратная функция $\pi^{-1}$: $\pi^{-1}\circ\pi = \pi \circ \pi^{-1} = e$.

Для любых $i\in\{1,...,n\}$ $\pi(i)=j\Rightarrow \pi^{-1}(j) = i$. Функция $\pi^{-1}$, обратная для биективной функции $\pi$, также будет биективной функцией: $\pi^{-1} : \{1,...,n\}\rightarrow \{1,...,n\}.$ То есть, $\pi^{-1}\in\sigma_n$.

Замечание

Заметим, что обратная перестановка $\pi^{-1}$ для данной перестановки $\pi$ единственна.

Действительно, если бы существовала еще одна такая перестановка [math]\displaystyle{ \pi' }[/math], что [math]\displaystyle{ \pi\circ\pi' = e }[/math], то [math]\displaystyle{ \pi' = e\circ \pi' = \pi^{-1}\circ\pi\circ\pi' = \pi^{-1}\circ e = \pi^{-1} }[/math]; если перестановка [math]\displaystyle{ \pi' ' }[/math] такова, что [math]\displaystyle{ \pi' '\circ\pi = e }[/math], то

[math]\displaystyle{ \pi^{-1} = e\circ \pi^{-1} = \pi' '\circ\pi\circ\pi^{-1} = \pi' '\circ e = \pi' ' }[/math].

Таким образом, мы доказали, что множество перестановок $\sigma_n$ с операцией произведения перестановок образуют группу. Эту группу называют группой перестановок или симметрической группой.

Замечание

Произведение перестановок в общем случае не коммутативно.

Пусть [math]\displaystyle{ \pi_1 = \left(\begin{array}{ccc} 1 & 2 & 3\\ 2 & 1 & 3\end{array}\right),\qquad \pi_2 = \left(\begin{array}{ccc} 1 & 2 & 3\\ 3 & 1 & 2\end{array}\right). }[/math]

Тогда

[math]\displaystyle{ \pi_2\circ\pi_1 = \left(\begin{array}{ccc} 1 & 2 & 3\\ 1 & 3 & 2\end{array}\right) \neq \left(\begin{array}{ccc} 1 & 2 & 3\\ 3 & 2 & 1\end{array}\right) = \pi_1\circ\pi_2. }[/math]

Рис. 1. Для [math]\displaystyle{ \pi_1=(2,1,3) }[/math] и [math]\displaystyle{ \pi_2=(3,1,2) }[/math] получаем [math]\displaystyle{ \pi_2\circ\pi_1=(1,3,2) }[/math], а [math]\displaystyle{ \pi_1\circ\pi_2=(3,2,1) }[/math]. Результаты различны, поэтому группа перестановок некоммутативна.

Конспект: Дискретная математика