Jump to content

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

(Перенаправлено из групп перестановок )

В математике группа перестановок — это группа 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 в первой строке, а также для каждого элемента его изображение под перестановкой под ним во второй строке. Если является перестановкой множества затем,

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

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

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

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

[ редактировать ]

Произведение двух перестановок определяется как их композиция как функции, поэтому это функция, которая отображает любой элемент x набора в . Обратите внимание, что самая правая перестановка сначала применяется к аргументу из-за способа написания композиции функции. [6] [7] Некоторые авторы предпочитают, чтобы первым действовал самый левый фактор, но для этого перестановки должны быть записаны справа от их аргумента, часто в виде верхнего индекса , поэтому перестановка действующий на элемент результаты на изображении . Согласно этому соглашению, произведение определяется выражением . [8] [9] [10] Однако это дает другое правило умножения перестановок. Это соглашение обычно используется в литературе по группам перестановок, но в этой статье используется соглашение, согласно которому сначала применяется самая правая перестановка.

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

продукт QP :

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

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

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

[ редактировать ]

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

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

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

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

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

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

Рассмотрим следующий набор G 1 перестановок множества 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 1 образует группу, поскольку aa = bb = e , ba = ab и abab = e . Эта группа перестановок, как абстрактная группа , является группой Клейна V 4 .

В качестве другого примера рассмотрим группу симметрий квадрата . Пусть вершины квадрата обозначены цифрами 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 .

Для любой группы перестановок действие, которое отправляет ( , x ) ( x ) , называется естественным действием G g на M. g Это действие предполагается, если не указано иное. [12] В примере группы симметрии квадрата действие группы на множестве вершин является естественным действием. Однако эта группа также индуцирует действие на множество четырех треугольников в квадрате, а именно: t 1 = 234, t 2 = 134, t 3 = 124 и t 4 = 123. Она также действует на две диагонали: d 1 = 13 и d 2 = 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 . [13] примеров Из приведенных выше группа {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 , действующую на множестве {1, 2, 3, 4}, данном выше. Обозначим элементы этой группы через e , a , b и c = ab = ba . Действие G 1 на себя, описанное в теореме Кэли, дает следующее представление перестановок:

ж е ↦ ( е )( а )( б )( c )
ж а ↦ ( из )( до н.э. )
ж б ↦ ( eb )( и )
ж c ↦ ( ec )( ab ).

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

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

грамм ( s 1 , ..., s n ) знак равно ( грамм ( s 1 ), ..., грамм ( s n )).

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

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

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

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

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Обозначения SM и S М также используются.
  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. ^ Перейти обратно: а б с Диксон и Мортимер 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.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: ef1ff2be48085e28795a3bd55b191965__1718725980
URL1:https://arc.ask3.ru/arc/aa/ef/65/ef1ff2be48085e28795a3bd55b191965.html
Заголовок, (Title) документа по адресу, URL1:
Permutation group - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)