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

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

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

Визначення

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

$\pi =\left(\begin{array}{cccc}1& 2& \cdots & n\\ \pi (1)& \pi (2)& \cdots & \pi (n)\end{array}\right),$

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

$P_{\pi }=\left(\begin{array}{c}{𝐞}_{\pi (1)}\\ {𝐞}_{\pi (2)}\\ ⋮\\ {𝐞}_{\pi (n)}\end{array}\right)$

де ${𝐞}_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 =\left(\begin{array}{ccccccc}1& & 2& & 3& & 4\\ 4& & 2& & 1& & 3\end{array}\right)$ відповідатиме матриця: $P=\left(\begin{array}{ccccccc}0& & 0& & 0& & 1\\ 0& & 1& & 0& & 0\\ 1& & 0& & 0& & 0\\ 0& & 0& & 1& & 0\end{array}\right)$

Джерела

• Шаблон:Гантмахер.Теорія матриць
• Шаблон:Хорн.Джонсон.Матричний аналіз