Группа перестановок

Группа, операция которой представляет собой композицию перестановок

В математике группа перестановок — это группа G , элементы которой являются перестановками заданного множества M , а групповая операция — это композиция перестановок в G (которые рассматриваются как биективные функции из множества M в себя). Группа всех перестановок множества M — это симметрическая группа M , часто записываемая как Sym( M ). ^[1] Таким образом, термин «группа перестановок» означает подгруппу симметрической группы. Если M = {1, 2, ..., n }, то Sym( M ) обычно обозначается как S _n и может называться симметрической группой от n букв .

По теореме Кэли каждая группа изоморфна некоторой группе перестановок.

Способ, которым элементы группы перестановок переставляют элементы множества, называется ее групповым действием . Групповые действия имеют приложения в изучении симметрии , комбинаторики и многих других разделов математики , физики и химии.

Популярная головоломка кубик Рубика, изобретенная в 1974 году Эрнё Рубиком, использовалась в качестве иллюстрации групп перестановок. Каждое вращение слоя куба приводит к перестановке цветов поверхности и является членом группы. Группа перестановок куба называется группой кубика Рубика .

Основные свойства и терминология

Группа перестановок — это подгруппа симметрической группы ; то есть ее элементы являются перестановками заданного множества. Таким образом, это подмножество симметрической группы, которое замкнуто относительно композиции перестановок, содержит тождественную перестановку и содержит обратную перестановку каждого из своих элементов. ^[2] Общее свойство конечных групп подразумевает, что конечное непустое подмножество симметрической группы является группой перестановок тогда и только тогда, когда оно замкнуто относительно композиции перестановок. ^[3]

Степень группы перестановок конечного множества — это число элементов в множестве. Порядок группы (любого типа) — это число элементов (мощность) в группе. По теореме Лагранжа порядок любой конечной группы перестановок степени n должен делить n !, поскольку n - факториал — это порядок симметрической группы S _n .

Обозначение

Поскольку перестановки являются биекциями множества, их можно представить с помощью двухстрочной нотации Коши . ^[4] Эта нотация перечисляет каждый из элементов M в первой строке, а для каждого элемента — его образ под перестановкой под ним во второй строке. Если — перестановка множества , то ${\displaystyle \sigma }$ ${\displaystyle M=\{x_{1},x_{2},\ldots ,x_{n}\}}$

${\displaystyle \sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.}$

Например, конкретную перестановку набора {1, 2, 3, 4, 5} можно записать как

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}};}$

это означает, что σ удовлетворяет σ (1) = 2, σ (2) = 5, σ (3) = 4, σ (4) = 3 и σ (5) = 1. Элементы M не обязательно должны появляться в каком-либо особом порядке в первой строке, поэтому ту же перестановку можно записать как

${\displaystyle \sigma ={\begin{pmatrix}3&2&5&1&4\\4&5&1&2&3\end{pmatrix}}.}$

Перестановки также часто записываются в циклической нотации ( циклическая форма ) ^[5] , так что, если задано множество M = {1, 2, 3, 4}, перестановка g из M с g (1) = 2, g (2) = 4, g (4) = 1 и g (3) = 3 будет записана как (1, 2, 4)(3) или, что более распространено, (1, 2, 4), поскольку 3 остается неизменным; если объекты обозначены отдельными буквами или цифрами, запятые и пробелы также можно опустить, и мы получим такую ​​запись, как (124). Перестановка, записанная выше в 2-строчной нотации, будет записана в циклической нотации как ${\displaystyle \sigma =(125)(34).}$

Композиция перестановок – групповое произведение

