Изменения

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

Пусть дана перестановка <mathtex>\sigma</mathtex> порядка <mathtex>n</mathtex>:: <mathtex>\begin{pmatrix}

\end{pmatrix}</mathtex>

Соответствующей матрицей перестановки является матрица <mathtex>n \times n</mathtex> вида:: <mathtex>P_\sigma = \begin{pmatrix}

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

: <mathtex>\pi = \begin{pmatrix}

\end{pmatrix}</mathtex>

: <mathtex>P = \begin{pmatrix}

\end{pmatrix}</mathtex>

* Для любых двух перестановок <mathtex>\sigma, \pi</mathtex> их матрицы обладают свойством:*: <mathtex>P_\sigma P_\pi = P_{\sigma \circ \pi}</mathtex>

*: <mathtex>P_\sigma^{-1} = P_\sigma^T</mathtex>* Умножение произвольной матрицы <mathtex>M</mathtex> на перестановочную соответственно меняет местами её столбцы.* Умножение перестановочной матрицы на произвольную <mathtex>M</mathtex> меняет местами строки в <mathtex>M</mathtex>.