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

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

Матриця перестановки розміру 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}}$