Произведение двух перестановок определяется как их композиция как функций, так же как и функция, которая отображает любой элемент x множества в . Обратите внимание, что самая правая перестановка применяется к аргументу первой из-за способа записи композиции функций. ^{[6] [7]} Некоторые авторы предпочитают, чтобы самый левый множитель действовал первым, но для этого перестановки должны быть записаны справа от их аргумента, часто как верхний индекс , поэтому перестановка, действующая на элемент, приводит к изображению . При таком соглашении произведение задается как . ^{[8] [9] [10]} Однако это дает другое правило для умножения перестановок. Это соглашение обычно используется в литературе по группам перестановок, но в этой статье используется соглашение, где самая правая перестановка применяется первой. ${\displaystyle \sigma \cdot \pi }$ ${\displaystyle \sigma (\pi (x))}$ ${\displaystyle \sigma }$ ${\displaystyle x}$ ${\displaystyle x^{\sigma }}$ ${\displaystyle x^{\sigma \cdot \pi }=(x^{\sigma })^{\pi }}$

Так как композиция двух биекций всегда дает другую биекцию, произведение двух перестановок снова является перестановкой. В двухстрочной записи произведение двух перестановок получается путем перестановки столбцов второй (самой левой) перестановки так, чтобы ее первая строка совпадала со второй строкой первой (самой правой) перестановки. Затем произведение можно записать как первую строку первой перестановки над второй строкой измененной второй перестановки. Например, учитывая перестановки,

${\displaystyle P={\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}\quad {\text{ and }}\quad Q={\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}},}$

QP продукта составляет:

${\displaystyle QP={\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}}{\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}={\begin{pmatrix}2&4&1&3&5\\4&2&5&3&1\end{pmatrix}}{\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}}.}$

Композиция перестановок, когда они записаны в циклической нотации, получается путем сопоставления двух перестановок (вторая записана слева) и последующего упрощения до формы непересекающегося цикла, если это необходимо. Таким образом, указанное выше произведение будет иметь вид:

${\displaystyle Q\cdot P=(15)(24)\cdot (1243)=(1435).}$

Поскольку композиция функций ассоциативна , то же самое можно сказать и о операции произведения перестановок: . Поэтому произведения двух или более перестановок обычно записываются без добавления скобок для выражения группировки; они также обычно записываются без точки или другого знака для обозначения умножения (точки в предыдущем примере были добавлены для выразительности, поэтому их можно было бы просто записать как ). ${\displaystyle (\sigma \cdot \pi )\cdot \rho =\sigma \cdot (\pi \cdot \rho )}$ ${\displaystyle \sigma \pi \rho }$

Нейтральный элемент и обратные ему элементы

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

${\displaystyle {\begin{pmatrix}1&2&3&\cdots &n\\1&2&3&\cdots &n\end{pmatrix}}.}$

В циклической нотации e = (1)(2)(3)...( n ), что по соглашению также обозначается просто (1) или даже (). ^[11]

Поскольку биекции имеют обратные , то же самое происходит и с перестановками, и обратный σ ⁻¹ для σ снова является перестановкой. Явно, всякий раз, когда σ ( x )= y, также имеем σ ⁻¹ ( y )= x . В двухстрочной записи обратный можно получить, поменяв местами две строки (и отсортировав столбцы, если требуется, чтобы первая строка была в заданном порядке). Например,

${\displaystyle {\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}^{-1}={\begin{pmatrix}2&5&4&3&1\\1&2&3&4&5\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5\\5&1&4&3&2\end{pmatrix}}.}$

Чтобы получить обратный цикл, мы меняем порядок его элементов на обратный. Таким образом,

${\displaystyle (125)^{-1}=(521)=(152).}$

Чтобы получить инверсию произведения циклов, мы сначала меняем порядок циклов на обратный, а затем берем инверсию каждого из них, как указано выше. Таким образом,

${\displaystyle [(125)(34)]^{-1}=(34)^{-1}(125)^{-1}=(43)(521)=(34)(152).}$

Наличие ассоциативного произведения, единичного элемента и обратных элементов для всех его элементов превращает множество всех перестановок M в группу Sym( M ); группу перестановок.

Примеры

Рассмотрим следующий набор G ₁ перестановок множества M = {1, 2, 3, 4}:

• е = (1)(2)(3)(4) = (1)
  • Это тождество, тривиальная перестановка, которая фиксирует каждый элемент.
• а = (1 2)(3)(4) = (1 2)
  • Эта перестановка меняет местами 1 и 2 и фиксирует 3 и 4.
