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

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

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

Визначення

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

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

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

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

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

Властивості

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

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

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

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

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

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

Приклад

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

Джерела

• , . Матричный анализ. — М: : Мир, 1989. — 653 с.(рос.)