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

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

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

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

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

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

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

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

Обозначения

Основная статья: Перестановка § Обозначения

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

$\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} можно записать как

$\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 не обязательно должны появляться ни в одном особый порядок в первой строке, поэтому ту же перестановку можно записать как

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

Перестановки также часто записываются в циклической записи ( циклическая форма ). так что для данного набора 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). Перестановка, записанная выше в двухстрочной записи, будет записана в циклической записи как $\sigma =(125)(34).$

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

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

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

$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 :

$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}}.$

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

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

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

Нейтральный элемент и инверсии

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

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

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

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

${\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}}.$

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

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

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

$[(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). Эта группа перестановок известна как абстрактная группа, как группа диэдра восьмого порядка.

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

Основная статья: Групповое действие (математика)

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

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

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

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

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

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

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

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

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

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

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

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

Теорема Кэли

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

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

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

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

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

ж _б ↦ ( eb )( и )

ж _c ↦ ( ec )( ab ).

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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

См. также

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

Ссылки

• Артин, Майкл (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 «Транзитивные группы перестановок» .