• б = (1)(2)(3 4) = (3 4)
  • Как и предыдущий, но поменяны местами 3 и 4, а остальные исправлены.
• аб = (1 2)(3 4)
  • Эта перестановка, которая является композицией двух предыдущих, одновременно меняет местами 1 с 2 и 3 с 4.

G ₁ образует группу, так как aa = bb = e , ba = ab и abab = e . Эта группа перестановок, как абстрактная группа , является группой Клейна V ₄ .

В качестве другого примера рассмотрим группу симметрий квадрата . Пусть вершины квадрата обозначены 1, 2, 3 и 4 (против часовой стрелки вокруг квадрата, начиная с 1 в верхнем левом углу). Симметрии определяются изображениями вершин, которые, в свою очередь, могут быть описаны перестановками. Вращение на 90° (против часовой стрелки) вокруг центра квадрата описывается перестановкой (1234). Вращения на 180° и 270° задаются формулами (13)(24) и (1432) соответственно. Отражение относительно горизонтальной прямой, проходящей через центр, задается формулами (12)(34), а соответствующее отражение относительно вертикальной прямой — (14)(23). Отражение относительно диагональной прямой 1,3 — это (24), а отражение относительно диагональной прямой 2,4 — это (13). Единственная оставшаяся симметрия — это тождество (1)(2)(3)(4). Эта группа перестановок известна как абстрактная группа как диэдральная группа порядка 8.

Групповые действия

В приведенном выше примере группы симметрии квадрата перестановки «описывают» движение вершин квадрата, индуцированное группой симметрий. Обычно говорят, что эти элементы группы «действуют» на множество вершин квадрата. Эту идею можно уточнить, формально определив действие группы . ^[12]

Пусть G — группа , а M — непустое множество . Действие G на M — это функция f : G × M → M такая, что

• f (1, x ) = x , для всех x из M (1 — единичный (нейтральный) элемент группы G ), и
• f ( g , f ( h , x )) = f ( gh , x ) для всех g , h из G и всех x из M .

Эту пару условий можно также выразить так, что действие индуцирует групповой гомоморфизм из G в Sym ( M ) . ^[12] Любой такой гомоморфизм называется (перестановочным) представлением G на M .

Для любой группы перестановок действие, которое отправляет ( g , x ) → g ( x ), называется естественным действием G на M . Это действие, которое предполагается, если не указано иное. ^[12] В примере группы симметрии квадрата действие группы на множестве вершин является естественным действием. Однако эта группа также индуцирует действие на множестве из четырех треугольников в квадрате, которые являются: t 1 ₌ 234, t ₂ = 134, t ₃ = 124 и t ₄ = 123. Она также действует на две диагонали: d ₁ = 13 и d ₂ = 24.

Переходные действия

Действие группы G на множестве M называется транзитивным , если для любых двух элементов s , t из M существует некоторый элемент группы g такой, что g ( s ) = t . Эквивалентно, множество M образует одну орбиту под действием G . ^[13] Из приведенных выше примеров группа {e, (1 2), (3 4), (1 2)(3 4)} перестановок {1, 2, 3, 4} не является транзитивной (никакой элемент группы не переводит 1 в 3), но группа симметрий квадрата транзитивна на вершинах.

Примитивные действия

Группа перестановок G, действующая транзитивно на непустом конечном множестве M, является импримитивной, если существует некоторое нетривиальное разбиение множества M , которое сохраняется под действием G , где «нетривиальное» означает, что разбиение не является разбиением на одноэлементные множества и не является разбиением только с одной частью. В противном случае, если G транзитивна, но не сохраняет никакого нетривиального разбиения M , группа G является примитивной .

Например, группа симметрий квадрата импримитивна на вершинах: если они пронумерованы 1, 2, 3, 4 в циклическом порядке, то разбиение {{1, 3}, {2, 4}} на противоположные пары сохраняется каждым элементом группы. С другой стороны, полная симметрическая группа на множестве M всегда примитивна.

Теорема Кэли

