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

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

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

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

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

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

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

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

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

Обозначения

Поскольку перестановки являются биекциями множества, они могут быть представлены двухстрочной нотацией Коши . ^[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). Перестановка, записанная выше в двухстрочной записи, будет записана в циклической записи как ${\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). Эта группа перестановок известна как абстрактная группа, как группа диэдра восьмого порядка.

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

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

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

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

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

Для любой группы перестановок действие, которое отправляет ( g , x ) → g ( x ) , называется естественным действием G на M. Это действие предполагается, если не указано иное. ^[12] В примере группы симметрии квадрата действие группы на множество вершин является естественным действием. Однако эта группа также индуцирует действие на множество четырех треугольников в квадрате, а именно: t ₁ = 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 функция fg ( x ) = _gx является биекцией на G и, следовательно , перестановкой множества элементов G. Таким образом , каждый элемент G можно рассматривать как перестановку, и поэтому G изоморфен группе перестановок; в этом состоит содержание теоремы Кэли .

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

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

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

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

ж _c ↦ ( ec )( ab ).

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

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

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

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

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

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

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

грамм ( s ₁ , ..., s _n ) знак равно ( грамм ( s ₁ ), ..., грамм ( s _n )).

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

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

История

Изучение групп первоначально выросло из понимания групп перестановок. ^{[20] Сами} перестановки интенсивно изучались Лагранжем в 1770 году в его работе над алгебраическими решениями полиномиальных уравнений. Этот предмет процветал, и к середине 19 века существовала хорошо разработанная теория групп перестановок, систематизированная Камиллом Джорданом в его книге « Трактат о подстановках и алгебраических уравнениях» 1870 года. Книга Джордана, в свою очередь, была основана на оставшихся статьях. Эвариста Галуа в 1832 году.

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

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

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

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

Примечания

1. Также ^{используются} обозначения SM и SM _.
2. Ротман 2006, с. 148, Определение подгруппы
3. Ротман 2006, с. 149, предложение 2.69.
4. Вуссинг, Ганс (2007), Генезис концепции абстрактной группы: вклад в историю происхождения абстрактной теории групп, Courier Dover Publications, стр. 94, ISBN 9780486458687Коши впервые использовал свою нотацию перестановок, в которой аранжировки пишутся одна под другой и обе заключаются в круглые скобки, в 1815 году.
5. особенно, когда интерес представляют алгебраические свойства перестановки.
6. Биггс, Норман Л.; Уайт, AT (1979). Группы перестановок и комбинаторные структуры . Издательство Кембриджского университета. ISBN 0-521-22287-7.
7. Ротман 2006, с. 107 – обратите особое внимание на сноску на этой странице.
8. Диксон и Мортимер 1996, стр. 3 – см. комментарий к примеру 1.2.2.
9. Кэмерон, Питер Дж. (1999). Группы перестановок . Издательство Кембриджского университета. ISBN 0-521-65302-9.
10. Джеррам, М. (1986). «Компактное представление групп перестановок». Дж. Алгоритмы . 7 (1): 60–78. дои : 10.1016/0196-6774(86)90038-6.
11. Ротман 2006, с. 108
12. Dixon & Mortimer 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). Замечания о бесконечных группах перестановок . Конспект лекций по математике. Том. 1698. Берлин: Springer-Verlag . п. 83. ИСБН 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), Комбинаторика: темы, методы, алгоритмы , издательство Кембриджского университета, ISBN 0-521-45761-0
• Диксон, Джон Д.; Мортимер, Брайан (1996), Группы перестановок , Тексты для выпускников по математике 163), Springer-Verlag, ISBN 0-387-94599-7
• Ротман, Джозеф Дж. (2006), Первый курс абстрактной алгебры с приложениями (3-е изд.), Пирсон Прентис-Холл, ISBN 0-13-186267-7

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

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

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

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