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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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