Изменения

__TOC__== Определение Матрица перестановок==

'''Матрица перестановкиперестановок'''(англ. '' Permutation matrix'') — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица.}}{{Определение |definition=Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок'''. }}

== Пример =Элементарная матрица перестановок===

Перестановка:{{Определение |definition=Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок''' (англ. ''Elementary permutation matrix''). }} ===Пример=== Пусть дана перестановка: <tex>\pi = \begin{pmatrix}

\end{pmatrix}</tex>. В соответствующей матрице в первом столбце единица будет стоять на первом месте, во втором столбе  Соответствующая матрица:на третьем месте, в третьем на втором. Итого: <tex>P = \begin{pmatrix}

\end{pmatrix}</tex>. Также эта матрица является элементарной матрицей перестановок, так как получена из единичной, перестановкой второго и третьего столбцов. ===Применение=== Благодаря своим свойствам, матрицам перестановок нашлось применение в линейной алгебре. Они используются в элементарных преобразованиях матриц, то есть домножение слева или справа на матрицу перестановок, есть перестановка любых строк или столбов соответственно.

<center><tex>P_\sigma P_\pi = P_{\sigma pi \circ \pisigma}</tex></center>

где <tex>\circ</tex> - — операция [[Умножение перестановок, обратная перестановка, группа перестановок| умножения двух перестановок]].

Рассмотрим <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>.}}

<center><tex>P^T P = P P^T = E</tex></center> где <tex>E</tex> - — единичная матрица.

Так же следует из того что перестановки являются группой.Рассмотрим <tex>{(P P^T)}_{ij} = \sum\limits_{k = 1}^{n}{(P)}_{ik} {(P^T)}_{kj} = \sum\limits_{k=1}^{n} {(P)}_{ik} {(P)}_{jk} = {\delta}_{ij} = {E} </tex> Теперь в обратную сторону <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>. }}

Умножение произвольной При умножение слева матрицы перестановок <tex>M{P}_{ij} </tex> на перестановочную соответственно меняет местами её столбцыматрицу <tex>A</tex> происходит перестановка <tex> {i} </tex>-й и <tex> {j} </tex>-й строк матрицы <tex>A</tex>.Умножение перестановочной справа матрицы перестановок <tex> {P}_{ij} </tex> на произвольную матрицу <tex>A</tex> приводит к перестановке <tex>M{i} </tex> меняет местами строки в -го и <tex>M{j} </tex>-го столбцов матрицы <tex>A</tex>.

Рассмотрим произвольную сначала умножение слева, т.е. матрицу <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> {k \ne i,j} </tex>, на <tex> {j} </tex>-м месте, если <tex>A{k = i} </tex> , и умножим на <tex>j{i} </tex> - тый столбец м месте, если <tex>P{k = j} </tex>. Итак,так как если <tex>{k \ne i,j} </tex>, то <tex> {k} </tex> - тый столбец я строка матрицы <tex>PB</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\\\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>{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{Утверждение|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>, видно, что вторая и третья строки поменялись местами.

{{Утверждение|statement=Матрица перестановок * <tex>n</tex>-го порядка может быть представлена в виде произведения <tex>(n - 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)</tex> элементарных матриц перестановок|proof& 0 \\ \end{pmatrix} =Перестановка \begin{pmatrix} <tex>n</tex>-го порядка может быть получена <tex>(n - 1)& 3 & 2 \\ 4 & 6 & 5 \\ 7 & 9 & 8 \\ \end{pmatrix}</tex> элементарной транспозицией из тождественной перестановки}}, видно, что второй и третий столбец поменялись местами.

Благодаря последним свойствам{{Утверждение|statement=Квадрат элементарной матрицы перестановок есть единичная матрица.|proof=Любая элементарная матрица перестановок является симметричной матрицей, следовательно <tex> \forall{i, матрицам перестановок нашлось применение в линейной алгебреj} :{a}_{ij} = {a}_{ji} </tex>. Отсюда следует, что <tex> {P} = {P^T} </tex>, а <tex> {P P^T} = {E} </tex>.}}

пусть задана матрица перестановки {{Утверждение|statement=Матрица перестановок <tex>P = \begin{pmatrix} n</tex>-го порядка может быть представлена в виде произведения <tex>(n - 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end)</tex> элементарных матриц перестановок <tex>{pmatrix(n > 2)}</tex>, которая соответствует перестановке .|proof=Обозначим <tex>\pi = \begin{pmatrixt} 1 & 2 & 3 \\ 1 & 3 & 2 \end_{pmatrixij}</tex>— элементарную матрицу, полученную из единичной путем изменения <tex>i</tex>-й и матрица <tex>A j</tex>-й строк. Рассмотрим матрицу перестановок <tex> P = \begin{pmatrix} 1 {a}_{11} & {a}_{12} & 2 \ldots & 3 {a}_{1n}\\ 4 {a}_{21} & 5 {a}_{22} & 6 \ldots & {a}_{2n}\\\vdots & \ 7 vdots & 8 \ddots & 9 \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>PA = t_1 \beginldots t_kAt_{pmatrix} k+1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{pmatrix} \times \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \endldots t_{pmatrixk+l} = \begin{pmatrix} 1 & 2 & 3 \\ 7 & 8 & 9 \\ 4 & 5 & 6 \\ \end{pmatrix}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>AP = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix} \times \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & (n - 1 \\ 0 & 1 & 0 \\ \end{pmatrix} = \begin{pmatrix} 1 & 3 & 2 \\ 4 & 6 & 5 \\ 7 & 9 & 8 \\ \end{pmatrix}) </tex>,таких матриц.}}

видно== См. также==* [[Умножение перестановок, что второй и третий столбец поменялись местами.обратная перестановка, группа перестановок]]

== Ссылки Источники информации ==*[http://ru.wikipedia.org/wiki/Матрица_перестановки Википедия — Матрица перестановки — Википедия]