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

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

Определение

Пусть дана перестановка $\sigma$ порядка $n$:

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

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

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

где $\mathbf{e}_{i}$ — вектор длины $n$, $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}$

Свойства

• Для любых двух перестановок $\sigma, \pi$ их матрицы обладают свойством:

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

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

  $P_\sigma^{-1} = P_\sigma^T$

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