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

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

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

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

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

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

знак ( σ ) = (−1) ^{N ( σ )}

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

В качестве альтернативы знак перестановки  σ может быть определен из ее разложения на произведение транспозиций как

sgn ( σ ) = (−1) ^м

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

Пример [ править ]

Рассмотрим перестановку σ набора {1, 2, 3, 4, 5}, которая превращает исходное расположение 12345 в 34521. Его можно получить тремя транспозициями: сначала поменять местами числа 2 и 4, затем поменять местами 1 и 3 и наконец, поменять местами 1 и 5. Это показывает, что данная перестановка σ нечетная. Следуя методу статьи с обозначениями цикла , это можно было бы записать слева направо как

${\ 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} 1 & 5 \ end {pmatrix}} {\ begin {pmatrix} 2 & 4 \ end {pmatrix}}.}$

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

σ = (2 3) (1 2) (2 4) (3 4) (1 5) ,

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

Свойства [ править ]

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

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

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

Из этого следует, что

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

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

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

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

Кроме того, мы видим, что четные перестановки образуют подгруппу в S _n . ^[1] Это знакопеременная группа из n букв, обозначаемая A _n . ^[3] Это ядро гомоморфизма sign. ^[4] Нечетные перестановки не могут образовывать подгруппу, поскольку композиция двух нечетных перестановок четна, но они образуют смежный класс A _n (в S _n ). ^[5]

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

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

${\ Displaystyle (a \ b \ c \ d \ e) = (d \ e) (c \ e) (b \ e) (a \ e) {\ text {или}} (a \ b) (b \ c) (c \ d) (d \ e).}$

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

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

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

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

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

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

Доказательство 1 [ править ]

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

σ = Т ₁ Т ₂ ... Т _к

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

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

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

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

• Базовый случай 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})}}.}$

Поскольку многочлен имеет те же множители, что и за исключением их знаков, следует, что sgn ( σ ) равно +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}}$   для всех i < n  - 1
• ${\displaystyle \tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}}$   если | i  -  j | ≥ 2.

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

Доказательство 4 [ править ]

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

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

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

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

Пусть σ = ( i ₁ i ₂ ... i _{r +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. Из разложения в м циклах непересекающихся можно получить разложение сг в 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 )} дает обобщенная карта знаков.

См. Также [ править ]

• Пятнадцать головоломка представляет собой классическое приложение
• Лемма Золотарева

Заметки [ править ]

Ссылки [ править ]

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