Изменения
→Свойства: Исправление опечатки
__TOC__
==Матрица перестановок==
{{Определение
|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>-й элемент которого равен единице, а остальные равны нулю.
===Элементарная матрица перестановок=== {{Определение |definition=Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок''' (англ. ''Elementary permutation matrix''). }} ===Пример. ===
Пусть дана перестановка: <tex>\pi = \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{pmatrix}</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>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> 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://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.
