43
правки
Изменения
Новая страница: «'''Ма́трица перестано́вки''' (или ''подстано́вки'') — квадратная бинарная матрица, в каждой…»
'''Ма́трица перестано́вки''' (или ''подстано́вки'') — квадратная [[бинарная матрица]], в каждой строке и столбце которой находится лишь один единичный элемент. Каждая матрица перестановки размера <math>n \times n</math> является матричным представлением [[Перестановка|перестановки]] порядка <math>n</math>.
== Определение ==
Пусть дана перестановка <math>\sigma</math> порядка <math>n</math>:
: <math>\begin{pmatrix}
1 && 2&& \ldots && n\\
\sigma(1)&& \sigma(2) && \ldots && \sigma(n)
\end{pmatrix}</math>
Соответствующей матрицей перестановки является матрица <math>n \times n</math> вида:
: <math>P_\sigma = \begin{pmatrix}
\mathbf{e}_{\sigma(1)}\\
\mathbf{e}_{\sigma(2)}\\
\vdots \\
\mathbf{e}_{\sigma(n)}
\end{pmatrix},
</math>
где <math>\mathbf{e}_{i}</math> — [[Вектор (математика)|вектор]] длины <math>n</math>, <math>i</math>-й элемент которого равен 1, а остальные равны нулю.
=== Пример ===
Перестановка:
: <math>\pi = \begin{pmatrix}
1 && 2 && 3 && 4\\
4 && 2 && 1 && 3
\end{pmatrix}</math>
Соответствующая матрица:
: <math>P = \begin{pmatrix}
0 && 0 && 0 && 1 \\
0 && 1 && 0 && 0 \\
1 && 0 && 0 && 0 \\
0 && 0 && 1 && 0 \\
\end{pmatrix}</math>
== Свойства ==
* Для любых двух перестановок <math>\sigma, \pi</math> их матрицы обладают свойством:
*: <math>P_\sigma P_\pi = P_{\sigma \circ \pi}</math>
* Матрицы перестановки [[Ортогональная матрица|ортогональны]], так что для каждой такой матрицы существует обратная:
*: <math>P_\sigma^{-1} = P_\sigma^T</math>
* Умножение произвольной матрицы <math>M</math> на перестановочную соответственно меняет местами её столбцы.
* Умножение перестановочной матрицы на произвольную <math>M</math> меняет местами строки в <math>M</math>.
== Определение ==
Пусть дана перестановка <math>\sigma</math> порядка <math>n</math>:
: <math>\begin{pmatrix}
1 && 2&& \ldots && n\\
\sigma(1)&& \sigma(2) && \ldots && \sigma(n)
\end{pmatrix}</math>
Соответствующей матрицей перестановки является матрица <math>n \times n</math> вида:
: <math>P_\sigma = \begin{pmatrix}
\mathbf{e}_{\sigma(1)}\\
\mathbf{e}_{\sigma(2)}\\
\vdots \\
\mathbf{e}_{\sigma(n)}
\end{pmatrix},
</math>
где <math>\mathbf{e}_{i}</math> — [[Вектор (математика)|вектор]] длины <math>n</math>, <math>i</math>-й элемент которого равен 1, а остальные равны нулю.
=== Пример ===
Перестановка:
: <math>\pi = \begin{pmatrix}
1 && 2 && 3 && 4\\
4 && 2 && 1 && 3
\end{pmatrix}</math>
Соответствующая матрица:
: <math>P = \begin{pmatrix}
0 && 0 && 0 && 1 \\
0 && 1 && 0 && 0 \\
1 && 0 && 0 && 0 \\
0 && 0 && 1 && 0 \\
\end{pmatrix}</math>
== Свойства ==
* Для любых двух перестановок <math>\sigma, \pi</math> их матрицы обладают свойством:
*: <math>P_\sigma P_\pi = P_{\sigma \circ \pi}</math>
* Матрицы перестановки [[Ортогональная матрица|ортогональны]], так что для каждой такой матрицы существует обратная:
*: <math>P_\sigma^{-1} = P_\sigma^T</math>
* Умножение произвольной матрицы <math>M</math> на перестановочную соответственно меняет местами её столбцы.
* Умножение перестановочной матрицы на произвольную <math>M</math> меняет местами строки в <math>M</math>.
