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

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

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