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

Ма́трица перестано́вки (или подстано́вки) — квадратная бинарная матрица, в каждой строке и столбце которой находится ровно один единичный элемент. Каждая матрица перестановки размера $n\times <!--\; \times \; -->n$$n\times n$ является матричным представлением перестановки из $n$$n$ элементов.

ОпределениеПравить

Пусть дана перестановка $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$  из $n$$n$  элементов:

${\begin{pmatrix}1&&2&&\ldots &&n\\\sigma (1)&&\sigma (2)&&\ldots &&\sigma (n)\end{pmatrix}}$ 

Соответствующей матрицей перестановки является матрица $n\times <!--\; \times \; -->n$$n\times n$  вида:

$P_{\mathrm{\sigma <!--\; \sigma \; -->}}=\left(\begin{array}{c}{\mathbf{e}}_{\mathrm{\sigma <!--\; \sigma \; -->}(1)}\\ {\mathbf{e}}_{\mathrm{\sigma <!--\; \sigma \; -->}(2)}\\ ⋮<!--\; ⋮\; -->\\ {\mathbf{e}}_{\mathrm{\sigma <!--\; \sigma \; -->}(n)}\end{array}\right),$$P_{\sigma }={\begin{pmatrix}{\mathbf {e}}_{{\sigma (1)}}\\{\mathbf {e}}_{{\sigma (2)}}\\\vdots \\{\mathbf {e}}_{{\sigma (n)}}\end{pmatrix}},$ 

где ${\mathbf{e}}_i$${\mathbf {e}}_{{i}}$  — вектор размерности $n$$n$ , $i$$i$ -й элемент которого равен 1, а остальные равны нулю.

ПримерПравить

Перестановка:

$\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}}$ 

СвойстваПравить

• Для любых двух перестановок $\mathrm{\sigma <!--\; \sigma \; -->},\mathrm{\pi <!--\; \pi \; -->}$$\sigma ,\pi$  их матрицы обладают свойством:

  $P_{\mathrm{\pi <!--\; \pi \; -->}}{P}_{\mathrm{\sigma <!--\; \sigma \; -->}}=P_{\mathrm{\sigma <!--\; \sigma \; -->}\circ <!--\; \circ \; -->\mathrm{\pi <!--\; \pi \; -->}}.$$P_{\pi }P_{\sigma }=P_{\sigma \circ \pi }.$ 

• Матрицы перестановки ортогональны, так что для каждой такой матрицы существует обратная:

  $P_{\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}=P_{\mathrm{\sigma <!--\; \sigma \; -->}}^T.$$P_{\sigma }^{-1}=P_{\sigma }^{T}.$ 

• Умножение произвольной матрицы $M$$M$  на перестановочную соответственно меняет местами её столбцы.
• Умножение перестановочной матрицы на произвольную $M$$M$  меняет местами строки в $M$$M$ .
• Определитель перестановочной матрицы равен чётности перестановки. Определитель чётной перестановки равен 1, определитель нечётной перестановки - -1.