В математике , когда Х представляет собой конечное множество , по меньшей мере , из двух элементов, то перестановки из X (т.е. биективные функции от X к X ) делятся на два класса равного размера: в четные перестановки и нечетные перестановки . Если какое - либо общее упорядочение в X фиксирована, четности ( нечетности или ровность ) от перестановкииз X может быть определена как четность числа инверсий для сг , т.е. пар элементов х , у из X , таких , что х < у и σ ( х )> σ ( у ) .
Знак , подпись , или сигнум из перестановок сг обозначается 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. Это показывает, что данная перестановка σ нечетная. Следуя методу статьи с обозначениями цикла , это можно было бы записать слева направо как
Есть много других способов записать σ как композицию транспозиций, например
- σ = (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]
Цикл даже тогда и только тогда , когда его длина составляет нечетное. Это следует из формул вида
На практике, чтобы определить, является ли данная перестановка четной или нечетной, ее записывают как произведение непересекающихся циклов. Перестановка нечетная тогда и только тогда, когда эта факторизация содержит нечетное количество циклов четной длины.
Другой метод определения, является ли данная перестановка четной или нечетной, состоит в построении соответствующей матрицы перестановок и вычислении ее определителя. Значение определителя такое же, как четность перестановки.
Каждая перестановка нечетного порядка должна быть четной. Перестановка (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
Альтернативное доказательство использует полином Вандермонда
Так, например, в случае n = 3 мы имеем
Теперь для данной перестановки σ чисел {1, ..., n } определим
Поскольку многочлен имеет те же факторы, что и кроме их знаков, sgn ( σ ) равно +1 или −1. Кроме того, если σ и τ - две перестановки, мы видим, что
Поскольку из этого определения, кроме того, ясно, что любая транспозиция двух элементов имеет сигнатуру -1, мы действительно восстанавливаем сигнатуру, как определено ранее.
Доказательство 3
Третий подход использует представление группы S n в терминах образующих τ 1 , ..., τ n −1 и соотношений
- для всех я
- для всех i < n - 1
- если | i - j | ≥ 2.
[Здесь генератор представляет собой транспонирование ( i , i + 1) .] Все отношения сохраняют длину слова одинаковой или изменяют ее на два. Таким образом, начало со слова четной длины всегда будет приводить к слову четной длины после использования отношений, и аналогично для слов нечетной длины. Поэтому однозначно называть элементы S n, представленные словами четной длины, «четными», а элементы, представленные словами нечетной длины, «нечетными».
Доказательство 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 . Количество инверсий я получил, таким образом , п - 2 v я , который имеет ту же четность, п .
Точно так же количество полученных инверсий j также имеет ту же четность, что и n . Следовательно, количество инверсий, полученных обоими вместе, имеет ту же четность, что и 2 n или 0. Теперь, если мы посчитаем инверсии, полученные (или потерянные) заменой i- го и j- го элементов, мы увидим, что этот обмен изменяет четность количества инверсий, так как мы также добавляем (или вычитаем) 1 к количеству инверсий, полученных (или проигранных) для пары (i, j) . Обратите внимание, что изначально, когда своп не применяется, количество инверсий равно 0. Теперь мы получаем эквивалентность двух определений четности перестановки.
Другие определения и доказательства
Четность перестановки точки также закодированы в его структуре цикла .
Пусть σ = ( 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-циклов):
так называют K на размер цикла, и заметим , что, согласно этому определению, транспозиции циклы размера 1. Из разложения в м циклах непересекающихся можно получить разложение сг в K 1 + K 2 + ... + к m транспозиций, где k i - размер i- го цикла. Число N ( σ ) = k 1 + k 2 + ... + k m называется дискриминантом числа σ , и его также можно вычислить как
если мы позаботимся включить неподвижные точки σ как 1-циклы.
Предположим, что транспозиция ( a b ) применяется после перестановки σ . Когда a и b находятся в разных циклах σ, то
- ,
и если a и b находятся в одном цикле σ, то
- .
В любом случае видно, что N (( a b ) σ ) = N ( σ ) ± 1 , поэтому четность N (( a b ) σ ) будет отличаться от четности N ( σ ).
Если σ = t 1 t 2 ... t r - произвольное разложение перестановки σ на транспозиции, применяя r транспозицийпосле t 2 после ... после t r после тождества (у которого N равно нулю) заметим, что N ( σ ) и r имеют одинаковую четность. Определив четность σ как четность N ( σ ), перестановка, которая имеет разложение четной длины, является четной перестановкой, а перестановка, которая имеет одно разложение нечетной длины, является нечетной перестановкой.
Примечания:
- Тщательное рассмотрение приведенного выше аргумента показывает, что r ≥ N ( σ ) , и поскольку любое разложение σ на циклы, сумма размеров которых равна r, может быть выражено как композиция из r транспозиций, число N ( σ ) является минимально возможной суммой размеров циклов в разложении σ , включая случаи, когда все циклы являются транспозициями.
- Это доказательство не вводит (возможно, произвольного) порядка в множество точек, в которых действует σ .
Обобщения
Четность может быть обобщена на группы Кокстера : определяется функция длины ℓ ( v ), которая зависит от выбора образующих (для симметрической группы, смежных транспозиций ), а затем функция v ↦ (−1) ℓ ( v ) дает обобщенная карта знаков.
Смотрите также
- Пятнадцать головоломка представляет собой классическое приложение
- Лемма Золотарева
Заметки
- ^ a b c d Якобсон (2009), стр. 50.
- ^ Ротман (1995), стр. 9, теорема 1.6.
- ^ a b c Якобсон (2009), стр. 51.
- Перейти ↑ Goodman, p. 116, определение 2.4.21
- ^ Мейер & Bauer (2004), стр. 72
Рекомендации
- Вайсштейн, Эрик В. «Даже перестановка» . 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.