Любая группа G может действовать на себя (элементы группы рассматриваются как множество M ) многими способами. В частности, существует регулярное действие, заданное (левым) умножением в группе. То есть f ( g , x ) = gx для всех g и x из G . Для каждого фиксированного g функция f _g ( x ) = gx является биекцией на G и, следовательно, перестановкой множества элементов G . Каждый элемент G можно рассматривать как перестановку таким образом, и поэтому G изоморфна группе перестановок; это содержание теоремы Кэли .

Например, рассмотрим группу G _{1 ,} действующую на множестве {1, 2, 3, 4}, указанном выше. Пусть элементы этой группы обозначены как e , a , b и c = ab = ba . Действие G ₁ на себя, описанное в теореме Кэли, дает следующее перестановочное представление:

е _е ↦ ( е )( а )( б )( в )

f _a ↦ ( ea )( bc )

f _b ↦ ( eb )( ac )

f _c ↦ ( ec )( ab ).

Изоморфизмы групп перестановок

Если G и H — две группы перестановок на множествах X и Y с действиями f ₁ и f ₂ соответственно, то мы говорим, что G и H изоморфны перестановкам (или изоморфны как группы перестановок ), если существует биективное отображение λ  : X → Y и изоморфизм групп ψ  : G → H такие, что

λ ( f ₁ ( g , x )) = f ₂ ( ψ ( g ), λ ( x )) для всех g из G и x из X . ^[14]

Если X = Y, то это эквивалентно тому, что G и H сопряжены как подгруппы Sym( X ). ^[15] Особый случай, когда G = H , а ψ — тождественное отображение, порождает концепцию эквивалентных действий группы. ^[16]

В примере симметрий квадрата, приведенном выше, естественное действие на множестве {1,2,3,4} эквивалентно действию на треугольниках. Биекция λ между множествами задается как i ↦ t _i . Естественное действие группы G ₁ выше и ее действие на себя (через левое умножение) не эквивалентны, поскольку естественное действие имеет неподвижные точки, а второе действие — нет.

Олигоморфные группы

Когда группа G действует на множество S , действие может быть естественным образом расширено до декартова произведения S ⁿ множества S , состоящего из n -кортежей элементов S : действие элемента g на n -кортеж ( s ₁ , ..., s _n ) задается формулой

г ( с ₁ , ..., с _n ) = ( г ( с ₁ ), ..., г ( с _n )).

Группа G называется олигоморфной , если действие на S ⁿ имеет только конечное число орбит для каждого положительного целого числа n . ^{[17] [18]} (Это происходит автоматически, если S конечно, поэтому этот термин обычно представляет интерес, когда S бесконечно.)

Интерес к олигоморфным группам частично основан на их применении в теории моделей , например, при рассмотрении автоморфизмов в счетно-категоричных теориях . ^[19]

История

Изучение групп изначально выросло из понимания групп перестановок. ^[20] Перестановки сами по себе интенсивно изучались Лагранжем в 1770 году в его работе по алгебраическим решениям полиномиальных уравнений. Эта тема процветала, и к середине 19 века существовала хорошо развитая теория групп перестановок, систематизированная Камиллом Жорданом в его книге Traité des Substitutions et des Équations Algébriques 1870 года. Книга Жордана, в свою очередь, основывалась на работах, которые были оставлены Эваристом Галуа в 1832 году.

Когда Кэли ввел понятие абстрактной группы , не сразу стало ясно, является ли это большим набором объектов, чем известные группы перестановок (которые имели определение, отличное от современного). Кэли продолжил доказывать, что эти два понятия эквивалентны в теореме Кэли. ^[21]

Другим классическим текстом, содержащим несколько глав о группах перестановок, является « Теория групп конечного порядка» Бернсайда 1911 года. ^[22] Первая половина двадцатого века была периодом застоя в изучении теории групп в целом, но интерес к группам перестановок был возрожден в 1950-х годах Х. Виландтом, чьи немецкие лекции были переизданы под названием « Конечные группы перестановок» в 1964 году. ^[23]

Смотрите также

• 2-транзитивная группа
• Группа перестановок ранга 3
• Группа Матье

