играет роль единицы и называется тождественной подстановкой. У каждой подстановки имеется обратная:
Группа подстановок из n элементов {симметрическая группа n-й степени) имеет, очевидно, порядок n!.
Определение 1.8. Обратной для подстановки A называется подстановка той же степени A-1 такая, что AA-1=A-1A=E.
Так для подстановки обратной служит подстановка. Если нам нужно решить уравнения в подстановках: а) AX=B; б) XA=B; в) AXB=C, то мы поступим таким образом: 1) в случае а) умножим обе части уравнения AX=B слева (в виду не коммутативности умножения) на A-1, получим, A-1(AX)=A-1B, а так как умножение подстановок ассоциативно, то (A- 1A)X=A-1B, EX=A-1B, X=A-1B - решение уравнения AX=B; 2) в случае б) XA=B, (XA)A-1=BA-1, X(AA-1)=BA-1, X=BA-1; 3) в случае в) AXB=C, A-1(AXB)=A-1C,
XB=A-1C, (XB)B-1=(A-1C)B-1, X(BB-1)=A-1CB-1, X=A-1CB-1.
Теорема 1.2. При всех разложениях подстановки в произведение транспозиций четность числа этих транспозиций будет одна и та же, причем она совпадает с четностью самой подстановки.
Доказательство. Эта теорема будет доказана, если мы покажем, что произведение любых k транспозиций есть подстановка, четность которой совпадает с четностью k. Это утверждение доказываем по методу математической индукции. При k=1 это верно, так как всякая транспозиция есть нечетная подстановка. Пусть наше утверждение уже доказано для случая k-1 множителей. Тогда его справедливость для k множителей вытекает из того, что числа k-1 и k имеют противоположные четности, а умножение подстановки (в данном случае - произведение первых k-1 множителей - мы предположили, что это подстановка, четность которой совпадает с четностью числа k-1) на транспозицию равносильно выполнению этой транспозиции в нижней строке подстановки, то есть, меняет ее четность. Теорема доказана.
Согласно этой теореме, определить четность подстановки можно разложением подстановки в произведение транспозиций - их число определяет четность подстановки.
Рассмотрим подробнее один из способов разложения подстановки в произведение транспозиций. Он заключается в следующем: сначала разложим подстановку в произведение циклов, а затем каждый цикл разложим в произведение транспозиций. Для этого приведем новые определения и факты.
2.2 Циклические подстановки
Определение 1.9. Циклической подстановкой или циклом называется такая подстановка, что при повторении ее достаточное число раз, всякий из действительно перемещаемых ею символов может быть переведен в любой другой из этих символов. Такова, например, подстановка восьмой степени
Она действительно перемещает символы 2, 3, 6 и 8, причем переводит
символ 2 в 8, символ 8 в 3, символ 3 в 6, а символ 6 снова в 2.
Для циклов употребляется следующая запись: действительно переставляемые символы записываются в круглых скобках друг за другом в том порядке, в каком они друг в друга переходят при повторении подстановки; начинается запись с любого из действительно перемещаемых символов, а последний символ считается переходящим в первый. Так, для указанного выше примера эта запись имеет вид (2836).
Число символов, действительно перемещаемых циклом, называется длиной цикла.
Два цикла n-й степени называются независимыми, если они не имеют общих действительно переставляемых символов. Понятно, что при перемножении независимых циклов порядок расположения множителей не влияет на результат.
Всякая подстановка может быть единственным способом разложена в произведение независимых циклов.
Практически разложение осуществляется следующим образом: начинаем с любого из действительно перемещаемых символов и выписываем за ними те символы, в которые он переходит при повторении подстановки, пока не вернемся к исходному символу. После этого "закрытия" цикла начинаем с одного из оставшихся действительно перемещаемых символов, получаем второй цикл и так далее. Например,
Обратно, для всякой подстановки, заданной разложением в независимые циклы, можно найти запись в обычной форме (при условии, что степень этой подстановки известна). Например,если известно, что степень этой подстановки есть 7.
Циклическая подстановка длины k при возведении в kстепень дает тождественную подстановку E.
Пусть дана подстановка n-й степени и пусть s есть число независимых циклов в ее разложении плюс число символов, оставляемых ею на месте.
Если множество N конечно и содержит п чисел, то множество S всех подстановок п-й степени также конечно и содержит п! элементов. Такая группа называется симметрической группой порядка п! (порядок группы определяется числом ее элементов).
Полгруппы симметрических групп называют группами подстановок. К ним относятся единичная группа, содержащая только нейтральный элемент (тождественную подстановку), и сама симметрическая группа. Однако, кроме этих тривиальных групп, имеется много подгрупп симметрической группы, являющихся группами подстановок. В частности, группу образует множество всех четных подстановок (знакопеременная группа). Множество всех подстановок переводящих какой-либо элемент в себя, также является группой.
Подгруппами симметрических групп исчерпываются по существу все конечные группы. Имеет место следующая теорема.
теорема Кэли. всякая конечная группа порядка п изоморфна некоторой группе подстановок п-й степени ее элементов.
Доказательство. Пусть множество с определенным на нем законом композиции T образует группу и - фиксированный элемент из G. Определим отображение, ставящее каждому элементу из G элемент , следующим образом:
T , i = 1, 2, ... .... п.
Это отображение взаимно-однозначно, так как при любом соотношение T имеет единственное решение T , т.к. каждый элемент группы имеет единственный симметричный ему . Таким образом, взаимно-однозначное отображение на множестве G можно представить подстановкой п объектов , которая соответствует элементу , т. е.
В этой подстановке нижняя перестановка - это строка матрицы композиции для элемента . Принимая k = 1, 2, ..., n, получаем п подстановок, соответствующих п элементам группы G. Нейтральному элементу отвечает тождественная подстановка е, симметричному элементу - симметричная подстановка .
Так как групповая операция T по определению ассоциативна, то
T T = T (T) = .
С другой стороны,
T T = (T ) T = T = .
Отсюда , т. е. элементу T соответствует композиция отображения и , а значит, и композиция соответствующих им подстановок. Таким образом, множество подстановок образует группу порядка п, которая однозначно представляет группу G.
Например, группе третьего порядка с групповой операцией, заданной таблицей
соответствует группа подстановок , где
; ; .
Нейтральным элементом этой группы относительно определенного закона композиции является , а подстановки и - взаимно симметричные элементы (проверить самостоятельно). Если элементы исходной группы пронумеровать и заменить соответствующими им числами, то
; ; .
Эта группа подстановок является подгруппой симметрической группы, которая, кроме указанных подстановок содержит подстановки
; ; .
каждая из которых обратна самой себе. Ясно, что при большом п для представления конечной группы п-го порядка используется лишь ничтожная часть перестановок симметрической группы.
2.3. Умножение подстановок
Определение. Произведением первой подстановки на вторую называют последовательное выполнение двух подстановок n-й степени, приводящее к некоторой вполне определенной третьей подстановке n-й степени.
так, если даны подстановки четвертой степени
то
Действительно, при подстановке А символ 1 переходит в 3, но при В символ 3 переходит в 4, поэтому при АВ символ 1 переходит в 4, и т. д.
Можно перемножить лишь подстановки одинаковой степени. Умножение подстановки n-й степени при n ? 3некоммутативно. Действительно, для рассмотренных выше подстановок А и В произведение ВА имеет вид
т. е. подстановка ВА отлична от подстановки АВ. Такие примеры можно подобрать для всех n при n ? 3, хотя для некоторых пар подстановок закон коммутативности случайно может выполняться.
Умножение подстановок ассоциативно, т. е. можно говорить о произведении любого конечного числа подстановок n-й степени, взятых (ввиду некоммутативности) в определенном порядке. В самом деле, пусть даны подстановки А, В и С и пусть символ i1, 1 ? i1 ? n, переходит при подстановке А в символ i2, i2 при подстановке В переходит в символ i3, а последний при подстановке С - в символ i4. Тогда при подстановке АВ символ i1 переходит в i3, при подстановке ВС символ i2 переходит в i4, а поэтому как при (АВ)С, так и при А(ВС) символ i1 ,будет переходить в символ i4.
Очевидно, что произведение любой подстановки А на тождественную подстановку Е, а также произведение Е на А, равно А:
АЕ=ЕА=А
Назовем, наконец, обратной для подстановки А такую подстановку А-1 той же степени, что
АА-1 = А-1А = Е
Легко видеть, что обратной подстановкой для подстановки
служит подстановка
получающаяся из А переменой мест верхней и нижней строк.
Пример 5.
Найти подстановку, обратную данной
Решение.
Подстановка А-1, обратная подстановке А будет иметь вид
приведем её к каноническому виду
Пример 6.
Найти порядок указанного элемента в группе Sn, n=5
Решение:
Наконец, получили тождественную подстановку Е
Ответ: 6
2.3. Разложение подстановок в произведение циклов с непересекающимися орбитами
Орбитой цикла (i1 i2 ... ir) назовем множество {i1,...,ir} .
Если - подстановка символов {1,2,...,n} и , , то рассмотрим последовательность
(орбиту элемента a ). Из конечности множества {1,2,...,n} следует, что найдутся такие натуральные числа t и s, t<s, что . В группе S_n рассмотрим . Применяя к этому равенству, получим , r=s-t>0. Рассмотрим самое маленькое такое натуральное число r (со свойством , при этом все r элементов различны). Итак, получили цикл длины r. Выбирая элемент b вне этого цикла (если r<n ), получаем цикл длины r', при этом орбиты этих циклов не пересекаются. Продолжим этот процесс. Заметим, что циклы с непересекающимися орбитами перестановочны. Единственность этого разложения следует из инвариантности определения орбиты. Итак, получаем следующее утверждение.
Теорема 5.3.1. Каждая подстановка разлагается (и притом единственным образом) в произведение циклов с непересекающимися орбитами (поэтому эти циклы перестановочны друг с другом).
Замечание 5.3.2.
1. В практических задачах удобно начинать с a=1, затем число b выбирать как наименьшее число, не вошедшее в ,и т. д.
2. Как правило, циклы длины 1 (т. е. неподвижные элементы) опускают в записи циклового разложения подстановки.
Упражнение 5.3.3.
1. Пусть . Подстановка называется подстановкой, сопряженной с подстановкой (с помощью подстановки ). Проверьте, что отношение сопряженности является отношением эквивалентности. Соответствующее разбиение множества Sn на классы эквивалентных подстановок называется разбиением на классы сопряженных элементов .
2. Доказать, что подстановки сопряжены тогда и только тогда, когда и имеют одинаковое цикловое разложение (т. е. одинаковое число циклов каждой длины в своих разложениях в произведение циклов с непересекающимися орбитами).
Указания
.
Если - цикл длины r, то .
Заключение
Выполняя эту курсовую работу я узнала, то что не знала. Поглубже изучил эту тему я много узнала о перестановках и подстановках, как вычислить четность или нечетность или знак перестановки, о циклических подстановок, как оно решается, или каким способом. Уделяя важное внимание на под темы этого работу глубже понял важные места и роль перестановок нашей жизни. Умножение подстановок ассоциативно, но, вообще говоря, не коммутативно. Рассмотрим подробнее один из способов разложения подстановки в произведение транспозиций. Он заключается в следующем: сначала разложим подстановку в произведение циклов, а затем каждый цикл разложим в произведение транспозиций. Все четные подстановки симметрической группы образуют в ней подгруппу. Порядок этой подгруппы равен, очевидно, . Она называется знакопеременной подгруппой симметрической группы и обозначается символом .
Список литературы
1. Апатенок Р.Ф. и др. Элементы линейной алгебры и аналитической геометрии. - Минск: Высшая. школа, 1986. - 272 с.
2. Тевяшев А.Д., Литвин О.Г. Алгебра и геометрия : Линейная алгебра. Аналитическая геометрия: - Харкив: ХТУРЕ, 2000. - 388 с. .
3. Данко П.Е. и др. Высшая математика в упражнениях и задачах. Ч.I. - М.: Высш. шк., 1986. - 304с. .
4. Тевящев А.Д., Литвин О.Г. Высшая математика. Загальний курс: Сборник задач та вправ. - Х.:Рубикон, 1999. - 320 с. .
6. Барковский В.В., Барковская Н.В. Математика для экономистов. Высшая математика. - К.: Национальная академия управления, 1999. - 399 с