Умножение перестановок, обратная перестановка, группа перестановок — различия между версиями
(→Группа перестановок) |
(→Пример) |
||
Строка 26: | Строка 26: | ||
==Пример== | ==Пример== | ||
− | <tex> \varphi(1)=\begin{ | + | <tex> \varphi(1)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 1 \end{pmatrix} </tex> |
− | <tex> \varphi(2)=\begin{ | + | <tex> \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} </tex> |
<tex> (\varphi(1) \circ \varphi(2))_i=</tex> | <tex> (\varphi(1) \circ \varphi(2))_i=</tex> | ||
− | <tex> \begin{ | + | <tex> \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{pmatrix} \circ</tex> |
− | <tex> \begin{ | + | <tex> \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} = |
− | \begin{ | + | \begin{pmatrix} 4 & 1 & 3 & 6 & 5 & 2 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix} \circ |
− | \begin{ | + | \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} =</tex> |
− | <tex>\begin{ | + | <tex>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}</tex> |
=Обратная перестановка= | =Обратная перестановка= |
Версия 03:14, 19 декабря 2011
Содержание
Умножение перестановок
Определение: |
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу: |
Утверждение: |
Умножение перестановок ассоциативно:
|
Доказывается простым раскрытием скобок. |
Пример
Обратная перестановка
Определение: |
Обратной перестановкой | к перестановке называется такая перестановка, что:
Определение: |
Перестановка, равная своей обратной, называется инволюцией: |
Получение обратной перестановки
Пусть в массиве 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; } } }
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
Группа перестановок
Определение: |
Группой называется множество
| с заданной на нём бинарной операцией , удовлетворяющей следующим свойствам:
Утверждение: |
Множество перестановок с элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают ). |
Свойства 1 и 3 доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка ( | ).
Мощность множества симметрических групп:
Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
Источники и литература
- инволюция (Wikipedia, the free encyclopedia)
- Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161