Как найти произведение перестановок
Перестановка порядка n это биективное отображение конечного множества из n элементов в себя.
Также можно для удобства переставлять столбцы местами:
Для наглядности, ту же перестановку можно изобразить картинкой вида
Пример вычисления произведения перестановок: если
При помощи обычного определения удобно вычислять произведение так: в перестановке σ переставляем столбцы так, что первая строчка в σ совпадает с последней строчкой в τ . Тогда произведением будет перестановка, у которой первая строчка — стандартная, а вторая строчка — это вторая строчка из σ.
Пример 2. Найти произведение перестановок можно и так
Первая перестановка переводит один в два, а вторая два в семь, значит произведение переводит один в семь и т.д.
Перестановки удобно перемножать и в том случае, когда они представлены в виде произведения непересекающихся циклов.
При этом произведение получается так: для каждого элемента от 1 до 4 надо пройти по циклам в левой части и проследить куда он переходит.
В частности, 3 сначала переходит в 1 (цикл (1 , 3)),
а затем 1 в 2 (цикл(1 , 2 , 4 , 3)).
Значит в произведении 3 будет переходить в 2.
Умножение перестановок некоммутативно: τσ ≠ στ .
Умножение перестановок, обратная перестановка, группа перестановок
Также обратная перестановка единственна. Это следует из того, что для каждой [math] i [/math] -ой позиций в исходной перестановке однозначно определяется [math] j [/math] -ая позиций в обратной перестановке, значение которой есть [math] i [/math]
| Определение: |
| Перестановка, равная своей обратной, называется инволюцией (англ. involution): [math] a_i = a^<-1>_i \Rightarrow (aa ^<-1>)_i = (aa)_i = a_ |
| Определение: |
| Перестановка, содержащая чётное количество инверсий, называется чётной (англ. even permutation), в противном случае [math] — [/math] нечётной (англ. odd permutation). |
| Определение: |
| Перестановка, меняющая местами только два элемента, называется транспозицией (англ. transposition). |
Получение обратной перестановки [ править ]
Пусть в массиве [math] p [/math] содержится перестановка, длины [math] n [/math] , тогда после выполнения алгоритма в массиве [math] rep [/math] будет содержаться перестановка, обратная ей.
Группа перестановок [ править ]
Мощность симметрической группы: [math]\left\vert S_n \right\vert = n![/math]
Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
Группа чётных перестановок [ править ]
| Определение: |
| Группа чётных перестановок (англ. alternating group) [math] A_n [/math] является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится. |
Группа подстановок [ править ]
| Определение: |
| Подстановкой (англ. substitution) называется всякое взаимно однозначное отображение [math] A [/math] множества первых [math]n[/math] натуральных чисел на себя. |
Всякая подстановка [math]A[/math] может быть записана при помощи двух перестановок, подписанных одна под другой:
[math] A = \begin
Где через [math] a_
Перестановка. Циклы. Четность. Свойства
Пусть — конечное множество из элементов. Поскольку природа его элементов для нас несущественна, удобно считать, что . Взаимно однозначное отображение называется перестановкой из элементов (длины ).
В развернутой и наглядной форме перестановку : , , изображают двухрядным символом
полностью указывая все образы:
Число различных перестановок из чисел равно произведению , обозначаемому .
Множество всех перестановок длины будем обозначать символом .
Перестановки перемножаются в соответствии с общим правилом композиции отображений: То есть под произведением перестановок будем понимать их суперпозицию.
Например, для перестановок
Умножение перестановок подчиняется следующим правилам.
1. Умножение ассоциативно, то есть для всех .
2. обладает единичным элементом : для всех
3. Для каждой перестановки существует обратная
Эти три свойства дают основание говорить о группе, называемой симметрической группой степени .
Разложим теперь перестановки в произведение более простых перестановок. Идею разложения поясним схематически на примере указанных выше перестановок
Перестановка , носит название цикла длины 4, а перестановка — произведение двух независимых (непересекающихся) циклов и длины 2.
Каждая перестановка в является произведением независимых циклов длины . Это разложение в произведение определено однозначно с точностью до порядка следования циклов.
Обратим внимание на циклы длины 2.
Цикл длины 2 называется транспозицией.
Любая транспозиция имеет вид и оставляет на месте все символы, отличные от
Говорят, что элементы и образуют относительно перестановки правильную пару, если
Если то элементы образуют неправильную пару, которая также называется инверсией.
Если количество инверсий в перестановке ( ) является числом четным (нечетным), то перестановка называется четной (нечетной).
Знаком перестановки ( ) называется функция, определяемая следующим образом:
Утверждение. Пусть перестановка разложена в произведение независимых циклов длин Тогда .
1. Произведение четных перестановок – четная перестановка.
2. Произведение четной перестановки на нечетную — есть нечетная перестановка.
3. Умножение на транспозицию меняет четность перестановки.
4. Четные перестановки образуют группу.
5. Перестановка и ей обратная имеют одинаковую четность.
6. Число четных и нечетных перестановок равно
2. Элементы теории колец (кольцо многочленов)
Понятие кольца и поля. Свойства
Кольцо – непустое множество с определенными на нем двумя бинарными операциями «+» и « », условно называющимися сложением и умножением, удовлетворяющее следующим свойствам:
1) – является коммутативной (абелевой) группой;
2) выполняется ассоциативный закон
3) справедливы следующие равенства , .
Если относительно умножения выполняется закон коммутативности, то кольцо коммутативно.
Если в существует нейтральный элемент 1 относительно умножения, то кольцо называется кольцом с единицей (1 — единичный элемент).
Элементы, у которых есть обратный элемент относительно умножения, называются единицами кольца (обратимыми элементами).
Множество единиц кольца образует группу
множество элементов кольца, рассматриваемого относительно сложения, называется аддитивной группой кольца.
Ненулевые элементы называются левым и правым соответственно делителями нуля, если . Оказывается удобным и сам нуль считать делителем нуля.
Если в кольце нет делителей нуля, отличных от самого нуля, то есть если из следует, что или , или , то говорят о кольце без делителей нуля. Если, кроме того, кольцо коммутативно, то оно называется целостным.
Коммутативное кольцо с единицей, в котором любой ненулевой элемент имеет обратный, называется полем.
Область целостности – коммутативное кольцо с единицей, в которых нет делителей нуля.