Умножение перестановок, обратная перестановка, группа перестановок — различия между версиями
(→Группа перестановок) |
(→Умножение перестановок) |
||
Строка 5: | Строка 5: | ||
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу: | Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу: | ||
− | <tex> ( | + | <tex> (ab)_i = a_{b_i} </tex> |
}} | }} | ||
Строка 13: | Строка 13: | ||
Умножение перестановок ассоциативно: | Умножение перестановок ассоциативно: | ||
− | <tex> (a | + | <tex> (a(bc))_i = ((ab)c)_i </tex> |
|proof= | |proof= | ||
Строка 19: | Строка 19: | ||
Доказывается простым раскрытием скобок. | Доказывается простым раскрытием скобок. | ||
− | # <tex> (a | + | # <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex> |
− | # <tex> (( | + | # <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex> |
}} | }} | ||
Строка 30: | Строка 30: | ||
<tex> \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} </tex> | <tex> \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} </tex> | ||
− | <tex> (\varphi(1) | + | <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> \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} = | <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} 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> |
− | \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>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}</tex> | ||
Версия 06:59, 9 января 2012
Содержание
Умножение перестановок
Определение: |
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу: |
Утверждение: |
Умножение перестановок ассоциативно:
|
Доказывается простым раскрытием скобок. |
Пример
Обратная перестановка
Определение: |
Обратной перестановкой | к перестановке называется такая перестановка, что:
Определение: |
Перестановка, равная своей обратной, называется инволюцией: |
Получение обратной перестановки
Пусть в массиве 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