Матричное представление перестановок
Определение
| Определение: |
| Матрица перестановки — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица. |
| Определение: |
| Если матрица перестановок получена из единичной матрицы перестановкой местами двух строк (или двух столбцов), то такая матрица называется элементарной матрицей перестановок. |
Каждая матрица перестановки размера является матричным представлением перестановки порядка .
Пусть дана перестановка порядка :
Соответствующей матрицей перестановки является матрица вида:
- , где — двоичный вектор длины , -й элемент которого равен единице, а остальные равны нулю.
Пример
Перестановка:
Соответствующая матрица:
Свойства
- Для любых двух перестановок их матрицы обладают свойством:
- , где - операция умножения двух перестановок
- Для любой матрицы перестановок существует обратная:
- , где - транспонированная матрица
- Для любой матрицы перестановок справедливо:
- , где - единичная матрица
- Произведение матриц перестановок одного и того же порядка есть матрица перестановок
- Матрица перестановок -го порядка может быть представлена в виде произведения элементарных матриц перестановок
- Квадрат элементарной матрицы перестановок есть единичная матрица
- Умножение произвольной матрицы на перестановочную соответственно меняет местами её столбцы.
- Умножение перестановочной матрицы на произвольную меняет местами строки в .
Применение
Благодаря последним свойствам, матрицам перестановок нашлось применение в линейной алгебре:
пусть задана матрица перестановки , которая соответствует перестановке , и матрица ,
тогда перемножив получим:
- ,
видно, что вторая и третья строки поменялись местами;
- ,
видно, что второй и третий столбец поменялись местами.
