Группа подстановок, подстановка п числа, композиция, группа симметрии фигуры. Группа подстановок, подстановка п числа, композиция, группа симметрии фигуры Как записать подстановку двумя строками

Взаимно однозначное отображение на себя (или преобразование) конечного множества N = { 1, 2, 3, п} первых п натуральных чисел называют подстановкой п чисел (или подстановкой n-d степени). Подстановку принято записывать в виде заключенных в круглые скобки двух строк чисел. Например, взаимно однозначное соответствие натуральных чисел 1, 2 и 3, заданное множеством {(2, 3), (1, 2), (3, 1)} упорядоченных пар) записывают в виде подстановки р третьей степени (2 1 3 \ Р=13 2 1 J" в которой 2 переходит в 3, 1 - в 2 и 3 - в 1. Поскольку отображение не изменится при изменении порядка расположения упорядоченных пар, одну и ту же подстановку можно представить в нескольких формах: Предпочтительнее запись, при которой числа в верхней строке расположены в естественном порядке. Тогда подста- новка 71-и степени принимает вид (4.19) где t"i, t"2, in -расположенные в некотором определенном порядке первые п натуральных чисел. Каждое изменение их расположения будет задавать новую подстановку, а общее число подстановок n-й степени совпадет с числом п! перестановок первых п элементов множества N в нижней строке (4.19). Тождественная подстановка n-й степени переводит каждое число в себя и может быть записана в виде (4.20) Композицией p2°Pi подстановок п-й степени pi и Рз называют подстановку n-й степени p = pipi} которая является результатом последовательного выполнения отображения, сперва задаваемого рi, а затем задаваемого />2. Композицию подстановок записывают в виде их произведения, но взятых в обратном порядке, причем pip? фрър\. Например, для подстановок Ясно, что если р - подстановка n-й степени, то т.е. еп выполняет роль нейтрального элемента относительно закона композиции отображений. Если строки подстановки р в (4.19) поменять местами, то получим подстановку обратную к подстановке р и обладающую свойством т.е. р"1 выполняет роль симметричного для р элемента относительно закона композиции отображений. Таким образом, множество Р из п! подстановок n-й степени образует мультипликативную группу (см. табл. 4.1) относительно этого закона, который в данном случае играет роль мультипликативного закона (ассоциативного, но не коммутативного). Множество Р называют группой подстановок n-й степени. Поскольку при записи в виде (4.19) первая строка неизменна, подстановку n-й степени можно задать лишь второй строкой: Группа подстановок подстановка п числа композиция группа симметрии фигуры т.е. перестановкой первых п элементов множества N. Бели в такой перестановке поменять местами любые два числа (не обязательно стоящие рядом), а остальные оставить на своих местах, то получим новую перестановку. Это преобразовал ние называют транспозицией перестановки. Два числа образуют инверсию в перестановке, когда меньшее из них расположено правее большего (или, как говорят, большее число в перестановке встречается раньше меньшего). Перестановку наг зывают четной, если общее число инверсий в ее строке четное, и нечетной - в противном случае. Для подсчета общего числа инверсий в некоторой перестаг новке из п элементов последовательно сравнивают каждый элемент, начиная с первого слева, со всеми, следующими за ним, g определяют количество стоящих правее его меньших чисел. Это дает число инверсий данного элемента. Полученные таким образом п-1 чисел складывают. Пример 4.12. а. Перестановка (1, 2, ..., п) четная при любом п, так как число инверсий в ней равно нулю. б. Перестановка () содержит 14 инверсий и поэтому четная. в. Перестановка () содержит 17 инверсий и поэтому нечетная. Теорема 4.7. Любая транспозиция меняет четность перестановки. Рассмотрим сначала случай, когда переставляемые числа г и j стоят рядом, т.е. перестановка исходная и перестановка, полученная транспозицией, имеют вид где многоточия заменяют те числа, которые не затрагивает данная транспозиция. В обеих перестановках каждое из чисел t, j составляет одни и те же инверсии с числами, которые остаются на своих местах. Если числа г и в исходной перестановке не образовывали инверсии, то после транспозиции возникнет одна новая инверсия. Бели же эти числа в исходной перестановке образовывали инверсию, то после транспозиции она исчезнет, т.е. общее количество инверсий станет на одну меньше. В обоих случаях четность перестановки меняется. Пусть теперь между переставляемыми числами г и j расположены т чисел (т 6 N), т.е. исходная перестановка имеет вид Переставить местами «ела i и j можно в результате последовательной смены мест соседних чисел, выполнив 2т +1 шагов (переставим t с klf затем t, стоящее уже на месте A?i, с и т.д., пока г за т шагов не займет место кт и не станет рядом с j; затем поменяем местами i и У, и, наконец, еще m шагов уйдет на то, чтобы последовательно j переставить с кт-1 и т.д., после чего j займет место i, а числа к кт сохранят свои места). При зтом четность перестановки меняется нечетное число (2т+ 1) раз. Поэтому перестановки (4.21) и имеют противоположные четности. Рассмотрим запись подстановки (4.19). Перестановки, составляющие ее верхнюю и нижнюю строки, могут иметь или одинаковые, или противоположные четности. Переход к любой другой записи можно осуществить путем последовательного выполнения нескольких транспозиций в верхней строке и соответствующих им транспозиций в нижней строке. Однако совершая одну транспозицию в верхней строке (4.19) и одну транспозицию соответствующих элементов в нижней строке, мы одновременно меняем четности обеих перестановок и поэтому сохраняем совпадение или противоположность их четностей. Отсюда следует, что при любой записи подстановки четности верхней и нижней строк либо совпадают, либо противоположны. Группа подстановок подстановка п числа композиция группа симметрии фигуры Определение 4.10. Подстановку называют четной, если перестановки в ее обеих строках имеют одинаковую четность, и нечетной - если противоположную. Ясно, что тождественная подстановка (4.20) является четной, а четность подстановки, задаваемой в виде (4.19), совпадает с четностью перестановки в ее нижней строке. Сказанное выше можно обобщить применительно к взаимно однозначному отображению на себя (преобразованию) любого конечного множества Е- {ni, 02, an} (не обязательна числового), если пронумеровать его элементы первыми п натуральными числами. Пример 4.13. Пусть - вершины равностороннего треугольника (рис. 4.5). ^Гогда множество Р из п! = 3! = 6 подстановок где «ь »2, «з - расположенные в некотором порядке три натуральных числа 1, 2, 3, описывает группу рис. 4,5 симметрий этого треугольника, т.е. таких перемещений треугольника в плоскости, при которых он совпадает с самим собой. Тождественная подстановка е, когда, оставляет треугольник на месте. При (четные подстановки а и 0) происходит поворот треугольника против часовой стрелки относительно точки О соответственно на углы а = =3 (см. рис. 4.5). При (нечетная подстановка q) треугольник поворачивается вокруг оси симметрии OA. Повороты вокруг осей симметрии ОВ и ОС задают нечетные подстановки г и з соответственно при 4 = 3, «2 = 2, «з = 1 и «1 = 2, «2=1, «З = 3. Произведение pip? любых из этих подстановок также задает одну из операций совмещения треугольника (например, qr = /?). В левом столбце и верхней строке табл. 4.2 помещены обозначения подстановок р\ и р2 соответственно, а на остальных местах - произведения pip? этих подстановок. В каждой строке и в каждом столбце табл. 4.2 присутствует тождественная подстановка е, т.е. всякая операция имеет симметричную (или обратную), причем для операции поворота относительно любой оси симметрии (и, разумеется, для тождественной операции) обратной является сама эта операция. Таблица несимметрична относительно своей главной диагонали (проходящей через верхний левый и правый нижний элементы), что еще раз показывает, что произведение подстановок некоммутативно. Рассмотренное множество Р подстановок называют также группой симметрии фигуры (в данном случае равностороннего треугольника). Аналогично можно построить группу симметрий любого другого геометрического объекта как совокупность всех преобразований метрического пространства, совмещающих его с ним самим (например, группу симметрий квадрата, куба, тетраэдра и т.п.). Именно с таких позиций Е.С. Федоров в 1890 г. построил классификацию правильных пространственных систем точек применительно к кристаллографии. Это было исторически первое приложение теории групп непосредственно в естествознании. Вопросы и задачи 4.1. Проверить, обладает ли закон композиции (операция) т свойствами ассоциативности и коммутативности на множестве Е: где НОД - наибольший общий делитель двух натуральных чисел. 4.2. Установить, какие алгебраические структуры образуются следующими числовыми множествами относительно указанных законов композиции: а) одно из множеств относительно сложения и относительно умножения; б) множество всех четных чисел относительно сложения и умножения; в) множество степеней заданного действительного числа аф Ос целыми показателями относительно умножения; г) множество всех комплексных корней заданной степени п € N из единицы относительно умножения; д) множество комплексных корней всех степеней п € 14 из единицы относительно умножения; е) множества комплексных чисел с заданным модулем г € R относительно умножения; ж) множество комплексных чисел с модулем, не превосходящим заданное число R ф 0, относительно сложения и относительно умножения; з) множество комплексных чисел с ненулевым модулем, расположенных на лучах, выходящих из начала координат и образующих с осью Ох углы y>2i » ¥>m относительно умножения. и) множество Р(Е) всех подмножеств некоторого множества Е относительно операций симметрической разности и пересечения и относительно каждой из них в отдельности. 4.3. На множестве Е = {о, 6, с} одной из таблиц задан закон композиции т. Для каждого из этих законов определить его свойства, указать нейтральный элемент и пары симметричных элементов (если они существуют), установить тип алгебраической структуры. 4.4. На множестве Е = {о, 6, с} при помощи таблиц заданы аддитивный (+) и мультипликативный (*) законы композиции. Для каждого из этих законов определить его свойства, указать нейтральный элемент и пары симметричных элементов (если они существуют). Какую алгебраическую структуру образует множество Е относительно каждого из заданных законов и какую - относительно обоих законов? Какой смысл приобретают эти законы в числовом множестве, если положить а = 1, 6 = 2, с = 3 ? 4.5. На множестве Е= {0, 1, ру д} при помощи таблиц заданы аддитивный (+) и мультипликативный (*) законы композиции. Для каждого из этих законов определить его свойства, указать нейтральный элемент и пары симметричных элементов (если они существуют). Какую алгебраическую структуру образует множество Е относительно каждого из заданных законов и какую - относительно обоих законов? 4.6. Доказать свойства операций сложения и умножения комплексных чисел. 4.7. Найти действительную и мнимую части комплексных чисел: 4.8. Доказать равенства: Группа подстановок подстановка п числа композиция группа симметрии фигуры 4.9. Доказать, что | £ С. При каких условиях эти неравенства переходят в равенства? 4.10. Найти все комплексные числа, сопряженные к своему а) квадрату и б) кубу. 4.11. Пусть на комплексной плоскости заданы три точки zlf z3. 1. Найти точку г, определяющую положение центра масс системы материальных точек с массами mi, т2) тз, расположенных в заданных трех точках. При каком условии центр масс будет в начале координат? 2. Заданные точки являются вершинами треугольника. Найти точку пересечения его медиан. При каком условии она будет в начале координат? 3. Заданные точки являются тремя вершинами А\% А2у параллелограмма. Найти его четвертую вершину Л4, Противолежащую А2. При каком условии она будет в начале координат? 4. При каком условии заданные точки лежат на одной прямой? 5. Найти центр окружности, проходящей через заданные точки. При каком условии он будет в начале координат? 6. Как расположены заданные точки, если |zi| = \z2\ = = 1*з| ф 0 и zi + z2 + г3 = 0? 4.12. Найти множество точек комплексной плоскости, заданных условием: 4.13. Доказать равенства: а 4.14. Верно ли равенство (* 4.15. Найти произведение всех корней степени п € N из единицы. 4.16. Является ли число (2 + i)/(2-«) корнем некоторой степени из единицы? 4.17. Найти комплексные числа, соответствующие противоположным вершинам квадрата, если двум другим вершинам соответствуют числа z\ и 23. 4.18. Найти комплексные числа, соответствующие верши-вам правильного n-угольника, если двум его соседним вершинам соответствуют числа z\ и 22 4.19. Доказать, что целые нули многочлена с целыми коэффициентами являются делителями его свободного члена (коэффициента ап), и найти целые нули многочленов: 4.20. Доказать, что каждый многочлен нечетной степени с действительными коэффициентами имеет по крайней мере один действительный нуль. 4.21. Найти многочлен наименьшей степени с действительными коэффициентами, нулями которого являются: а) 3 и 2-i; б) t (корень кратности 2) и -1-i; в) 0, 1, i. 4.22. Найти: а) многочлен с нулями х\ при условии, что числа a?i, Х2 и а?з являются нулями многочлена х3 -х2 -1; б) значение а, при котором нули многочлена х3-1-х2 + 2а:+а образуют геометрическую прогрессию; в) сумму квадратов и сумму кубов нулей многочлена 8а:4 -- 5®2 + 2« + 1; г) сумму всех коэффициентов многочлена: 1) ; д) многочлен Р(х) наименьшей степени по условию: Найти четность подстановок: 4.24. Записать группу симметрий квадрата, найти четность каждой подстановки из этой группы, построить таблицу, аналогичную табл. 4.2, и проанализировать ее.

