3622
правки
Изменения
→Матрица перестановок
__TOC__== Определение Матрица перестановок==
{{Определение
|definition=
'''Матрица перестановкиперестановок''' (англ. ''Permutation matrix'') — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица.}}{{Определение |definition=Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок''' (англ. ''Elementary 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>. В соответствующей матрице в первом столбце единица будет стоять на первом месте, во втором столбе Соответствующая матрица:на третьем месте, в третьем на втором. Итого: <tex>P = \begin{pmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{pmatrix}</tex>. Также эта матрица является элементарной матрицей перестановок, так как получена из единичной, перестановкой второго и третьего столбцов. ===Применение=== Благодаря своим свойствам, матрицам перестановок нашлось применение в линейной алгебре. Они используются в элементарных преобразованиях матриц, то есть домножение слева или справа на матрицу перестановок, есть перестановка любых строк или столбов соответственно.
== Свойства ==
где <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=
При умножение слева матрицы перестановок <tex> {P}_{ij} </tex> на матрицу <tex>A</tex> происходит перестановка <tex> {i} </tex> - й и <tex> {j} </tex> - й строк матрицы <tex>A</tex>. Умножение справа матрицы перестановок <tex> {P}_{ij} </tex> на матрицу <tex>A</tex> приводит к перестановке <tex> {i} </tex> - го и <tex> {j} </tex> - го столбцов матрицы <tex>A</tex>.
|proof=
Рассмотрим сначала умножение слева, т.е. матрицу <tex> {P}_{ij}{A} </tex>, которую обозначим <tex> {B} = {b}_{kl} </tex>. Посчитаем чему равны элементы этой матрицы:
<tex> {b}_{kl} = {(\ 0\ ...\ldots\ 0\ 1\ 0\ ...\ldots\ 0\ )}
\begin {pmatrix}
{a}_{1l}\\
\end {cases} </tex>
Действительно, по определению матрицы перестановок единица в строке стоит на <tex> {k} </tex> - м месте, если , <tex> {k \ne i,j} </tex>, на <tex> {j} </tex> - м месте, если <tex> {k = i} </tex>, и на <tex> {i} </tex> - м месте, если <tex> {k = j} </tex>. Итак, если <tex> {k \ne i,j} </tex>, то <tex> {k} </tex> - я строка матрицы <tex>B</tex> просто совпадает с <tex> {k} </tex> - й строкойматрицы <tex>A</tex>. Далее, <tex> {i} </tex> - я строка матрицы <tex>B</tex> совпадает с <tex> {j} </tex> - й строкой матрицы <tex>A</tex>, инаоборот. Поэтому <tex>B</tex> получается из <tex>A</tex> перестановкой <tex> {i} </tex> - й и <tex> {j} </tex> - й строк.
Теперь рассмотрим умножение справа. Пусть <tex> {B} = {A}{P}_{ij} </tex>.
<tex> {b}_{kl} = {(\ {a}_{k1}\ {a}_{k2}\ ...\ldots\ {a}_{kn}\ )}
\begin {pmatrix}
0\\
\end {cases} </tex>
По определению матрицы перестановок единица в столбце стоит на <tex> {l} </tex> - м месте, если <tex> {l \ne i,j} </tex>, на <tex> {j} </tex> - м месте, если <tex> {l = i} </tex>, и на <tex> {i} </tex> - м месте, если <tex> {l = j} </tex>.Итак, если <tex> {l \ne i,j} </tex>, то <tex> {l} </tex> - й столбец матрицы <tex>B</tex> просто совпадает с <tex> {l} </tex> - м столбцомматрицы <tex>A</tex>. Далее, <tex> {i} </tex> - й столбец матрицы <tex>B</tex> совпадает с <tex> {j} </tex> - м столбцом матрицы <tex>A</tex>, инаоборот. Поэтому <tex>B</tex> получается из <tex>A</tex> перестановкой <tex> {i} </tex> - го и <tex> {j} </tex> - го столбцов.
}}
'''Пример'''
Пусть задана матрица перестановки <tex>P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{pmatrix}</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>, видно, что вторая и третья строки поменялись местами.
* <tex>AP = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix} \times \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{pmatrix} = \begin{pmatrix} 1 & 3 & 2 \\ 4 & 6 & 5 \\ 7 & 9 & 8 \\ \end{pmatrix}</tex>, видно, что второй и третий столбец поменялись местами.
{{Утверждение|statement=Квадрат элементарной матрицы перестановок есть единичная матрица.
}}
{{Утверждение|statement=Матрица перестановок <tex>n</tex>-го порядка может быть представлена в виде произведения <tex>(n - 1)</tex> элементарных матриц перестановок (<tex>{(n > 2)}</tex>).
|proof=
Обозначим <tex>{t}_{ij}</tex> - — элементарную матрицу, полученную из единичной путем изменения <tex>i</tex> - й и <tex>j</tex> - й строк. Рассмотрим матрицу перестановок
<tex> P = \begin {pmatrix}
{a}_{11} & {a}_{12} & ... \ldots & {a}_{1n}\\{a}_{21} & {a}_{22} & ... \ldots & {a}_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
{a}_{n1} & {a}_{n2} & ... \ldots & {a}_{nn}
\end {pmatrix}</tex>
Возьмем <tex> {{a}_{ij} \ne 0} </tex> и перестановками строк (домножением соответствующей элементарной матрицей слева) или столбцов (домножением соответствующей элементарной матрицей справа) перемещаем его на первое место. Так как в каждой строке или столбце только одна единица, то получим: <tex> \begin {pmatrix}
1 & 0 & ... \ldots & 0\\0 & {a}_{22}' & ... \ldots & {a}_{2n}'\\
\vdots & \vdots & \ddots & \vdots\\
0 & {a}_{n2}' & ... \ldots & {a}_{nn}'
\end {pmatrix}</tex> и так далее, пока не получится единичной матрицы.
В итоге: <tex> t_1 ... \ldots t_kAt_{k+1} ... \ldots t_{k+l} = E </tex>.
Все элементарные матрицы обратимы и обратная к элементарной матрице — это тоже элементарная матрица, следовательно: <tex> A = t_k^{-1} ... \ldots t_1^{-1}Et_{k+l}^{-1} ... \ldots t_{k+1}^{-1} = t_k^{-1} ... \ldots t_1^{-1}t_{k+l}^{-1} ... \ldots t_{k+1}^{-1} </tex>.
Заметим, что с каждым шагом мы домнажаем на одну элементарную матрицу перестановок, следовательно всего будет <tex> (n-1) </tex> таких матриц.
}}
== См. также==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BE%D0%BA,_%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0,_%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BE%D0%BA [Умножение перестановок, обратная перестановка, группа перестановок]]
== Источники информации ==
*[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.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Свойства комбинаторных объектов]]
