Меню Главная Случайная статья Настройки Матрица перестановки Материал из https://ru.wikipedia.org Матрица перестановки (или подстановки) — квадратная бинарная матрица, в каждой строке и столбце которой находится ровно один единичный элемент. Каждая матрица перестановки размера ${\displaystyle n\times n}$ является матричным представлением перестановки из ${\displaystyle n}$ элементов. Определение Пусть дана перестановка ${\displaystyle \sigma }$ из ${\displaystyle n}$ элементов: ${\displaystyle {\begin{pmatrix}1&&2&&\ldots &&n\\\sigma (1)&&\sigma (2)&&\ldots &&\sigma (n)\end{pmatrix}}}$ Соответствующей матрицей перестановки является матрица ${\displaystyle n\times n}$ вида: ${\displaystyle P_{\sigma }={\begin{pmatrix}\mathbf {e} _{\sigma (1)}\\\mathbf {e} _{\sigma (2)}\\\vdots \\\mathbf {e} _{\sigma (n)}\end{pmatrix}},}$ где ${\displaystyle \mathbf {e} _{i}}$ — вектор размерности ${\displaystyle n}$, ${\displaystyle i}$-й элемент которого равен 1, а остальные равны нулю. Пример Перестановка: ${\displaystyle \pi ={\begin{pmatrix}1&&2&&3&&4\\{\color {Red}4}&&{\color {Green}2}&&{\color {Orange}1}&&{\color {Blue}3}\end{pmatrix}}}$ Соответствующая матрица: ${\displaystyle P={\begin{pmatrix}0&&0&&0&&{\color {Red}1}\\0&&{\color {Green}1}&&0&&0\\{\color {Orange}1}&&0&&0&&0\\0&&0&&{\color {Blue}1}&&0\\\end{pmatrix}}}$ Свойства Для любых двух перестановок ${\displaystyle \sigma ,\pi }$ их матрицы обладают свойством: ${\displaystyle P_{\pi }P_{\sigma }=P_{\sigma \circ \pi }.}$ Матрицы перестановки ортогональны, так что для каждой такой матрицы существует обратная: ${\displaystyle P_{\sigma }^{-1}=P_{\sigma }^{T}.}$ Умножение произвольной матрицы ${\displaystyle M}$ на перестановочную соответственно меняет местами её столбцы. Умножение перестановочной матрицы на произвольную ${\displaystyle M}$ меняет местами строки в ${\displaystyle M}$. Определитель перестановочной матрицы равен чётности перестановки. Определитель чётной перестановки равен 1, определитель нечётной перестановки — 1.