Определение 5. Подстановкой N-й степени называется взаимно однозначное отображение Множества самого на себя. Обычно подстановку записывают с помощью двух N -перестановок, записанных одна под другой:

, (1)

Где через обозначается число, в которое при подстановке переходит элемент i , т. е. ; i=1,2,...,N .

В записи подстановки можно произвольным образом менять столбцы местами. Например, все три указанные ниже подстановки равны.

. (2)

В частности всякая подстановка N -й степени может быть записана в виде:

При такой форме записи различные подстановки различаются только перестановками, стоящими в нижней строке. Тогда в силу теоремы 1 получили следующее утверждение.

Теорема 4. Число различных подстановок n-й степени равно N.

Определение 6. Числом инверсий в подстановке называется сумма числа инверсий в первой и второй строках подстановки.

Обозначаем число инверсий в подстановке символом . Подстановка называется Четной, если число четное, и называется Нечетной если число нечетное. Знаком подстановки называется число:

Таким образом знак подстановки равен 1 или -1 в зависимости от того четная подстановка или нечетная.

В силу теоремы 2 при перестановке столбцов в подстановке одновременно четности перестановок, стоящих в нижней и верхней строках подстановки, меняются на противоположные. Следовательно, четность перестановки сохраняется. Отсюда и из теоремы 3 получаем, следующие свойства подстановок.

