Четность перестановки

Свойство в теории групп

Перестановки из 4 элементов.

Нечетные перестановки имеют зеленый или оранжевый фон. Числа в правом столбце — это числа инверсий (последовательность A034968 в OEIS ), которые имеют ту же четность , что и перестановка.

В математике , когда X — конечное множество , состоящее как минимум из двух элементов, перестановки X ( т.е. биективные функции от X до X ) делятся на два класса одинакового размера: четные перестановки и нечетные перестановки . Если какой-либо общий порядок X фиксирован, четность ( нечетность или четность ) перестановки X может быть определена как четность количества инверсий для  σ , т. е. пар элементов x ,  y из X таких, что x < y и σ ( Икс ) > σ ( y ) . ${\displaystyle \sigma }$

Знак , сигнатура или сигнум перестановки  σ обозначается sn( σ ) и определяется как +1, если σ четное, и -1, если σ нечетное . Сигнатура определяет знакопеременный характер симметрической группы Sn _. Другое обозначение знака перестановки дается более общим символом Леви-Чивита ( ε _σ ), который определен для всех карт от X до X и имеет нулевое значение для небиективных карт .

Знак перестановки можно явно выразить как

знак( σ ) знак равно (−1) ^{N ( σ )}

где N ( σ ) — количество инверсий в  σ .

Альтернативно, знак перестановки  σ можно определить путем ее разложения на произведение транспозиций как

знак( σ ) = (−1) ^м

где m — количество транспозиций в разложении. Хотя такое разложение не уникально, четность числа транспозиций во всех разложениях одинакова, а это означает, что знак перестановки четко определен . ^[1]

Пример

Рассмотрим перестановку σ набора {1, 2, 3, 4, 5}, определенную как и В однострочном обозначении эта перестановка обозначается 34521. Ее можно получить из тождественной перестановки 12345 тремя транспозициями: сначала поменяйте местами числа 2 и 4, затем поменяйте местами 3 и 5 и, наконец, поменяйте местами 1 и 3. Это показывает, что данная перестановка σ нечетна. Следуя методу статьи с циклической записью , это можно было бы записать, складывая справа налево, как ${\displaystyle \sigma (1)=3,}$ ${\displaystyle \sigma (2)=4,}$ ${\displaystyle \sigma (3)=5,}$ ${\displaystyle \sigma (4)=2,}$ ${\displaystyle \sigma (5)=1.}$

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

Есть много других способов записи σ как композиции транспозиций, например

σ знак равно (1 5)(3 4)(2 4)(1 2)(2 3) ,

но невозможно записать его в виде произведения четного числа транспозиций.

Характеристики

Тождественная перестановка является четной перестановкой. ^[1] Четная перестановка может быть получена как композиция четного числа (и только четного числа) обменов (называемых транспозициями ) двух элементов, тогда как нечетная перестановка может быть получена (только) нечетным числом транспозиций.

Следующие правила следуют непосредственно из соответствующих правил сложения целых чисел: ^[1]

• композиция двух четных перестановок четна
• композиция двух нечетных перестановок четна
• композиция нечетной и четной перестановки нечетна

Из них следует, что

• обратная каждой четной перестановке четна
• обратная каждой нечетной перестановке нечетна

Рассматривая симметрическую группу S _n всех перестановок множества {1, ..., n }, можно заключить, что отображение

знак: S _n → {−1, 1} 

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

