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

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

Определение

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

${\begin{pmatrix}1&&2&&\ldots &&n\\\sigma (1)&&\sigma (2)&&\ldots &&\sigma (n)\end{pmatrix}}$

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

$P_{\sigma }={\begin{pmatrix}\mathbf {e} _{\sigma (1)}\\\mathbf {e} _{\sigma (2)}\\\vdots \\\mathbf {e} _{\sigma (n)}\end{pmatrix}},$

где $\mathbf {e} _{i}$ — вектор размерности $n$, $i$-й элемент которого равен 1, а остальные равны нулю.

Пример

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

$\pi ={\begin{pmatrix}1&&2&&3&&4\\{\color {Red}4}&&{\color {Green}2}&&{\color {Orange}1}&&{\color {Blue}3}\end{pmatrix}}$

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

$P={\begin{pmatrix}0&&0&&0&&{\color {Red}1}\\0&&{\color {Green}1}&&0&&0\\{\color {Orange}1}&&0&&0&&0\\0&&0&&{\color {Blue}1}&&0\\\end{pmatrix}}$

Свойства

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

  $P_{\pi }P_{\sigma }=P_{\sigma \circ \pi }.$

• Матрицы перестановки ортогональны, так что для каждой такой матрицы существует обратная:

  $P_{\sigma }^{-1}=P_{\sigma }^{T}.$

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