Матричное представление перестановок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства)
м (rollbackEdits.php mass rollback)
 
(не показано 16 промежуточных версий 5 участников)
Строка 1: Строка 1:
== Определение ==
+
__TOC__
 +
==Матрица перестановок==
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
'''Матрица перестановки''' (англ. ''Permutation matrix'') — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица.}}
+
'''Матрица перестановок''' (англ. ''Permutation matrix'') — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица.}}
{{Определение
 
|definition=
 
Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок''' (англ. ''Elementary permutation matrix''). }}
 
  
 
Каждая матрица перестановки размера <tex>n \times n</tex> является матричным представлением перестановки порядка <tex>n</tex>.
 
Каждая матрица перестановки размера <tex>n \times n</tex> является матричным представлением перестановки порядка <tex>n</tex>.
Строка 23: Строка 21:
 
\end{pmatrix}</tex>, где <tex>\mathbf{e}_{i}</tex> — двоичный вектор длины <tex>n</tex>, <tex>i</tex>-й элемент которого равен единице, а остальные равны нулю.
 
\end{pmatrix}</tex>, где <tex>\mathbf{e}_{i}</tex> — двоичный вектор длины <tex>n</tex>, <tex>i</tex>-й элемент которого равен единице, а остальные равны нулю.
  
== Пример ==
+
===Элементарная матрица перестановок===
  
Перестановка:
+
{{Определение
: <tex>\pi = \begin{pmatrix}
+
|definition=
 +
Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок''' (англ. ''Elementary permutation matrix''). }}
 +
 
 +
===Пример===
 +
 
 +
Пусть дана перестановка: <tex>\pi = \begin{pmatrix}
 
1 & 2 & 3\\
 
1 & 2 & 3\\
 
1 & 3 & 2
 
1 & 3 & 2
\end{pmatrix}</tex>
+
\end{pmatrix}</tex>. В соответствующей матрице в первом столбце единица будет стоять на первом месте, во втором столбе
 
+
на третьем месте, в третьем на втором. Итого: <tex>P = \begin{pmatrix}
Соответствующая матрица:
 
: <tex>P = \begin{pmatrix}
 
 
1 & 0 & 0 \\
 
1 & 0 & 0 \\
 
0 & 0 & 1 \\
 
0 & 0 & 1 \\
 
0 & 1 & 0 \\
 
0 & 1 & 0 \\
\end{pmatrix}</tex>
+
\end{pmatrix}</tex>. Также эта матрица является элементарной матрицей перестановок, так как получена из единичной, перестановкой второго и третьего столбцов.
 +
 
 +
===Применение===
 +
 
 +
Благодаря своим свойствам, матрицам перестановок нашлось применение в линейной алгебре. Они используются в элементарных преобразованиях матриц, то есть домножение слева или справа на матрицу перестановок, есть перестановка любых строк или столбов соответственно.
  
 
== Свойства ==
 
== Свойства ==
Строка 47: Строка 52:
 
где <tex>\circ</tex> — операция умножения перестановок.
 
где <tex>\circ</tex> — операция умножения перестановок.
 
|proof=
 
|proof=
Рассмотрим <tex>{(P_\sigma P_\pi)}_{i,j} = \sum\limits_{x = 1}^{n}{({P_\sigma}_{i,x} {P_\pi}_{x,j})}</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>.
 
 
эта сумма может быть равна нулю или единице, причем единице в том случае, если в <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=
 
Так как перестановки являются группой, то для любой перестановки существует обратная. Так как любая перестановка имеет свою матрицу перестановки, то утверждение о существовании обратной матрицы перестановки также справедливо.
 
 
}}
 
}}
  
Строка 66: Строка 61:
  
 
Теперь в обратную сторону <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>{(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> {\delta}_{ij} </tex> — символ Кронекера.  
  
{{Утверждение|statement=Произведение матриц перестановок есть матрица перестановок.
+
Отсюда следует, что <tex> P^T=P^{-1} </tex>, так как по определению обратной матрицы <tex> PP^{-1}=P^{-1}P = E </tex>. }}
|proof=
 
Каждой матрице перестановок соответствует своя перестановка. Так как произведение перестановок также дает перестановку, значит и произведение матриц перестановок есть такая же матрица перестановок.}}
 
  
 