Примечания

1. Также используются обозначения S _M и S ^M.
2. Ротман 2006, стр. 148, Определение подгруппы
3. Ротман 2006, стр. 149, Предложение 2.69
4. Вуссинг, Ганс (2007), Генезис концепции абстрактной группы: вклад в историю происхождения абстрактной теории групп, Courier Dover Publications, стр. 94, ISBN 9780486458687В 1815 году Коши впервые использовал свою систему обозначений перестановок, в которой последовательности записываются одна под другой и обе заключаются в скобки.
5. особенно когда интерес представляют алгебраические свойства перестановки.
6. Биггс, Норман Л.; Уайт, AT (1979). Группы перестановок и комбинаторные структуры . Cambridge University Press. ISBN 0-521-22287-7.
7. Ротман 2006, стр. 107 – обратите особое внимание на сноску на этой странице.
8. Dixon & Mortimer 1996, стр. 3 – см. комментарий после примера 1.2.2
9. Кэмерон, Питер Дж. (1999). Группы перестановок . Cambridge University Press. ISBN 0-521-65302-9.
10. Джеррум, М. (1986). «Компактное представление групп перестановок». J. Algorithms . 7 (1): 60–78. doi :10.1016/0196-6774(86)90038-6.
11. Ротман 2006, стр. 108
12. Диксон и Мортимер 1996, стр. 5
13. Артин 1991, стр. 177
14. Диксон и Мортимер 1996, стр. 17
15. Диксон и Мортимер 1996, стр. 18
16. Кэмерон 1994, стр. 228
17. Кэмерон, Питер Дж. (1990). Олигоморфные группы подстановок . Серия заметок лекций Лондонского математического общества. Том 152. Кембридж: Издательство Кембриджского университета . ISBN 0-521-38836-8. Збл  0813.20002.
18. Олигоморфные группы перестановок - Препринт Института Исаака Ньютона, Питер Дж. Кэмерон
19. Бхаттачарджи, Минакси; Макферсон, Дугалд; Мёллер, Рёгнвалдур Г.; Нойманн, Питер М. (1998). Заметки о бесконечных группах перестановок . Lecture Notes in Mathematics. Vol. 1698. Berlin: Springer-Verlag . p. 83. ISBN 3-540-64965-4. Збл  0916.20002.
20. Диксон и Мортимер 1996, стр. 28
21. Кэмерон 1994, стр. 226
22. Бернсайд, Уильям (1955) [1911], Теория групп конечного порядка (2-е изд.), Дувр
23. Виландт, Х. (1964), Конечные группы перестановок , Academic Press

Ссылки

• Артин, Майкл (1991), Алгебра , Прентис-Холл, ISBN 0-13-004763-5
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы , Cambridge University Press, ISBN 0-521-45761-0
• Диксон, Джон Д.; Мортимер, Брайан (1996), Группы перестановок , Graduate Texts in Mathematics 163), Springer-Verlag, ISBN 0-387-94599-7
• Ротман, Джозеф Дж. (2006), Первый курс абстрактной алгебры с приложениями (3-е изд.), Pearson Prentice-Hall, ISBN 0-13-186267-7

Дальнейшее чтение

• Акош Сересс. Алгоритмы групп перестановок . Cambridge Tracts in Mathematics, 152. Cambridge University Press, Кембридж, 2003.
• Минакси Бхаттачарджи, Дугалд Макферсон, Рёгнвалдур Г. Мёллер и Питер М. Нойман. Заметки о бесконечных группах перестановок . Номер 1698 в Lecture Notes in Mathematics. Springer-Verlag, 1998.
• Питер Дж. Кэмерон . Группы перестановок . Текст LMS для студентов 45. Cambridge University Press, Кембридж, 1999.
• Питер Дж. Кэмерон. Олигоморфные группы перестановок . Cambridge University Press, Кембридж, 1990.

Внешние ссылки

• «Группа перестановок», Энциклопедия математики , EMS Press , 2001 [1994]
• Александр Хулпке. Библиотека данных GAP «Транзитивные группы перестановок».