Изменения

Перейти к: навигация, поиск

Матричное представление перестановок

9 байт убрано, 15:20, 6 января 2017
Нет описания правки
__TOC__
{{Определение
|definition=
'''Матрица перестановки''' (англ. ''Permutation matrix'') — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица.}}
__TOC__
Каждая матрица перестановки размера <tex>n \times n</tex> является матричным представлением перестановки порядка <tex>n</tex>.
\end{pmatrix}</tex>, где <tex>\mathbf{e}_{i}</tex> — двоичный вектор длины <tex>n</tex>, <tex>i</tex>-й элемент которого равен единице, а остальные равны нулю.
===Пример===
Пусть дана перестановка: <tex>\pi = \begin{pmatrix}
Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок''' (англ. ''Elementary permutation matrix''). }}
== Свойства ==
{{Утверждение
матрицы <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=Квадрат элементарной матрицы перестановок есть единичная матрица.
}}
== Применение ==
Благодаря своим свойствам, матрицам перестановок нашлось применение в линейной алгебре. Они используются в элементарных преобразованиях матриц, то есть домножение слева или справа на матрицу перестановок, есть перестановка любых строк или столбов соответственно.
== См. также==
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
== Источники информации ==
*[http://ru.wikipedia.org/wiki/Матрица_перестановки Википедия — Матрица перестановки]
*[http://portal.tpu.ru/SHARED/k/KONVAL/Sites/Russian_sites/1/23.htm Матрица перестановки]
113
правок

Навигация