Четность перестановки - Parity of a permutation

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

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

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

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

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

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

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

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

sgn (σ) = (−1)^м

куда м - количество транспозиций в разложении. Хотя такое разложение не является уникальным, четность числа транспозиций во всех разложениях одинакова, что означает, что знак перестановки равен четко определенный.^[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_п всех перестановок множества {1, ..., п}, можно сделать вывод, что отображение

sgn: S_п → {−1, 1} 

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

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

Если п > 1, то четных перестановок в S_п как бывают странные;^[3] следовательно, A_п содержит п! / 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) в₄ показывает, что в общем случае обратное неверно.

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

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

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

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

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

σ = Т₁ Т₂ ... Т_k

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

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

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

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

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

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

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

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

где все А₁...А_м смежные. Кроме того, паритет м такой же, как у k.

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

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

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

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

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

${ Displaystyle P (x_ {1}, ldots, x_ {n}) = prod _ {i$

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

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

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

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

Поскольку многочлен ${ Displaystyle P (х _ { sigma (1)}, точки, x _ { sigma (n)})}$ имеет те же факторы, что и ${ Displaystyle P (x_ {1}, dots, x_ {n})}$ кроме их знаков, если следует, что sgn (σ) равно +1 или -1. Кроме того, если σ и τ две перестановки, мы видим, что

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

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

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

Третий подход использует презентация группы S_п с точки зрения генераторов τ₁, ..., τ_п−1 и отношения

• ${ Displaystyle тау _ {я} ^ {2} = 1}$ для всех я
• ${ Displaystyle тау _ {я} ^ {} тау _ {я + 1} тау _ {я} = тау _ {я + 1} тау _ {я} тау _ {я + 1}}$ для всех я < п − 1
• ${ Displaystyle тау _ {я} ^ {} тау _ {j} = тау _ {j} тау _ {я}}$ если |я − j| ≥ 2.

[Здесь генератор ${ Displaystyle тау _ {я}}$ представляет собой перестановку (я, я + 1).] Все отношения сохраняют длину слова одинаковой или изменяют ее на два. Таким образом, начало со слова четной длины всегда будет приводить к слову четной длины после использования отношений, и аналогично для слов нечетной длины. Поэтому однозначно называть элементы S_п представлены словами четной длины "even", а элементы представлены словами нечетной длины "odd".

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

Напомним, что пара Икс, у такой, что Икс < у и σ(Икс) > σ(у) называется инверсией. Мы хотим показать, что количество инверсий имеет ту же четность, что и количество двухэлементных свопов. Для этого мы можем показать, что каждый обмен изменяет четность подсчета инверсий, независимо от того, какие два элемента меняются местами и какая перестановка уже была применена. Предположим, мы хотим поменять местами яй и jй элемент. Ясно, что инверсии, образованные я или же j с элементом вне [я, j] не пострадает. Для п = j − я − 1 элементы в интервале (я, j), предполагать v_я из них образуют инверсии с я и v_j из них образуют инверсии с j. Если я и j поменяны местами, те v_я инверсии с я ушли, но п − v_я образуются инверсии. Счетчик инверсий я получено таким образом п − 2v_я, имеющая ту же четность, что и п.

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

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

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

Позволять σ = (я₁ я₂ ... я_р+1)(j₁ j₂ ... j_s+1)...(ℓ₁ ℓ₂ ... ℓ_ты+1) быть уникальным разложение σ на непересекающиеся циклы, которые могут быть составлены в любом порядке, потому что они коммутируют. Цикл (а б c ... Икс у z) с участием k + 1 баллы всегда можно получить, составив k транспозиции (2 цикла):

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

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

${ displaystyle n { text {минус количество непересекающихся циклов в разложении}} sigma}$

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

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

${ 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})}$,

и если а и б находятся в одном цикле σ тогда

${ 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((а б)σ) = N(σ) ± 1, поэтому четность N((а б)σ) будет отличаться от четности N(σ).

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

Примечания:

• Тщательное изучение приведенного выше аргумента показывает, что р ≥ N(σ), а поскольку любое разложение σ на циклы, сумма которых составляет р можно выразить как композицию р транспозиции, число 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.