113
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Матрица перестановки''' (англ. ''Permutation matrix'') — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица.}}
Каждая матрица перестановки размера <tex>n \times n</tex> является матричным представлением перестановки порядка <tex>n</tex>.
\end{pmatrix}</tex>, где <tex>\mathbf{e}_{i}</tex> — двоичный вектор длины <tex>n</tex>, <tex>i</tex>-й элемент которого равен единице, а остальные равны нулю.
1 & 2 & 3\\
1 & 3 & 2
\end{pmatrix}</tex>. В соответствующей матрице в первом столбце единица будет стоять на первом месте, во втором столбе на 3 месте, в третьем на 2.
: <tex>P = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
\end{pmatrix}</tex>
{{Определение
|definition=
Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок''' (англ. ''Elementary permutation matrix''). }}
== Свойства ==
где <tex>\circ</tex> — операция умножения перестановок.
|proof=
Рассмотрим <tex>{(P_\sigma P_\pi)}_{i,j} = \sum\limits_{x = 1}^{n}{({P_\sigma}_{i,x} {P_\pi}_{x,j})}</tex> эта . Эта сумма может быть равна нулю или единице, причем единице в том случае, если в <tex>i</tex> - той строчке на <tex>k</tex> - том столбце матрицы <tex>P_\sigma</tex> и в <tex>k</tex> - той строчке на <tex>j</tex> - том столбце матрицы <tex>P_\pi</tex> стоят единицы. <tex>{P_\sigma}_{i,k} = 1</tex> значит, что в перестановке <tex>\sigma</tex> на <tex>i</tex> - том месте стоит элемент <tex>k</tex>, и <tex>{P_\pi}_{k,j} = 1</tex> означает что в перестановке <tex>\pi</tex> на <tex>k</tex> - том месте стоит элемент <tex>j</tex>, а <tex>{(P_\sigma P_\pi)}_{i,j} = 1</tex> означает что в перестановке, которой соответствует эта матрица, так же на <tex>i</tex> - том месте стоит элемент <tex>j</tex>. Но также известно, что <tex> (\pi \circ \sigma)(i) = \pi(\sigma(i)) = j </tex>. В результате если <tex>{(P_\sigma P_\pi)}_{i,j} = 1</tex>, то <tex>({P_{\pi \circ \sigma}})_{i,j} = 1</tex>. Аналогичные рассуждения можно провести когда <tex>{(P_\sigma P_\pi)}_{i,j} = 0</tex>, и также получим, что <tex>({P_{\pi \circ \sigma}})_{i,j} = 0</tex>. Поэтому для любых <tex>i,j</tex> справедливо <tex>{(P_\sigma P_\pi)}_{i,j} = ({P_{\pi \circ \sigma}})_{i,j}</tex>, а раз такое равентсво выполняется, то <tex>P_\sigma P_\pi = P_{\pi \circ \sigma}</tex>.}}{{Утверждение|statement=Для любой матрицы перестановок существует обратная:<center><tex>P_\sigma^{-1} = P_\sigma^T</tex></center>где <tex>P^T</tex> — транспонированная матрица <tex>P</tex>.|proof=Так как перестановки являются группой, то для любой перестановки существует обратная. Так как любая перестановка имеет свою матрицу перестановки, то утверждение о существовании обратной матрицы перестановки также справедливо.
}}
Теперь в обратную сторону <tex>{(P^T P)}_{ij} = \sum\limits_{k = 1}^{n}{(P^T)}_{ik} {(P)}_{kj} = \sum\limits_{k=1}^{n} {(P)}_{ki} {(P)}_{kj} = {\delta}_{ij} = {E} </tex>
где <tex> {\delta}_{ij} </tex> — символ Кронекера. }}
Отсюда следует, что <tex> P^T=P^{-1} </tex>, так как по определению обратной матрицы <tex> PP^{Утверждение|statement-1}=Произведение матриц перестановок есть матрица перестановок.|proofP^{-1}P =Каждой матрице перестановок соответствует своя перестановка. Так как произведение перестановок также дает перестановку, значит и произведение матриц перестановок есть такая же матрица перестановокE </tex>. }}
{{Утверждение|statement=
