Матрица перестановки

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Ма́трица перестано́вки (или подстано́вки) — квадратная бинарная матрица, в каждой строке и столбце которой находится ровно один единичный элемент. Каждая матрица перестановки размера является матричным представлением перестановки порядка .

Определение[править | править вики-текст]

Пусть дана перестановка порядка :

Соответствующей матрицей перестановки является матрица вида:

где вектор длины , -й элемент которого равен 1, а остальные равны нулю.

Пример[править | править вики-текст]

Перестановка:

Соответствующая матрица:

Свойства[править | править вики-текст]

  • Для любых двух перестановок их матрицы обладают свойством:

' Pπ Pσ = Pσ o π

  • Матрицы перестановки ортогональны, так что для каждой такой матрицы существует обратная:
  • Умножение произвольной матрицы на перестановочную соответственно меняет местами её столбцы.
  • Умножение перестановочной матрицы на произвольную меняет местами строки в .
  • Определитель перестановочной матрицы равен чётности перестановки. Определитель чётной перестановки равен 1, определитель нечётной перестановки - -1.