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

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

Определение

Пусть дана перестановка $\sigma$ из $n$ элементов:

$\left(\begin{array}{ccccccc}1& & 2& & \dots & & n\\ \sigma (1)& & \sigma (2)& & \dots & & \sigma (n)\end{array}\right)$

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

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

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

Пример

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

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

Свойства

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

  $P_{\pi }{P}_{\sigma }=P_{\sigma \circ \pi }.$

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

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

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