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

Определение

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

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

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

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

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

Пример

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

${\displaystyle \pi ={\begin{pmatrix}1&&2&&3&&4\\4&&2&&1&&3\end{pmatrix}}}$

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

${\displaystyle P={\begin{pmatrix}0&&0&&0&&1\\0&&1&&0&&0\\1&&0&&0&&0\\0&&0&&1&&0\\\end{pmatrix}}}$

Свойства

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

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

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

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

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