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

Материал из Викиконспекты
Версия от 15:48, 6 января 2018; Denis (обсуждение | вклад) (Добавлено доказательство существования обратной перестановки для любой перестановки и указание на прувы свойств группы перестановок)
Перейти к: навигация, поиск

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

Определение:
Умножением (англ. multiplication) или композицией (англ. composition) перестановок,представленных в виде целочисленных функций [math] a_i [/math], где [math]i - [/math] позиция элемента, а [math] a_i [/math] — его номер, называется перестановка, получаемая по следующему правилу: [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] a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) [/math]

[math] b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) [/math]

[math] ab = {a_4, a_1, a_3, a_6, a_5, a_2} = {3, 2, 6, 4, 1, 5} [/math]

или

[math] ab = (1, 2, 5)(3, 6, 4)(1, 4, 6, 5) = (1, 3, 6, 5)(2)(4) = (1, 3, 6, 5) [/math]

Циклы подробно рассматриваются здесь: Действие перестановки на набор из элементов, представление в виде циклов

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

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


Утверждение:
Для каждой перестановки существует обратная ей.
[math]\triangleright[/math]
Пусть дана перестановка [math] a [/math], построим обратную ей перестановку [math] a^{-1}[/math]: если [math] a_x = y [/math], то [math] a^{-1}_y = x [/math]. Очевидно, что данная перестановка является обратной к [math] a [/math].
[math]\triangleleft[/math]


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


Утверждение:
Количество инволюционных перестановок длины [math]n\geqslant 2 [/math] может быть получено по формуле: [math] I(n) = I(n-1)+(n-1)\cdot I(n-2) [/math], где [math] I(0) = I(1) = 1. [/math]
[math]\triangleright[/math]
Очевидно, что [math] I(0) = I(1) = 1 [/math]. Предположим, что мы посчитали количество инволюций для всех длин [math] i \lt n [/math] перестановок, при [math] n \gt 1 [/math], тогда существует [math] I(n-1)[/math] инволюций, при [math]a_n = n [/math] (у которых последний элемент представляет собой цикл длины [math] 1 [/math]), а число инволюций длины [math] n [/math], содержащих в своём представлении в виде циклов цикл [math](j,n)[/math], где [math] 1\leqslant j\leqslant n-1 [/math], [math] (n-1)\cdot I(n-2)[/math] (так как при фиксированных [math] j [/math] и [math] n [/math] имеем [math] I(n-2) [/math] перестановок оставшихся элементов, которые не нарушают свойств инволюции). Таким образом, [math] I(n) = I(n-1)+(n-1)\cdot I(n-2). [/math]
[math]\triangleleft[/math]


Определение:
Перестановка, содержащая чётное количество инверсий, называется чётной (англ. even permutation), в противном случае [math] - [/math] нечётной (англ. odd permutation).


Определение:
Перестановка, меняющая местами только два элемента, называется транспозицией (англ. transposition).


Лемма:
Если в перестановке, длина которой больше [math]1[/math], поменять местами [math] 2 [/math] элемента, то её четность изменится.
Доказательство:
[math]\triangleright[/math]
Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами [math] a [/math] и [math] b [/math] находятся [math] d [/math] элементов, то есть перестановка имеет вид: [math] \ldots [/math] , [math] a, s_1, s_2, \ldots, s_d, b, \ldots [/math]. Сначала поменяем последовательно [math] a [/math] с числами [math] s_1, s_2, \ldots, s_d, b [/math], а затем число [math]b[/math] с рядом стоящими [math] s_d, s_d-1, \ldots, s_1 [/math]. В итоге мы выполним [math] 2\cdot d + 1 [/math] транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
[math]\triangleleft[/math]

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

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

fun reversePerm(p : int[], rep : int[])
   int n = p.size;
   for i = 0 to n
      for j = 0 to n
         if p[j] == i + 1
            rep[i] = j + 1;

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

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

Отсюда следует более эффективный алгоритм, где [math] visited[] [/math] - массив посещённых элементов: 

   fun reversePerm (visited : boolean[], p : int[], rep : int[])
      int n = p.size;
      for i = 0 to n
         if visited[i]
            continue;
         // инвертировать цикл, начинающийся в позиции [math] i [/math] 
         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;

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

Определение:
Группой (англ. group) называется множество [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] элементами с операцией умножения является группой (часто группу перестановок называют симметрической (англ. symmetric group), и обозначают [math] S_n [/math]).
[math]\triangleright[/math]
Свойства [math]1[/math] и [math]3[/math] (ассоциативность умножения и существование обратной перестановки для любой из перестановок) доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка ([math] \pi_i = i [/math]).
[math]\triangleleft[/math]

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

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

Группа чётных перестановок

Определение:
Группа чётных перестановок (англ. alternating group) [math] A_n [/math] является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.


Утверждение:
Количество чётных перестановок длины [math] n [/math] равно количеству нечётных и равно [math] \dfrac{n!}{2} [/math]
[math]\triangleright[/math]
Пусть число число чётных перестановок [math] - [/math] [math] a[/math], а нечётных [math] - [/math] [math] b [/math]. Сделаем транспозицию [math] (1, 2) [/math] для всех чётных перестановок. Получим [math] a [/math] нечётных различных перестановок, то есть [math] a\leqslant b [/math]. Проделаем то же самое с нечётными перестановками. Получим, что [math] b\leqslant a [/math], то есть [math] a = b [/math] и [math] a = \dfrac{n!}{2} [/math].
[math]\triangleleft[/math]

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

Определение:
Подстановкой (англ. substitution) называется всякое взаимно однозначное отображение [math] A [/math] множества первых [math]n[/math] натуральных чисел на себя.


Всякая подстановка [math]A[/math] может быть записана при помощи двух перестановок, подписанных одна под другой:

[math] A = \begin{pmatrix} q_1 & q_2 & \ldots & q_n \\ a_{k_1} & a_{k_2} & \ldots & a_{k_n} \end{pmatrix} [/math]

Где через [math] a_{k_i} [/math] обозначается то число, в которое при подстановке [math] A [/math] переходит число [math] q_i [/math].


Определение:
Группой подстановок (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве.


См. также

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

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