Изменения
→Свойства: Исправление опечатки
__TOC__== Определение Матрица перестановок==
{{Определение
|definition=
'''Матрица перестановкиперестановок'''(англ. '' Permutation matrix'') — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица.}}{{Определение |definition=Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок'''. }}
Каждая матрица перестановки размера <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>. В соответствующей матрице в первом столбце единица будет стоять на первом месте, во втором столбе Соответствующая матрица:на третьем месте, в третьем на втором. Итого: <tex>P = \begin{pmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{pmatrix}</tex>. Также эта матрица является элементарной матрицей перестановок, так как получена из единичной, перестановкой второго и третьего столбцов. ===Применение=== Благодаря своим свойствам, матрицам перестановок нашлось применение в линейной алгебре. Они используются в элементарных преобразованиях матриц, то есть домножение слева или справа на матрицу перестановок, есть перестановка любых строк или столбов соответственно.
== Свойства ==
|statement=Для любых двух перестановок <tex>\sigma, \pi</tex> их матрицы обладают свойством:
<center><tex>P_\sigma P_\pi = P_{\sigma pi \circ \pisigma}</tex></center>
где <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=Для любой матрицы перестановок <tex>P</tex> справедливо:
<center><tex>P^T P = P P^T = E</tex></center> где <tex>E</tex> - — единичная матрица.
|proof=
Теперь в обратную сторону <tex>{(P^T P)}_{Утверждение|statementij} =Произведение матриц перестановок есть матрица перестановок\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> — символ Кронекера. |proofОтсюда следует, что <tex> P^T=Произведение перестановок есть перестановкаP^{-1} </tex>, значит и произведение матриц перестановок есть матрица перестановоктак как по определению обратной матрицы <tex> PP^{-1}=P^{-1}P = E </tex>. }}
{{Утверждение|statement=
|proof=
Рассмотрим произвольную сначала умножение слева, т.е. матрицу <tex>{P}_{ij}{A} </tex> и матрицу перестановки , которую обозначим <tex>P{B} = {b}_{kl} </tex>. Посчитаем чему равны элементы этой матрицы:возьмем <tex>{b}_{kl} = {(\ 0\ \ldots\ 0\ 1\ 0\ \ldots\ 0\ )}\begin {pmatrix} {a}_{1l}\\{a}_{2l}\\\vdots\\{a}_{ml}\end {pmatrix} = \begin {cases}{a}_{kl}, & k \ne i,j,\\{a}_{jl}, & k = i,\\{a}_{il}, & k = j.\end {cases} </tex> Действительно, по определению матрицы перестановок единица в строке стоит на <tex> {k} </tex> - тую строчку матрицы м месте, если , <tex>A{k \ne i,j} </tex> и умножим , на <tex>{j} </tex> - тый столбец м месте, если <tex> {k = i} </tex>, и на <tex>P{i} </tex>-м месте,так как если <tex>{k = j} </tex> - тый столбец матрицы . Итак, если <tex>P{k \ne i,j} </tex> это двоичный вектор с одной единицей, то от <tex>i{k} </tex> - той строчки я строка матрицы <tex>AB</tex> выживет один элемент, причем на просто совпадает с <tex>j{k} </tex> - том местей строкойматрицы <tex>A</tex>.Умножив Далее, <tex>{i} </tex> - тую строчку я строка матрицы <tex>AB</tex> совпадает с <tex> {j} </tex>, на остальные столбцы -й строкой матрицы <tex>PA</tex>, получим, что в инаоборот. Поэтому <tex>iB</tex> - той строке матрицы получается из <tex>A</tex> элементы поменяются местами. Умножая другие строки матрицы перестановкой <tex>A{i} </tex>, будем наблюдать похожее (так как умножаем на те же самые столбцы матрицы -й и <tex>P{j} </tex>)-й строк. Теперь рассмотрим умножение справа. Таким образом получим, что в матрице Пусть <tex>{B} = {A}{P}_{ij} </tex> столбцы поменялись местами. <tex> {b}_{kl} = {(\ {a}_{k1}\ {a}_{k2}\ \ldots\ {a}_{kn}\ )}\begin {pmatrix} 0\\\vdots\\0\\1\\0\\\vdots\\0\end {pmatrix} = \begin {cases}{a}_{kl}, & l \ne i,j,\\{a}_{kj}, & l = i,\\{a}_{ki}, & l = j.\end {cases} </tex>
}}
'''Пример''' Пусть задана матрица перестановки <tex>P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{Утверждение|statementpmatrix}</tex>, которая соответствует перестановке <tex>\pi =Квадрат элементарной матрицы перестановок есть единичная \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}</tex>, и матрица<tex>A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix}</tex>, тогда перемножив получим: * <tex>PA = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{pmatrix}\times \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 7 & 8 & 9 \\ 4 & 5 & 6 \\ \end{pmatrix}</tex>, видно, что вторая и третья строки поменялись местами.
== Ссылки Источники информации ==*[http://ru.wikipedia.org/wiki/Матрица_перестановки Википедия — Матрица перестановки — Википедия]
*[http://portal.tpu.ru/SHARED/k/KONVAL/Sites/Russian_sites/1/23.htm Матрица перестановки]
*[https://en.wikipedia.org/wiki/Permutation_matrix Wikipedia — Permutation matrix]
* Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Cambridge: Cambridge University Press. стр. 2, 19.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Свойства комбинаторных объектов]]