_{Более того, мы видим ,} что четные перестановки образуют подгруппу Sn . ^[1] Это чередующаяся группа из n букв, обозначаемая _An . ^[3] Это ядро ​​гомоморфизма Sign. ^[4] Нечетные перестановки не могут образовывать подгруппу, поскольку композиция двух нечетных перестановок четна, но они образуют смежный _класс An ( в Sn ₎ . ^[5]

Если n > 1 , то в _Sn столько же четных перестановок, сколько и нечетных; ^[3] следовательно, _An содержит n ! /2 перестановки. (Причина в том, что если σ четно, то (1 2) σ нечетно, а если σ нечетно, то (1 2) σ четно, и эти два отображения обратны друг другу.) ^[3]

Цикл четен тогда и только тогда , когда его длина нечетна. Это следует из формул типа

${\displaystyle (a\ b\ c\ d\ e)=(d\ e)(c\ e)(b\ e)(a\ e){\text{ or }}(a\ b)(b\ c)(c\ d)(d\ e).}$

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

Другой метод определения того, является ли данная перестановка четной или нечетной, заключается в построении соответствующей матрицы перестановок и вычислении ее определителя. Значение определителя такое же, как и четность перестановки.

Любая перестановка нечетного порядка должна быть четной. Перестановка (1 2)(3 4) в A ₄ показывает, что обратное, вообще говоря, неверно.

Эквивалентность двух определений

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

• как четность числа инверсий в σ (при любом порядке); или
• как четность числа транспозиций, на которые можно разложить σ (как бы мы ни решили его разложить).

Доказательство 1

Пусть σ — перестановка в ранговой области S. Любую перестановку можно произвести с помощью последовательности транспозиций (двухэлементных обменов). Пусть следующее будет одним из таких разложений

σ = Т ₁ Т ₂ ... Т _k

Мы хотим показать, что четность k равна четности числа инверсий σ .

Каждую транспозицию можно записать как произведение нечетного числа транспозиций соседних элементов, например

(2 5) = (2 3) (3 4) (4 5) (4 3) (3 2).

Как правило, мы можем записать транспозицию ( i  i+d ) на множестве {1,..., i ,..., i+d ,...} как композицию 2 d −1 соседних транспозиций путем рекурсии на д :

• Базовый случай d=1 тривиален.

• В рекурсивном случае сначала перепишите ( i , i+d ) как ( i , i +1) ( i +1, i+d ) ( i , i +1). Затем рекурсивно перепишите ( i +1, i+d ) как смежные транспозиции.

Если мы разложим таким образом каждую из транспозиций T ₁  ...  T _k , приведенных выше, мы получим новое разложение:

σ = А ₁ А ₂ ... А _м

где все A ₁ ... A _m смежны. Кроме того, четность m такая же, как и у k .

Это факт: для всех перестановок τ и смежных транспозиций a, aτ либо имеет на одну инверсию меньше, либо на одну больше, чем τ . Другими словами, четность количества инверсий перестановки переключается при ее составлении с соседней транспозицией.

Следовательно, четность числа инверсий σ — это в точности четность m , которая также является четностью k . Именно это мы и намеревались доказать.

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

Доказательство 2

Альтернативное доказательство использует полином Вандермонда.

${\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{i<j}(x_{i}-x_{j}).}$

Так, например, в случае n = 3 мы имеем

${\displaystyle P(x_{1},x_{2},x_{3})=(x_{1}-x_{2})(x_{2}-x_{3})(x_{1}-x_{3}).}$

Теперь для данной перестановки  σ чисел {1, ...,  n } мы определяем

${\displaystyle \operatorname {sgn}(\sigma )={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}.}$

Поскольку многочлен имеет те же множители, за исключением знаков, отсюда следует, что sn( σ ) равен либо +1, либо −1. Более того, если σ и τ — две перестановки, мы видим, что ${\displaystyle P(x_{\sigma (1)},\dots ,x_{\sigma (n)})}$ ${\displaystyle P(x_{1},\dots ,x_{n})}$

${\displaystyle {\begin{aligned}\operatorname {sgn}(\sigma \tau )&={\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{1},\ldots ,x_{n})}}\\[4pt]&={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}\cdot {\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}}\\[4pt]&=\operatorname {sgn}(\sigma )\cdot \operatorname {sgn}(\tau ).\end{aligned}}}$

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

Доказательство 3

Третий подход использует представление группы S _n в терминах образующих τ ₁ , ..., τ _{n −1} и соотношений

• ${\displaystyle \tau _{i}^{2}=1}$  для всех я
• ${\displaystyle \tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}}$   для всех я < n  - 1
• ${\displaystyle \tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}}$   если ${\displaystyle |i-j|\geq 2.}$

[Здесь генератор представляет транспозицию ( i , i + 1) .] Все отношения сохраняют длину слова одинаковой или изменяют ее на два. Таким образом, если начать со слова четной длины, после использования отношений всегда будет получено слово четной длины, и аналогично для слов нечетной длины. Поэтому элементы Sn, представленные словами четной длины, однозначно называть _« четными», а элементы, представленные словами нечетной длины, «нечетными». ${\displaystyle \tau _{i}}$

Доказательство 4

Напомним, что пара x , y такая, что x < y и σ ( x ) > σ ( y ), называется инверсией. Мы хотим показать, что количество инверсий имеет ту же четность, что и количество 2-элементных свопов. Для этого мы можем показать, что каждая замена меняет четность счетчика инверсий, независимо от того, какие два элемента заменяются местами и какая перестановка уже была применена. Предположим, мы хотим поменять местами i- й и j- й элементы. Очевидно, что инверсии, образованные i или j с элементом вне [ i , j ], не будут затронуты. Для n = j − i − 1 элементов в интервале ( i , j ) предположим, что v _i из них образуют инверсии с i, а v _j из них образуют инверсии с j . Если i и j поменять местами, _{инверсии} vi с i исчезнут, но образуются инверсии _n − vi . Таким образом , количество полученных инверсий i равно n − 2 v _i , что имеет ту же четность, что и n .

