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

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

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

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

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

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

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

sgn( σ ) = (−1) ^{N ( σ )}

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

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

sgn( σ ) = (−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]

Кроме того, мы видим, что четные перестановки образуют подгруппу S _n . ^[1] Это знакопеременная группа из n букв, обозначаемая A _n . ^[3] Это ядро ​​гомоморфизма sgn . ^[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{ or }}(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}}$   если ${\displaystyle |i-j|\geq 2.}$

[Здесь генератор представляет транспозицию ( i , i + 1) .] Все отношения сохраняют длину слова неизменной или изменяют ее на два. Таким образом, начало со слова четной длины всегда приведет к слову четной длины после использования отношений, и аналогично для слов нечетной длины. Поэтому однозначно можно назвать элементы S _n , представленные словами четной длины, «четными», а элементы, представленные словами нечетной длины, «нечетными». ${\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 поменять местами, эти v _i инверсии с i исчезнут, но n − v _i инверсий будут образованы. Таким образом, число полученных инверсий i равно n − 2 v _i , что имеет ту же четность, что и n .

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

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

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

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

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

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

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

Четность перестановки точек также закодирована в ее циклической структуре . ${\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. Из разложения на 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. Jacobson (2009), стр. 51.
4. Гудман, стр. 116, определение 2.4.21
5. Мейер и Бауэр (2004), стр. 72

Ссылки

• Вайсштейн, Эрик В. «Четная перестановка». Математический мир .
• Якобсон, Натан (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.