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

Матриця перестановки — квадратна бінарна матриця, в якій в кожному рядку і кожному стовпці є рівно одна одиниця, а всі інші елементи — нулі.

Матриця перестановки розміру n×n є матричним представленням перестановки порядку n.

Визначення

Якщо задана перестановка порядку n:

$\pi ={\begin{pmatrix}1&2&\cdots &n\\\pi (1)&\pi (2)&\cdots &\pi (n)\end{pmatrix}},$

то їй відповідатиме матриця перестановки розміру n×n:

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

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

Властивості

• Для довільних двох перестановок $\ \sigma ,\pi$ їх матриці задовільняють умові:

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

• Матриці перестановки ортогональні, тому обернена матриця дорівнює транспонованій:

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

• Множення перестановочної матриці на довільну матрицю $\ M$ міняє місцями стовпці в $\ M.$

• Множення довільної матриці $\ M$ на перестановочну міняє місцями строки в $\ M.$

Приклад

Перестановці $\pi ={\begin{pmatrix}1&&2&&3&&4\\4&&2&&1&&3\end{pmatrix}}$ відповідатиме матриця: $P={\begin{pmatrix}0&&0&&0&&1\\0&&1&&0&&0\\1&&0&&0&&0\\0&&0&&1&&0\\\end{pmatrix}}$