Открыть главное меню

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

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

ОпределениеПравить

Пусть дана перестановка   из   элементов:

 

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

 

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

ПримерПравить

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

 

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

 

СвойстваПравить

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