{{Утверждение|statement=
 
{{Утверждение|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>.  
Умножение справа матрицы перестановок <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=
 
|proof=
 
Рассмотрим сначала умножение слева, т.е. матрицу <tex> {P}_{ij}{A} </tex>, которую обозначим <tex> {B} = {b}_{kl} </tex>. Посчитаем чему равны элементы этой матрицы:
 
Рассмотрим сначала умножение слева, т.е. матрицу <tex> {P}_{ij}{A} </tex>, которую обозначим <tex> {B} = {b}_{kl} </tex>. Посчитаем чему равны элементы этой матрицы:
  
<tex> {b}_{kl} = {(\ 0\ ...\ 0\ 1\ 0\ ...\ 0\  )}
+
<tex> {b}_{kl} = {(\ 0\ \ldots\ 0\ 1\ 0\ \ldots\ 0\  )}
 
\begin {pmatrix}  
 
\begin {pmatrix}  
 
{a}_{1l}\\
 
{a}_{1l}\\
Строка 91: Строка 84:
 
\end {cases} </tex>
 
\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> {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>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</tex> получается из <tex>A</tex> перестановкой <tex> {i} </tex>-й и <tex> {j} </tex>-й строк.
  
 
Теперь рассмотрим умножение справа. Пусть <tex> {B} = {A}{P}_{ij} </tex>.
 
Теперь рассмотрим умножение справа. Пусть <tex> {B} = {A}{P}_{ij} </tex>.
  
<tex> {b}_{kl} = {(\ {a}_{k1}\ {a}_{k2}\ ...\ {a}_{kn}\  )}
+
<tex> {b}_{kl} = {(\ {a}_{k1}\ {a}_{k2}\ \ldots\ {a}_{kn}\  )}
 
\begin {pmatrix}  
 
\begin {pmatrix}  
 
0\\
 
0\\
Строка 113: Строка 106:
 
\end {cases} </tex>
 
\end {cases} </tex>
  
По определению матрицы перестановок единица в столбце стоит на <tex> {l} </tex> - м месте, если <tex> {l \ne i,j} </tex>, на <tex> {j} </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 = 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> {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>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</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=Квадрат элементарной матрицы перестановок есть единичная матрица.
Строка 126: Строка 130:
 
}}
 
}}
  
{{Утверждение|statement=Матрица перестановок  <tex>n</tex>-го порядка может быть представлена в виде произведения <tex>(n - 1)</tex> элементарных матриц перестановок (<tex>{n > 2}</tex>).
+
{{Утверждение|statement=Матрица перестановок  <tex>n</tex>-го порядка может быть представлена в виде произведения <tex>(n - 1)</tex> элементарных матриц перестановок <tex>{(n > 2)}</tex>.
 
|proof=
 
|proof=
Обозначим  <tex>{t}_{ij}</tex> - элементарную матрицу, полученную из единичной путем изменения  <tex>i</tex> - й и  <tex>j</tex> - й строк. Рассмотрим  матрицу перестановок  
+
Обозначим  <tex>{t}_{ij}</tex> элементарную матрицу, полученную из единичной путем изменения  <tex>i</tex>-й и  <tex>j</tex>-й строк. Рассмотрим  матрицу перестановок  
 
<tex> P = \begin {pmatrix}  
 
<tex> P = \begin {pmatrix}  
{a}_{11} & {a}_{12} & ... & {a}_{1n}\\
+
{a}_{11} & {a}_{12} & \ldots & {a}_{1n}\\
{a}_{21} & {a}_{22} & ... & {a}_{2n}\\
+
{a}_{21} & {a}_{22} & \ldots & {a}_{2n}\\
 
\vdots & \vdots & \ddots & \vdots\\
 
\vdots & \vdots & \ddots & \vdots\\
{a}_{n1} & {a}_{n2} & ... & {a}_{nn}
+
{a}_{n1} & {a}_{n2} & \ldots & {a}_{nn}
 
\end {pmatrix}</tex>  
 
\end {pmatrix}</tex>  
  
 
Возьмем <tex> {{a}_{ij} \ne 0} </tex> и перестановками строк (домножением соответствующей элементарной матрицей слева) или столбцов (домножением соответствующей элементарной матрицей справа) перемещаем его на первое место. Так как в каждой строке или столбце только одна единица, то получим: <tex> \begin {pmatrix}  
 
Возьмем <tex> {{a}_{ij} \ne 0} </tex> и перестановками строк (домножением соответствующей элементарной матрицей слева) или столбцов (домножением соответствующей элементарной матрицей справа) перемещаем его на первое место. Так как в каждой строке или столбце только одна единица, то получим: <tex> \begin {pmatrix}  
1 & 0 & ... & 0\\
+
1 & 0 & \ldots & 0\\
0 & {a}_{22}' & ... & {a}_{2n}'\\
+
0 & {a}_{22}' & \ldots & {a}_{2n}'\\
 
\vdots & \vdots & \ddots & \vdots\\
 
\vdots & \vdots & \ddots & \vdots\\
0 & {a}_{n2}' & ... & {a}_{nn}'
+
0 & {a}_{n2}' & \ldots & {a}_{nn}'
 
\end {pmatrix}</tex>  и так далее, пока не получится единичной матрицы.
 
\end {pmatrix}</tex>  и так далее, пока не получится единичной матрицы.
  
В итоге: <tex> t_1 ... t_kAt_{k+1} ... t_{k+l} = E </tex>.  
+
В итоге: <tex> t_1 \ldots t_kAt_{k+1} \ldots t_{k+l} = E </tex>.  
  
Все элементарные матрицы обратимы и обратная к элементарной матрице — это тоже элементарная матрица, следовательно: <tex> A = t_k^{-1} ... t_1^{-1}Et_{k+l}^{-1} ... t_{k+1}^{-1} = t_k^{-1} ... t_1^{-1}t_{k+l}^{-1} ... t_{k+1}^{-1} </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> таких матриц.
+
Заметим, что с каждым шагом мы домножаем на одну элементарную матрицу перестановок, следовательно всего будет <tex> (n - 1) </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>,
 
 
видно, что второй и третий столбец поменялись местами.
 
  
 
== См. также==
 
== См. также==
* [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://ru.wikipedia.org/wiki/Матрица_перестановки Википедия — Матрица перестановки]
 
*[http://portal.tpu.ru/SHARED/k/KONVAL/Sites/Russian_sites/1/23.htm Матрица перестановки]
 
*[http://portal.tpu.ru/SHARED/k/KONVAL/Sites/Russian_sites/1/23.htm Матрица перестановки]
*[https://en.wikipedia.org/wiki/Permutation_matrix Permutation matrix]
+
*[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.
 
* Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Cambridge: Cambridge University Press. стр. 2, 19.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]
 +
[[Категория: Свойства комбинаторных объектов]]

Текущая версия на 19:14, 4 сентября 2022

Матрица перестановок

Определение:
Матрица перестановок (англ. Permutation matrix) — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица.


Каждая матрица перестановки размера [math]n \times n[/math] является матричным представлением перестановки порядка [math]n[/math].

Пусть дана перестановка [math]\sigma[/math] порядка [math]n[/math]:

[math]\begin{pmatrix} 1 & 2& \ldots & n\\ \sigma(1)& \sigma(2) & \ldots & \sigma(n) \end{pmatrix}[/math]

Соответствующей матрицей перестановки является матрица [math]n \times n[/math] вида:

[math]P_\sigma = \begin{pmatrix} \mathbf{e}_{\sigma(1)}\\ \mathbf{e}_{\sigma(2)}\\ \vdots \\ \mathbf{e}_{\sigma(n)} \end{pmatrix}[/math], где [math]\mathbf{e}_{i}[/math] — двоичный вектор длины [math]n[/math], [math]i[/math]-й элемент которого равен единице, а остальные равны нулю.

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

Определение:
Если матрица перестановок [math]P[/math] получена из единичной матрицы [math]E[/math] перестановкой местами двух строк (или двух столбцов), то такая матрица называется элементарной матрицей перестановок (англ. Elementary permutation matrix).


Пример

Пусть дана перестановка: [math]\pi = \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix}[/math]. В соответствующей матрице в первом столбце единица будет стоять на первом месте, во втором столбе на третьем месте, в третьем на втором. Итого: [math]P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{pmatrix}[/math]. Также эта матрица является элементарной матрицей перестановок, так как получена из единичной, перестановкой второго и третьего столбцов.

Применение

Благодаря своим свойствам, матрицам перестановок нашлось применение в линейной алгебре. Они используются в элементарных преобразованиях матриц, то есть домножение слева или справа на матрицу перестановок, есть перестановка любых строк или столбов соответственно.

Свойства

Утверждение:
Для любых двух перестановок [math]\sigma, \pi[/math] их матрицы обладают свойством:
[math]P_\sigma P_\pi = P_{\pi \circ \sigma}[/math]
где [math]\circ[/math] — операция умножения перестановок.
[math]\triangleright[/math]
Рассмотрим [math]{P_\sigma P_\pi}_{i,j} = \sum\limits_{x = 1}^{n}{{P_\sigma}_{i,x} {P_\pi}_{x,j}}[/math]. Эта сумма может быть равна нулю или единице, причем единице в том случае, если в [math]i[/math]-той строчке на [math]k[/math]-том столбце матрицы [math]P_\sigma[/math] и в [math]k[/math]-той строчке на [math]j[/math]-том столбце матрицы [math]P_\pi[/math] стоят единицы. [math]{P_\sigma}_{i,k} = 1[/math] значит, что в перестановке [math]\sigma[/math] на [math]i[/math]-том месте стоит элемент [math]k[/math], и [math]{P_\pi}_{k,j} = 1[/math] означает что в перестановке [math]\pi[/math] на [math]k[/math]-том месте стоит элемент [math]j[/math], а [math]{P_\sigma P_\pi}_{i,j} = 1[/math] означает что в перестановке, которой соответствует эта матрица, так же на [math]i[/math]-том месте стоит элемент [math]j[/math]. Но также известно, что [math] (\pi \circ \sigma)(i) = \pi(\sigma(i)) = j [/math]. В результате если [math]{P_\sigma P_\pi}_{i,j} = 1[/math], то [math]{P_{\pi \circ \sigma}}_{i,j} = 1[/math]. Аналогичные рассуждения можно провести когда [math]{P_\sigma P_\pi}_{i,j} = 0[/math], и также получим, что [math]{P_{\pi \circ \sigma}}_{i,j} = 0[/math]. Поэтому для любых [math]i,j[/math] справедливо [math]{P_\sigma P_\pi}_{i,j} = {P_{\pi \circ \sigma}}_{i,j}[/math], а раз такое равентсво выполняется, то [math]P_\sigma P_\pi = P_{\pi \circ \sigma}[/math].
[math]\triangleleft[/math]
Утверждение:
Для любой матрицы перестановок [math]P[/math] справедливо:
[math]P^T P = P P^T = E[/math]
где [math]E[/math] — единичная матрица.
[math]\triangleright[/math]

Рассмотрим [math]{(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} [/math]

Теперь в обратную сторону [math]{(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} [/math] где [math] {\delta}_{ij} [/math] — символ Кронекера.

Отсюда следует, что [math] P^T=P^{-1} [/math], так как по определению обратной матрицы [math] PP^{-1}=P^{-1}P = E [/math].
[math]\triangleleft[/math]
Утверждение:
При умножение слева матрицы перестановок [math] {P}_{ij} [/math] на матрицу [math]A[/math] происходит перестановка [math] {i} [/math]-й и [math] {j} [/math]-й строк матрицы [math]A[/math]. Умножение справа матрицы перестановок [math] {P}_{ij} [/math] на матрицу [math]A[/math] приводит к перестановке [math] {i} [/math]-го и [math] {j} [/math]-го столбцов матрицы [math]A[/math].
[math]\triangleright[/math]

Рассмотрим сначала умножение слева, т.е. матрицу [math] {P}_{ij}{A} [/math], которую обозначим [math] {B} = {b}_{kl} [/math]. Посчитаем чему равны элементы этой матрицы:

[math] {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} [/math]

Действительно, по определению матрицы перестановок единица в строке стоит на [math] {k} [/math]-м месте, если , [math] {k \ne i,j} [/math], на [math] {j} [/math]-м месте, если [math] {k = i} [/math], и на [math] {i} [/math]-м месте, если [math] {k = j} [/math]. Итак, если [math] {k \ne i,j} [/math], то [math] {k} [/math]-я строка матрицы [math]B[/math] просто совпадает с [math] {k} [/math]-й строкой матрицы [math]A[/math]. Далее, [math] {i} [/math]-я строка матрицы [math]B[/math] совпадает с [math] {j} [/math]-й строкой матрицы [math]A[/math], и наоборот. Поэтому [math]B[/math] получается из [math]A[/math] перестановкой [math] {i} [/math]-й и [math] {j} [/math]-й строк.

Теперь рассмотрим умножение справа. Пусть [math] {B} = {A}{P}_{ij} [/math].

[math] {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} [/math]

По определению матрицы перестановок единица в столбце стоит на [math] {l} [/math]-м месте, если [math] {l \ne i,j} [/math], на [math] {j} [/math]-м месте, если [math] {l = i} [/math], и на [math] {i} [/math]-м месте, если [math] {l = j} [/math]. Итак, если [math] {l \ne i,j} [/math], то [math] {l} [/math]-й столбец матрицы [math]B[/math] просто совпадает с [math] {l} [/math]-м столбцом матрицы [math]A[/math]. Далее, [math] {i} [/math]-й столбец матрицы [math]B[/math] совпадает с [math] {j} [/math]-м столбцом матрицы [math]A[/math], и

наоборот. Поэтому [math]B[/math] получается из [math]A[/math] перестановкой [math] {i} [/math]-го и [math] {j} [/math]-го столбцов.
[math]\triangleleft[/math]

Пример

Пусть задана матрица перестановки [math]P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{pmatrix}[/math], которая соответствует перестановке [math]\pi = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}[/math], и матрица [math]A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix}[/math],

тогда перемножив получим:

  • [math]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}[/math], видно, что вторая и третья строки поменялись местами.
  • [math]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}[/math], видно, что второй и третий столбец поменялись местами.


Утверждение:
Квадрат элементарной матрицы перестановок есть единичная матрица.
[math]\triangleright[/math]

Любая элементарная матрица перестановок является симметричной матрицей, следовательно [math] \forall{i,j} : {a}_{ij} = {a}_{ji} [/math]. Отсюда следует, что

[math] {P} = {P^T} [/math], а [math] {P P^T} = {E} [/math].
[math]\triangleleft[/math]
Утверждение:
Матрица перестановок [math]n[/math]-го порядка может быть представлена в виде произведения [math](n - 1)[/math] элементарных матриц перестановок [math]{(n \gt 2)}[/math].
[math]\triangleright[/math]

Обозначим [math]{t}_{ij}[/math] — элементарную матрицу, полученную из единичной путем изменения [math]i[/math]-й и [math]j[/math]-й строк. Рассмотрим матрицу перестановок [math] 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}[/math]

Возьмем [math] {{a}_{ij} \ne 0} [/math] и перестановками строк (домножением соответствующей элементарной матрицей слева) или столбцов (домножением соответствующей элементарной матрицей справа) перемещаем его на первое место. Так как в каждой строке или столбце только одна единица, то получим: [math] \begin {pmatrix} 1 & 0 & \ldots & 0\\ 0 & {a}_{22}' & \ldots & {a}_{2n}'\\ \vdots & \vdots & \ddots & \vdots\\ 0 & {a}_{n2}' & \ldots & {a}_{nn}' \end {pmatrix}[/math] и так далее, пока не получится единичной матрицы.

В итоге: [math] t_1 \ldots t_kAt_{k+1} \ldots t_{k+l} = E [/math].

Все элементарные матрицы обратимы и обратная к элементарной матрице — это тоже элементарная матрица, следовательно: [math] 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} [/math].

Заметим, что с каждым шагом мы домножаем на одну элементарную матрицу перестановок, следовательно всего будет [math] (n - 1) [/math] таких матриц.
[math]\triangleleft[/math]

См. также

Источники информации