Аналогично, количество полученных инверсий j также имеет ту же четность, что и n . Следовательно, количество инверсий, полученных обоими вместе, имеет ту же четность, что и 2 n или 0. Теперь, если мы подсчитаем инверсии, полученные (или потерянные) путем замены i - го и j -го элементов, мы увидим, что эта замена меняет четность количества инверсий, поскольку мы также добавляем (или вычитаем) 1 к количеству полученных (или потерянных) инверсий для пары (i,j) .

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

Доказательство 5

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

Элемент, который находится либо полностью выше, либо полностью ниже, не вносит никакого вклада в счетчик инверсии при применении транспонирования. Промежуточные элементы вносят свой вклад . ${\displaystyle 2}$

Поскольку сама транспозиция обеспечивает инверсию, а все остальные обеспечивают инверсию 0 (по модулю 2), транспозиция изменяет четность количества инверсий. ${\displaystyle \pm 1}$

Другие определения и доказательства

Четность перестановки точек также закодирована в ее циклической структуре . ${\displaystyle n}$

Пусть σ = ( я ₁ я ₂ ... я _{р +1} )( j ₁ j ₂ ... j _{s +1} )... ( ℓ ₁ ℓ ₂ ... ℓ _{u +1} ) будет уникальным разложением σ на непересекающиеся циклы , которые можно составлять в любом порядке, поскольку они коммутируют. Цикл ( a b c ... x y z ) , включающий k + 1 точку, всегда можно получить составлением k транспозиций (2-циклов):

${\displaystyle (a\ b\ c\dots x\ y\ z)=(a\ b)(b\ c)\dots (x\ y)(y\ z),}$

поэтому назовем k размером цикла и заметим, что согласно этому определению транспозиции представляют собой циклы размера 1. Из разложения на m непересекающихся циклов мы можем получить разложение σ на k ₁ + k ₂ + ... + k _m транспозиций, где k _i — размер i- го цикла. Число N ( σ ) = k ₁ + k ₂ + ... + k _m называется дискриминантом σ и также может быть вычислено как

${\displaystyle n{\text{ minus the number of disjoint cycles in the decomposition of }}\sigma }$

если мы позаботимся о том, чтобы включить неподвижные точки σ как 1-циклы.

Предположим, что транспозиция ( a b ) применяется после перестановки σ . Когда a и b находятся в разных циклах σ , тогда

${\displaystyle (a\ b)(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})}$,

и если a и b находятся в одном цикле σ , то

${\displaystyle (a\ b)(ac_{1}c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})}$.

В любом случае можно видеть, что N (( a b ) σ ) = N ( σ ) ± 1 , поэтому четность N (( a b ) σ ) будет отличаться от четности N ( σ ).

Если σ = t ₁ t ₂ ... t _r — произвольное разложение перестановки σ на транспозиции, применяя r транспозиции после t ₂ после ... после t _r после тождества (чье N равно нулю) заметите, что N ( σ ) и r имеют одинаковую четность. Определив четность σ как четность N ( σ ), перестановка, имеющая разложение четной длины, является четной перестановкой, а перестановка, имеющая одно разложение нечетной длины, является нечетной перестановкой. ${\displaystyle t_{1}}$

Примечания

• Тщательное рассмотрение приведенного выше аргумента показывает, что r ≥ N ( σ ) , и поскольку любое разложение σ на циклы, сумма размеров которых равна r, может быть выражена как композиция r транспозиций, число N ( σ ) является минимально возможной суммой размеров циклов в разложении σ , включая случаи, когда все циклы являются транспозициями.
• Это доказательство не вводит (возможно, произвольного) порядка в множество точек, на которых действует σ .

Обобщения

Четность может быть обобщена на группы Кокстера : определяется функция длины ℓ( v ), которая зависит от выбора образующих (для симметричной группы — смежные транспозиции ), а затем функция v ↦ (−1) ^{ℓ( v )} дает обобщенная карта знаков.

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

• Головоломка «Пятнадцать» — классическое приложение.
• Лемма Золотарева

Примечания

1. Джейкобсон (2009), с. 50.
2. Ротман (1995), с. 9, теорема 1.6.
3. Джейкобсон (2009), с. 51.
4. Гудман, с. 116, определение 2.4.21
5. Мейер и Бауэр (2004), с. 72

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

• Вайсштейн, Эрик В. «Четная перестановка». Математический мир .
• Джейкобсон, Натан (2009). Базовая алгебра . Том. 1 (2-е изд.). Дувр. ISBN 978-0-486-47189-1.
• Ротман, Джей Джей (1995). Введение в теорию групп . Дипломные тексты по математике. Спрингер-Верлаг. ISBN 978-0-387-94285-8.
• Гудман, Фредерик М. Алгебра: абстрактное и конкретное . ISBN 978-0-9799142-0-1.
• Мейер, Пауль Герман Эрнст; Бауэр, Эдмонд (2004). Теория групп: приложение к квантовой механике . Дуврская классика науки и математики. Дуврские публикации. ISBN 978-0-486-43798-9.