1. Четность и знак подстановки не зависят от формы записи подстановки.

2. При N >1 число четных подстановок N -й степени равно числу нечетных подстановок и равно .

Пример 4. Подстановка (2) нечетная и имеет знак -1, хотя при различных формах записи имеет 3, 7, 5 инверсий.

Покажем, что множество всех подстановок N -й степени образует группу относительно операции умножения подстановок, определенной ниже. Эта группа имеет большое значение в алгебре, называется Симметрической Группой и обозначается символом .

Определение 7. Произведением подстановок и N -й степени называется композиция Этих постановок как отображений, т. е. для любого имеем . Обозначаем

Так как композиция двух биективных отображений биективное отображение, то произведение двух подстановок N -й степени есть подставок N -й степени. При практическом умножении подстановок сначала выполняется правая подстановка, а затем левая. Например,

Теорема 5. Множество всех подстановок n-й степени образует группу относительно операции умножения подстановок .

Доказательство. В силу сказанного выше операция умножения подстановок бинарная алгебраическая операция. Проверим аксиомы группы.

Умножение подстановок ассоциативно. Действительно, пусть . Тогда для любого

Определение . Всякое взаимно однозначное отображение множества А первых n натуральных чисел на себя называется подстановкой n -й степени , причем, очевидно, всякая подстановка А может быть записана при помощи двух перестановок, подписанных одна под другой

