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

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

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

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

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

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

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

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

sgn ( σ) = (−1) ^м

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

СОДЕРЖАНИЕ

• 1 Пример
• 2 свойства
• 3 Эквивалентность двух определений
• 4 Другие определения и доказательства
• 5 Обобщения
• 6 См. Также
• 7 Примечания
• 8 ссылки

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ 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 4 показывает, что в общем случае обратное неверно.

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

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

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

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

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

σ = Т 1 Т 2... Т к

Мы хотим показать, что четность 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 1  ...  T k выше, мы получим новое разложение:

σ = А 1 А 2... А м

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

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

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

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

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

${\ displaystyle P (x_ {1}, \ ldots, x_ {n}) = \ prod _ {i lt;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 (х _ {\ sigma (1)}, \ точки, x _ {\ sigma (n)})}$${\ Displaystyle P (x_ {1}, \ dots, x_ {n})}$

${\ displaystyle {\ begin {align} \ operatorname {sgn} (\ sigma \ tau) amp; = {\ frac {P (x _ {\ sigma (\ tau (1))}, \ ldots, x _ {\ sigma (\ tau (n))})} {P (x_ {1}, \ ldots, x_ {n})}} \\ [4pt] amp; = {\ 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] amp; = \ operatorname {sgn} (\ sigma) \ cdot \ operatorname {sgn} (\ tau). \ end {align}}}$

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

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

• ${\ Displaystyle \ тау _ {я} ^ {2} = 1}$  для всех я
• ${\ Displaystyle \ тау _ {я} ^ {} \ тау _ {я + 1} \ тау _ {я} = \ тау _ {я + 1} \ тау _ {я} \ тау _ {я + 1}}$   для всех i lt; n  - 1
• ${\ Displaystyle \ тау _ {я} ^ {} \ тау _ {j} = \ тау _ {j} \ тау _ {я}}$   если

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

Напомним, что пара x, y такая, что x lt; y и σ ( x)gt; σ ( 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. Количество инверсий я получил, таким образом, п - 2 v я, который имеет ту же четность, п.

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

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

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

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

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

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

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

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

${\ Displaystyle (а \ б \ с \ точки х \ у \ z) = (а \ б) (б \ с) \ точек (х \ у) (у \ г),}$

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

${\ displaystyle n {\ text {минус количество непересекающихся циклов в разложении}} \ 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 1 t 2... t r - произвольное разложение перестановки σ на транспозиции, применяя r транспозиций после t 2 после... после 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.