- •Линейная алгебра Операции над матрицами Понятие матрицы
- •Линейные операции
- •Умножение строки на столбец
- •Произведение матриц
- •Свойства матричных операций
- •Диагональные матрицы
- •Единичная матрица
- •Нулевая матрица
- •Треугольные, транспонированные и симметричные матрицы
- •Обратная матрица
- •Сопряженные, эрмитовы и унитарные матрицы
- •Блочные матрицы
- •Матрица перестановок
- •Матрица масштабирования
- •Неунитарная матрица
- •Элементарные преобразования матриц
- •Матрицы Паули
- •Матрицы вида eA
- •Определители Перестановки и транспозиции
- •Теоремы о транспозициях и перестановках
- •Понятие определителя
- •Определители второго и третьего порядков
- •Свойства определителей
- •Разложение определителя по элементам строки или столбца
- •Теорема Лапласа
- •Вычисление определителей методом элементарных преобразований
- •Обратная матрица Основные понятия
- •Лемма 1 (Теорема аннулирования)
- •Лемма 2
- •Теорема об обратной матрице
- •Вычисление обратной матрицы методом элементарных преобразований
Теоремы о транспозициях и перестановках
Теорема 1. Любая транспозиция изменяет четность перестановки.
Доказательство. Утверждение теоремы представляется вполне очевидным в случае транспозиции соседних элементов, поскольку взаимная перестановка элементов ij и ij+1 приводит к появлению или исчезновению инверсии между ними. Транспозицию элементов ij и ij+k можно рассматривать как результат k последовательных транспозиций элемента ij с соседними элементами, расположенными справа от ij , и последующих k - 1 транспозиций элемента ij+k с соседними элементами, расположенными слева от ij+k :
Полное число транспозиций k + (k - 1) = 2 k - 1 является нечетным числом, что означает изменение четности перестановки.
Следствия.
Четная перестановка возникает в результате четного числа транспозиций элементов множества S = {1, 2, ..., n}.
Нечетная перестановка возникает в результате нечетного числа транспозиций элементов множества S.
Теорема 2. Существует n! различных перестановок множества S = {1, 2, ..., n}.
Доказательство. В произвольной перестановке множества S в первой позиции может располагаться любое из первых n натуральных чисел. Для каждого из этих n вариантов во вторую позицию можно поместить любое из оставшихся (n -1) чисел, в третью – любое из оставшихся (n - 2) чисел и так далее. Последняя n-ая позиция может быть замещена единственным оставшимся элементом. Таким образом, общее число различных перестановок множества S равно n(n – 1)(n – 2)...1 = n! .
Примеры:
{1, 2, 3}, {1, 3, 2}, {2, 3, 1}, {2, 1, 3}, {3, 1, 2} {3, 2, 1}. |
***
Таким образом, перестановка P содержит четное число инверсий. Другое решение. Перестановка P является четной, поскольку представляет собой результат четного числа последовательных транспозиций элементов множества S = {1, 2, 3}: {1, 2, 3} ⇒ {1, 3, 2} ⇒ {2, 3, 1}. |
***
Таким образом, перестановка Q содержит четное число инверсий. |
