Главная | Обратная связь | Поможем написать вашу работу!

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

Детерминанты

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

Детерминант (определитель) матрицы определим следующим образом:

(1)

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

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

Пусть , тогда по формуле (1) получаем, что .

Теорема 1. Пусть (2)

. (3)

Тогда для любых и . (Формулы (2) и (3) называют разложением определителя по -му столбцу и -ой строке соответственно).

Доказательство. Докажем теорему методом математической индукции по . Несложно проверить справедливость формул при (сделайте это!). Далее предполагая, что формулы (2) и (3) выполнены для определителей -го порядка, докажем их справедливость для определителей -ого порядка, где . Покажем сначала, что

= . Разложив минор по первой строке, получаем . Тогда =

= = .

С другой стороны, = . Раскладывая минор по первому столбцу, получаем . Значит, == = . Так как полученные выражения различаются только порядком суммирования, то показано, что .

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

Матрица называется транспонированной к матрице , если для любых и элементы этих матриц связаны соотношениями . Говорят также, что матрица получается транспонированием матрицы .

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

Действительно, разложение по первой строке и разложение по первому столбцу совпадают.

, так как при .

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

+ = .

= .

Так как

, получаем . Теорема доказана.

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

Следствие 1. . (4)

Следствие 2. Для любого

= . (5)

Свойства определителя

Соотношение (4) дает нам одно из важных свойств определителя, устанавливающих равноправность строк и столбцов в определителе. Поэтому все дальнейшие свойства, устанавливаемые для строк, будут иметь место и для столбцов. Итак,

Свойство 1. При транспонировании матрицы определитель не меняется.

Свойство 2. При транспозиции (перестановке) двух строк определитель меняет знак.

Доказательство. Пусть – матрица, полученная из матрицы перестановкой первой и -ой строк. Согласно следствию 2 имеем, что . Легко проверить, что , тогда .

Итак, перестановка строк меняет знак определителя. Перестановку -ой и -ой строк в определителе можно проделать за три шага: . Свойство доказано.

Пусть – -ая строка матрицы .

Свойство 3. Если найдется пара и такая, что и , то определитель равен нулю.

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

В том случае, если , то воспользовавшись свойством 2 и поменяв местами первую и -ую строки, сведем доказательство к уже разобранному случаю. Свойство доказано.

Свойство 4. Если все элементы некоторой строки матрицы умножить на элемент , то и сам определитель умножится на .

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

Свойство 5. Если , то , где

Доказательство. Действительно,

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

Свойство 6. Пусть , тогда, если , то , где – матрица, -ая строка которой равна .

Доказательство провести индукцией по .

Свойство 7: Определитель не изменится, если к строке прибавить линейную комбинацию остальных строк.

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

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

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

Перестановка – это всякое расположение чисел 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, то линейный по этому столбцу. Получили, что все слагаемые линейны по -ому столбцу.