Перестановки и подстановки

Перестановка – это всякое расположение чисел 1,2,..,n в некотором определенном порядке. Записывать перестановку из элементов будем в виде , где , .

Пара элементов составляет инверсию, если , а . Перестановка называется четной, если общее число инверсий в перестановке четное, в противном случае – нечетной. Например, , значит перестановка – нечетная.

Обозначим через вектор-столбец, такой что

Лемма 1. .

Доказательство. Применим метод индукции по . Если , то лемма верна. Пусть утверждение верно при , докажем его для .

Так как π – перестановка, тогда существует такое , что , т.е. . Пусть – перестановка из -ого элемента. Заметим, что .

Действительно, раскладывая исходный определитель по -ому столбцу, получаем, что

= , что и требовалось показать.

Следствие. Транспозиция меняет четность перестановки.

Доказательство. Рассмотрим сначала случай, когда символы и стоят рядом, то есть перестановка имеет вид . Транспозиция превращает перестановку в перестановку . Если в перестановке символы и не составляли инверсии, то в перестановке появляется новая инверсия, т.е. число инверсий увеличивается на 1. В противном случае, число инверсий уменьшится на 1. В обоих случаях четность перестановки меняется.

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

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

Доказательство. Применим метод индукции по числу элементов . Для утверждение верно. Это либо упорядочивание [1,2], [2,1], либо [2,1], [1,2].

Предположим справедливость леммы для и докажем истинность для . Пусть мы должны начать с перестановки . Рассмотрим все перестановки из элементов, в которых на первом месте стоит . Таких перестановок и их можно упорядочить согласно условию леммы по предположению индукции. Мы лишь упорядочиваем оставшуюся часть , в которой имеется элемент. В последней из полученных таким путем перестановок совершаем транспозицию с другим элементом, например , и т.д. Таким способом можно, очевидно, перебрать все перестановки из элементов. Лемма доказана.

Следствие 1. При число четных и нечетных перестановок одинаково и равно .

Доказательство. Упорядочим все перестановки согласно лемме 2, тогда четные и нечетные будут чередоваться, так как они получены одной транспозицией, что и требовалось показать.

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

Отметим, что любую подстановку можно записать различными способами, т.е. .

Четность подстановки определяется четностью общего числа инверсий обеих перестановок, из которых она составлена, т.е. подстановка четная, если – четное число.

Лемма 3. Четность подстановки не зависит от способа ее записи.

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

Пусть подстановка имеет вид , где , . Из перестановки можно получить перестановку путем последовательного применения подстановок , где . Применим , чтобы получить , и т.д.

Таким образом, .

Лемма 4. Любая подстановка раскладывается в произведение транспозиций, причем число этих сомножителей четно, когда подстановка четная.

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

Пусть – подмножество различных элементов множества . Подстановка называется циклом длины , если и при . Ясно, что цикл длины 2 – это транспозиция, а при – тождественная подстановка.

Доказать, что любую подстановку можно разложить в произведение независимых (т.е. непересекающихся) циклов и такое разложение единственно с точностью до перестановки сомножителей, т.е. .

Всякий цикл длины можно разложить в произведение -ой транспозиции, т.е. .

Теорема 2. , (6)

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

Доказательство. Так как , тогда по свойству 6 линейности определителя . Так как , если найдутся такие , что , получаем , где суммирование берется по всем перестановкам множества . В силу лемм 1 и 3 получаем . Теорема доказана.

Следующая теорема позволяет дать аксиоматическое определение детерминанта матрицы , основанное на полилинейной функции столбцов этой матрицы.

Теорема 3. Пусть – функция, для которой выполняются три условия: 1) – линейна по любому столбцу , т. е.

;

2) если и , то ;

3) .

Тогда .

Доказательство. Очевидно, что . Согласно свойству 3 имеем, что если при , то . Далее, раскладывая каждый столбец в виде линейной комбинации единичных столбцов, получаем, что

. Теорема доказана.

Из свойств 1)-2) получаем, что при перестановке двух столбцов местами функция меняет знак. Действительно, пусть , тогда , откуда получаем, что .

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

Рассмотрим функцию от столбцов матрицы .

Теорема 8. (теорема Лапласа). Пусть , тогда .

Доказательство. Пусть .

1) Очевидно, что

2) Проверим, что линейна по каждому столбцу матрицы. Рассмотрим -ый столбец, если , то линейный по этому столбцу, а если j J, то линейный по этому столбцу. Получили, что все слагаемые линейны по -ому столбцу.

3) Пусть и . Возможны 4 случая:

1) , тогда .

2) , тогда .

3) .

4) .

Если , тогда , если , тогда , биекция .

.

Не уменьшая общности можно считать, что -ый и -ый столбцы – соседние, т.е. , тогда .

= =

, откуда .

Таким образом, рассмотренная функция столбцов матрицы согласно теореме 3 равна . Теорема доказана.

Следствие. .