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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Определение:
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу: [math] (ab)_i = a_{b_i} [/math]


Утверждение:
Умножение перестановок ассоциативно: [math] (a(bc))_i = ((ab)c)_i [/math]
[math]\triangleright[/math]

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

  1. [math] (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} [/math]
  2. [math] ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} [/math]
[math]\triangleleft[/math]

Пример

[math] \varphi(1)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{pmatrix} [/math]

[math] \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} [/math]

[math] (\varphi(1)\varphi(2))_i=[/math] [math] \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{pmatrix}[/math] [math] \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} =[/math] [math]\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}[/math]

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

Определение:
Обратной перестановкой [math] a^{-1} [/math] к перестановке [math] a [/math] называется такая перестановка, что: [math] (a^{-1}a)_i = (aa^{-1})_i = i [/math]


Определение:
Перестановка, равная своей обратной, называется инволюцией: [math] a_i = a^{-1}_i \Rightarrow (aa ^{-1})_i = (aa)_i = a_{a_i} = i [/math]


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

Пусть в массиве 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;
           }
       }
}

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

[math] a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) [/math]

Отсюда следует более эффективный алгоритм (приведена 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;
       }      
   }

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

Определение:
Группой называется множество [math] M [/math] с заданной на нём бинарной операцией [math] \circ: МM\times M \longrightarrow M[/math], удовлетворяющей следующим свойствам:
  1. [math] (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) [/math] — ассоциативность соответствующей бинарной операции.
  2. Существование нейтрального элемента [math] e [/math] относительно операции [math] \circ [/math], такого, что для любого [math] g \in M: g \circ e = e \circ g = g [/math]
  3. Для любого [math] g \in M [/math]существует [math] g^{-1} \in M[/math] называемый обратным элементом, такой, что [math]: g \circ g^{-1} = g^{-1} \circ g = e [/math]


Утверждение:
Множество перестановок с [math] n [/math] элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают [math] S_n [/math]).
[math]\triangleright[/math]
Свойства 1 и 3 доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка ([math] \pi_i = i [/math]).
[math]\triangleleft[/math]

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

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

Источники и литература

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Умножение_перестановок,_обратная_перестановка,_группа_перестановок&oldid=33675»