Перестановки и транспозиции, определители

Совокупность чисел среди которых нет рав­ных и каждое из которых есть одно из чисел 1, 2, ..., п, назы­вается перестановкойэтих чисел. Перестановка 1, 2, ..., п. назы­вается нормальной.

В множестве из п чисел общее количество перестановок равно п!.

Говорят, что в данной перестановке числа i, j образуют инверсию, если i> j, но i стоит в перестановке раньше j.

Например, перестановка 15243. Числа 5, 2 образуют инверсию.

Подсчет числа инверсий производят следующим образом. Сначала подсчитываем число элементов, стоящих впереди единицы - все эти элементы и только они образуют инверсию с единицей. Вычеркиваем единицу и подсчитываем число элементов впереди двойки - это будут все те элементы, которые образуют инверсии с двойкой (не считая вычеркнутой единицы). Затем вычеркиваем двойку и подсчитываем число элементов перед тройкой и т.д. Сумма всех полученных чисел и будет равна числу инверсий. Число всех инверсий в перестановке обозначим .

Например =2+0+3+1+0+1=7

Перестановка называется четной, если ее числа состав­ляют четное количество инверсий, и нечетной — в противном случае.

Транспозициейназывается преобразование перестановки, при котором меняются местами какие-либо два числа, не обяза­тельно стоящие рядом.

Теорема 4.1 Всякая транспозиция меняет четность перестановки.

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

Общий случай. Пусть меняются местами элементы и перестановки между которыми стоят еще k элементов . Можно выполнить транспозицию элементов и посредством нескольких транспозиций рядом стоящих элементов: поменяем местами сначала с , затем с и т. д., наконец, с c_k (при этом сделаем k транс­позиций рядом стоящих элементов); затем поменяем местами и (еще одна транспозиция) и, наконец, поменяем местами последовательно с , с и так далее, до (еще k транспозиций рядом стоящих элементов). В итоге станет на место и наоборот. При каждой такой транспозиции четность перестановки меняется. Так как она изменит­ся нечетное число раз (2k + 1), поэтому не­четная перестановка сделается четной, а четная — не­четной.■

Следствие. Число четных перестановок равно числу нечетных и равно 0,5 n!

□ Пусть из n! перестановок из n элементов p перестановок четные и q нечетные. Сдела­ем в каждой четной перестановке одну и ту же транс­позицию, например, поменяем местами первые два эле­мента. Тогда каждая четная перестановка превратится в нечетную, при этом все p полученных при этом нечетных перестановок будут разными. А так как общее число нечетных перестановок из n элемен­тов, по предположению, равно q, то p < q. Точно так же можно убедиться в том, что, наоборот, q > р. Следова­тельно, p = q.!

Все n! перестановок из n чисел можно расположить в таком порядке, что каждая следующая будет получаться из пре­дыдущей при помощи одной транспозиции, причем начинать мож­но с любой перестановки.

Определителем n-го порядка, соответствующим квадрат­ной матрице порядка n, называется алгебраическая сумма n! членов, составленная следующим образом. Членами определителя служат всевозможные произведения по n элементов матрицы, взятых по одному в каждой строке и каждом столбце. Член бе­рется со знаком плюс, если индексы столбцов его элементов об­разуют четную перестановку при условии, что сами элементы расположены в порядке возрастания номеров строк, и со знаком минус — в противном случае и обозначается:

= det A =

Определителем первого порядка является величина элемента :

.

Определителем второго порядка равен произведению элементов на главной диагонали минус произведение элементов на побочной диагонали:

.

Определитель третьего порядка, вычисленный по правилу Саррюса