Умножение перестановок, обратная перестановка, группа перестановок

2015-01-04T17:28:20Z

46.20.65.123: /* Пример */

==Умножение перестановок==

{{Определение
|definition=
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

Доказывается простым раскрытием скобок.

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> \varphi(1)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{pmatrix} = (1,2,5)(3,6,4) </tex>

<tex> \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} = (1,4,6,2)(3)(5)</tex>

<tex> (\varphi(1)\varphi(2))_i=</tex>
<tex> \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{pmatrix}</tex>
<tex> \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} =
\begin{pmatrix} 4 & 1 & 3 & 6 & 5 & 2 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} =</tex>
<tex>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}</tex>

или

<tex> (\varphi(1)\varphi(2))_i= (1,2,5)(3,6,4)(1,4,6,2) =(1,3,6,5)(2)(4) = (1,3,6,5) </tex>

==Обратная перестановка==

{{Определение
|definition=

Обратной перестановкой <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|definition=
Перестановка, равная своей обратной, называется инволюцией:

<tex> a_i = a^{-1}_i \Rightarrow (aa ^{-1})_i = (aa)_i = a_{a_i} = i </tex>

}}

===Получение обратной перестановки===

Пусть в массиве p[i] содержится перестановка, тогда в массиве op[i], после выполнения алгоритма, будет содержаться обратная перестановка.

for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
if(p[j] == i + 1)
{
op[i] = j + 1;
}
}
}

При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм (приведена in-place версия):

boolean[] visited = new boolean[n];
for (int i = 0; i < n; ++i)
{
if (visited[i]) continue;
// Reverse the cycle starting at i
int last = i;
int j = p[i];
while (true)
{
int next = p[j];
p[j] = last;
visited[j] = true;
if (j == i) break;
last = j;
j = next;
}
}

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

{{Определение
|definition=
Группой называется множество <tex> M </tex> с заданной на нём бинарной операцией <tex> \circ: МM\times M \longrightarrow M</tex>, удовлетворяющей следующим свойствам:

# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> — ассоциативность соответствующей бинарной операции.
# Существование нейтрального элемента <tex> e </tex> относительно операции <tex> \circ </tex>, такого, что для любого <tex> g \in M: g \circ e = e \circ g = g </tex>
# Для любого <tex> g \in M </tex>существует <tex> g^{-1} \in M</tex> называемый обратным элементом, такой, что <tex>: g \circ g^{-1} = g^{-1} \circ g = e </tex>

}}

{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>).
|proof=
Свойства 1 и 3 доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>).
}}

Мощность симметрической группы: <tex>\left\vert S_n \right\vert = n!</tex>

[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.

==Источники и литература==
* [http://ru.wikipedia.org/wiki/%D0%98%D0%BD%D0%B2%D0%BE%D0%BB%D1%8E%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) инволюция (Wikipedia, the free encyclopedia)]
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Викиконспекты - Вклад участника [ru]

Умножение перестановок, обратная перестановка, группа перестановок