Через α i здесь обозначается то число, в которое при подстановке А переходит число i , i = 1, 2, …, n .

Запишем одну под другой две перестановки из n символов, беря полученные две строки в скобки; например, n=5:

Мы скажем, что число 3 переходит в число 5, число 5 переходит в 2, число 1 переходит в 3, число 4 переходит в 4(или остаётся на месте), и, наконец, число 2 переходит в 1. Таким образом, две перестановки, записанные друг под другом в виде (2), определяют некоторое взаимно однозначное отображение множества из первых пяти натуральных чисел на себя, т. е. отображение, которое каждому из натуральных чисел 1, 2, 3, 4, 5 ставит в соответствие одно из этих же натуральных чисел, причем разным числам ставятся в соответствие различные же числа.

Ясно, что то взаимно однозначное отображение множества их первых пяти натуральных чисел, которые мы получили при помощи (2), можно было получить, записывая одну под другой и некоторые другие пары перестановок из пяти символов. Эти записи получаются из (2) путем нескольких транспозиций (перестановок) столбиков; таковы, например,

Во всех этих записях 3 переходит в 5, 5 в 2 и т. д.

Подстановка А обладает многими различными записями вида (1). Так, (2) и (3) являются различными записями одной и той же подстановки 5-й степени.

Канонический вид подстановки

В частности, всякая подстановка n-й степени А может быть записана в каноническом виде

т. е. с натуральным расположением чисел в верхней строке. При такой записи различные подстановки отличаются друг от друга перестановками, стоящими в нижней строке.

Примером подстановки n-й степени служит тождественная подстановка

при котором на месте остаются все символы.

Замечание . Следует заметить, что верхняя и нижняя строки в записи (1) подстановки А играют разные роли и, переставив их, мы, вообще говоря, получаем другую подстановку.