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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 68: Строка 68:
  
 
{{Утверждение|statement=
 
{{Утверждение|statement=
При умножение слева элементарной матрицы <tex> {P}_{ij} </tex> перестановок на матрицу A происходит перестановка i и j строк матрицы A.  
+
При умножение слева элементарной матрицы <tex> {P}_{ij} </tex> перестановок на матрицу A происходит перестановка <tex> {i} </tex> - й и <tex> {j} </tex> - й строк матрицы A.  
Умножение справа элементарной матрицы перестановок <tex> {P}_{ij} </tex> на матрицу A приводит к перестановке i и j столбцов матрицы A.
+
Умножение справа элементарной матрицы перестановок <tex> {P}_{ij} </tex> на матрицу A приводит к перестановке <tex> {i} </tex> - го и <tex> {j} </tex> - го столбцов матрицы A.
 
|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\ ...\ 0\ 1\ 0\ ...\ 0)}
 
\begin {pmatrix}  
 
\begin {pmatrix}  
 
{a}_{1l}\\
 
{a}_{1l}\\
Строка 79: Строка 79:
 
\vdots\\
 
\vdots\\
 
{a}_{ml}
 
{a}_{ml}
\end {pmatrix}
+
\end {pmatrix} =
  </tex>
+
\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> {k = i} </tex>, и на <tex> {i} </tex> - м месте, если <tex> {k = j} </tex>. Итак, если <tex> {k \ne i,j} </tex>, то <tex> {k} </tex> - я строка матрицы B просто совпадает с <tex> {k} </tex> - й строкой
 +
матрицы A. Далее, <tex> {i} </tex> - я строка матрицы B совпадает с <tex> {j} </tex> - й строкой матрицы A, и
 +
наоборот. Поэтому B получается из A перестановкой <tex> {i} </tex> - й и <tex> {j} </tex> - й строк.
 +
 
 +
Теперь рассмотрим умножение справа. Пусть <tex> {B} = {A}{P}_{ij} </tex>.
 +
 
 +
<tex> {b}_{kl} = {(\ {a}_{k1}\ {a}_{k2}\ ...\ {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> - й столбец матрицы B просто совпадает с <tex> {l} </tex> - м столбцом
 +
матрицы A. Далее, <tex> {i} </tex> - й столбец матрицы B совпадает с <tex> {j} </tex> - м столбцом матрицы A, и
 +
наоборот. Поэтому B получается из A перестановкой <tex> {i} </tex> - го и <tex> {j} </tex> - го столбцов.
 
}}
 
}}
  
 
{{Утверждение|statement=
 
{{Утверждение|statement=
Умножение произвольной матрицы <tex>A</tex> на перестановочную соответственно меняет местами её столбцы.
+
Умножение справа матрицы перестановок на произвольной матрицу <tex>A</tex> соответственно меняет местами её столбцы.
Умножение перестановочной матрицы на произвольную <tex>A</tex> меняет местами строки в <tex>A</tex>.
+
Умножение слева матрицы перестановок на произвольную матрицу <tex>A</tex> меняет местами строки в этой матрице.
 
|proof=
 
|proof=
 
Рассмотрим произвольную матрицу <tex>A</tex> и матрицу перестановки <tex>P</tex>:
 
Рассмотрим произвольную матрицу <tex>A</tex> и матрицу перестановки <tex>P</tex>:
возьмем <tex>i</tex> тую строчку матрицы <tex>A</tex> и умножим на <tex>j</tex> тый столбец <tex>P</tex>,
+
возьмем <tex>i</tex> - тую строчку матрицы <tex>A</tex> и умножим на <tex>j</tex> - тый столбец <tex>P</tex>,
так как <tex>j</tex> тый столбец матрицы <tex>P</tex> это двоичный вектор с одной единицей, то от <tex>i</tex> той строчки матрицы <tex>A</tex> выживет один элемент, причем на <tex>j</tex> том месте.
+
так как <tex>j</tex> - тый столбец матрицы <tex>P</tex> это двоичный вектор с одной единицей, то от <tex>i</tex> - той строчки матрицы <tex>A</tex> выживет один элемент, причем на <tex>j</tex> - том месте.
Умножив <tex>i</tex> тую строчку матрицы <tex>A</tex>, на остальные столбцы матрицы <tex>P</tex>, получим, что в <tex>i</tex> той строке матрицы <tex>A</tex> элементы поменяются местами. Умножая другие строки матрицы <tex>A</tex>, будем наблюдать похожее (так как умножаем на те же самые столбцы матрицы <tex>P</tex>). Таким образом получим, что в матрице <tex>A</tex> столбцы поменялись местами.
+
Умножив <tex>i</tex> - тую строчку матрицы <tex>A</tex>, на остальные столбцы матрицы <tex>P</tex>, получим, что в <tex>i</tex> - той строке матрицы <tex>A</tex> элементы поменяются местами. Умножая другие строки матрицы <tex>A</tex>, будем наблюдать похожее (так как умножаем на те же самые столбцы матрицы <tex>P</tex>). Таким образом получим, что в матрице <tex>A</tex> столбцы поменялись местами.
  
 
Доказательство второго утверждения аналогично.
 
Доказательство второго утверждения аналогично.

Версия 21:20, 2 января 2017

Определение

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


Определение:
Если матрица перестановок [math]P[/math] получена из единичной матрицы [math]E[/math] перестановкой местами двух строк (или двух столбцов), то такая матрица называется элементарной матрицей перестановок (англ. Elementary 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]\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_\sigma^{-1} = P_\sigma^T[/math]
где [math]P^T[/math] — транспонированная матрица [math]P[/math].
[math]\triangleright[/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]\triangleleft[/math]
Утверждение:
При умножение слева элементарной матрицы [math] {P}_{ij} [/math] перестановок на матрицу A происходит перестановка [math] {i} [/math] - й и [math] {j} [/math] - й строк матрицы A. Умножение справа элементарной матрицы перестановок [math] {P}_{ij} [/math] на матрицу A приводит к перестановке [math] {i} [/math] - го и [math] {j} [/math] - го столбцов матрицы A.
[math]\triangleright[/math]

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

[math] {b}_{kl} = {(\ 0\ ...\ 0\ 1\ 0\ ...\ 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] - я строка матрицы B просто совпадает с [math] {k} [/math] - й строкой матрицы A. Далее, [math] {i} [/math] - я строка матрицы B совпадает с [math] {j} [/math] - й строкой матрицы A, и наоборот. Поэтому B получается из A перестановкой [math] {i} [/math] - й и [math] {j} [/math] - й строк.

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

[math] {b}_{kl} = {(\ {a}_{k1}\ {a}_{k2}\ ...\ {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] - й столбец матрицы B просто совпадает с [math] {l} [/math] - м столбцом матрицы A. Далее, [math] {i} [/math] - й столбец матрицы B совпадает с [math] {j} [/math] - м столбцом матрицы A, и

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

Рассмотрим произвольную матрицу [math]A[/math] и матрицу перестановки [math]P[/math]: возьмем [math]i[/math] - тую строчку матрицы [math]A[/math] и умножим на [math]j[/math] - тый столбец [math]P[/math], так как [math]j[/math] - тый столбец матрицы [math]P[/math] это двоичный вектор с одной единицей, то от [math]i[/math] - той строчки матрицы [math]A[/math] выживет один элемент, причем на [math]j[/math] - том месте. Умножив [math]i[/math] - тую строчку матрицы [math]A[/math], на остальные столбцы матрицы [math]P[/math], получим, что в [math]i[/math] - той строке матрицы [math]A[/math] элементы поменяются местами. Умножая другие строки матрицы [math]A[/math], будем наблюдать похожее (так как умножаем на те же самые столбцы матрицы [math]P[/math]). Таким образом получим, что в матрице [math]A[/math] столбцы поменялись местами.

Доказательство второго утверждения аналогично.
[math]\triangleleft[/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]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],

видно, что второй и третий столбец поменялись местами.

См. также

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