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

В математика, а группа перестановок это группа грамм чьи элементы перестановки данного набор M и чей групповая операция это композиция перестановок в грамм (которые считаются биективные функции из набора M себе). Группа все перестановки набора M это симметричная группа из M, часто пишется как Sym (M).^[1] Период, термин группа перестановок таким образом означает подгруппа симметрической группы. Если M = {1,2,...,п} тогда Sym (M), симметрическая группа из n букв обычно обозначается S_п.

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

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

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

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

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

В степень группы перестановок конечный набор это количество элементов в комплекте. В порядок группы (любого типа) - это количество элементов (мощность) в группе. К Теорема Лагранжа, порядок любой конечной группы подстановок степени п должен разделить п! поскольку п-факториал порядок симметрической группы S_п.

Обозначение

Основная статья: Перестановка § Определение и использование

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

${displaystyle sigma ={egin{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 ={egin{pmatrix}1&2&3&4&52&5&4&3&1end{pmatrix}};}$

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

${displaystyle sigma ={egin{pmatrix}3&2&5&1&44&5&1&2&3end{pmatrix}}.}$

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

Состав перестановок - групповой продукт

Основная статья: Перестановка § Перестановки в теории групп

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

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

${displaystyle P={egin{pmatrix}1&2&3&4&52&4&1&3&5end{pmatrix}}quad { ext{ and }}quad Q={egin{pmatrix}1&2&3&4&55&4&3&2&1end{pmatrix}},}$

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

${displaystyle QP={egin{pmatrix}1&2&3&4&55&4&3&2&1end{pmatrix}}{egin{pmatrix}1&2&3&4&52&4&1&3&5end{pmatrix}}={egin{pmatrix}2&4&1&3&54&2&5&3&1end{pmatrix}}{egin{pmatrix}1&2&3&4&52&4&1&3&5end{pmatrix}}={egin{pmatrix}1&2&3&4&54&2&5&3&1end{pmatrix}}.}$

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

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

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

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

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

${displaystyle {egin{pmatrix}1&2&3&cdots &n1&2&3&cdots &nend{pmatrix}}.}$

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

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

${displaystyle {egin{pmatrix}1&2&3&4&52&5&4&3&1end{pmatrix}}^{-1}={egin{pmatrix}2&5&4&3&11&2&3&4&5end{pmatrix}}={egin{pmatrix}1&2&3&4&55&1&4&3&2end{pmatrix}}.}$

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

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

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

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

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

Примеры

Рассмотрим следующий набор грамм₁ перестановок множества 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 и исправил остальные.
• ab = (1 2)(3 4)
  • Эта перестановка, которая является композицией двух предыдущих, меняет одновременно 1 на 2 и 3 на 4.

грамм₁ образует группу, поскольку аа = bb = е, ба = ab, и Abab = е. Эта группа перестановок изоморфный, как абстрактная группа, к Кляйн группа 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]

Позволять грамм быть группа и M непустой набор. An действие из грамм на M это функция ж: грамм × M → M такой, что

• ж(1, Икс) = Икс, для всех Икс в M (1 - это личность (нейтральный) элемент группы грамм), и
• ж(грамм, ж(час, Икс)) = ж(gh, Икс), для всех грамм,час в грамм и все Икс в M.

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

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

Элемент группы	Действия на треугольниках	Действия по диагоналям
(1)	(1)	(1)
(1234)	(т1 т2 т3 т4)	(d1 d2)
(13)(24)	(т1 т3)(т2 т4)	(1)
(1432)	(т1 т4 т3 т2)	(d1 d2)
(12)(34)	(т1 т2)(т3 т4)	(d1 d2)
(14)(23)	(т1 т4)(т2 т3)	(d1 d2)
(13)	(т1 т3)	(1)
(24)	(т2 т4)	(1)

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

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

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

Основная статья: Примитивная группа перестановок

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

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

Теорема Кэли

Основная статья: Теорема Кэли

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

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

ж_е ↦ (е)(а)(б)(c)

ж_а ↦ (еа)(до н.э)

ж_б ↦ (eb)(ac)

ж_c ↦ (ec)(ab).

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

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

λ(ж₁(грамм, Икс)) = ж₂(ψ(грамм), λ(Икс)) для всех грамм в грамм и Икс в Икс.^[14]

Если Икс = Y это эквивалентно грамм и ЧАС сопряжены как подгруппы в Sym (Икс).^[15] Частный случай, когда грамм = ЧАС и ψ это карта идентичности дает начало концепции эквивалентные действия группы.^[16]

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

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

Когда группа грамм действует на набор S, действие можно естественным образом распространить на Декартово произведение S^п из S, состоящий из п-наборы элементов S: действие элемента грамм на п-температура (s₁, ..., s_п) дан кем-то

грамм(s₁, ..., s_п) = (грамм(s₁), ..., грамм(s_п)).

Группа грамм как говорят олигоморфный если действие на S^п имеет только конечное число орбит для каждого положительного целого числа п.^[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. Биггс, Норман Л .; Уайт, А. Т. (1979). Группы перестановок и комбинаторные структуры. Издательство Кембриджского университета. ISBN  0-521-22287-7.
7. Ротман 2006, п. 107 - обратите внимание на сноску на этой странице.
8. Диксон и Мортимер 1996, п. 3 - см. Комментарий к примеру 1.2.2.
9. Кэмерон, Питер Дж. (1999). Группы перестановок. Издательство Кембриджского университета. ISBN  0-521-65302-9.
10. Джеррам, М. (1986). «Компактное представление групп подстановок». J. Алгоритмы. 7 (1): 60–78. Дои: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. Zbl  0813.20002.
18. Олигоморфные группы перестановок - Препринт Института Исаака Ньютона, Питер Дж. Кэмерон
19. Бхаттачарджи, Минакси; Макферсон, Дугальд; Möller, Rögnvaldur G .; Нойман, Питер М. (1998). Замечания о бесконечных группах перестановок. Конспект лекций по математике. 1698. Берлин: Springer-Verlag. п. 83. ISBN  3-540-64965-4. Zbl  0916.20002.
20. Диксон и Мортимер 1996, п. 28
21. Кэмерон 1994, п. 226
22. Бернсайд, Уильям (1955) [1911], Теория групп конечного порядка (2-е изд.), Дувр
23. Виландт, Х. (1964), Конечные группы перестановок, Academic Press

Рекомендации

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

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

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

внешняя ссылка

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