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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 45: Строка 45:
 
<center><tex>P_\sigma P_\pi = P_{\sigma \circ \pi}</tex></center>
 
<center><tex>P_\sigma P_\pi = P_{\sigma \circ \pi}</tex></center>
  
где <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>
Строка 55: Строка 55:
 
Для любой матрицы перестановок существует обратная:
 
Для любой матрицы перестановок существует обратная:
 
<center><tex>P_\sigma^{-1} = P_\sigma^T</tex></center>
 
<center><tex>P_\sigma^{-1} = P_\sigma^T</tex></center>
где <tex>P^T</tex> - транспонированная матрица <tex>P</tex>
+
где <tex>P^T</tex> - транспонированная матрица <tex>P</tex>.
 
|proof=
 
|proof=
 
Так как перестановки являются группой, то для любой перестановки существует обратная. Так как любая перестановка имеет свою матрицу перестановки, то утверждение о существовании обратной матрицы перестановки также справедливо.
 
Так как перестановки являются группой, то для любой перестановки существует обратная. Так как любая перестановка имеет свою матрицу перестановки, то утверждение о существовании обратной матрицы перестановки также справедливо.
 
}}
 
}}
 
{{Утверждение|statement=Для любой матрицы перестановок <tex>P</tex> справедливо:
 
{{Утверждение|statement=Для любой матрицы перестановок <tex>P</tex> справедливо:
<center><tex>P^T P = P P^T = E</tex></center> где <tex>E</tex> - единичная матрица
+
<center><tex>P^T P = P P^T = E</tex></center> где <tex>E</tex> - единичная матрица.
 
|proof=
 
|proof=
 
Так же следует из того что перестановки являются группой.}}
 
Так же следует из того что перестановки являются группой.}}
  
{{Утверждение|statement=Произведение матриц перестановок есть матрица перестановок
+
{{Утверждение|statement=Произведение матриц перестановок есть матрица перестановок.
 
|proof=
 
|proof=
 
Произведение перестановок есть перестановка, значит и произведение матриц перестановок есть матрица перестановок.}}
 
Произведение перестановок есть перестановка, значит и произведение матриц перестановок есть матрица перестановок.}}
Строка 70: Строка 70:
 
{{Утверждение|statement=
 
{{Утверждение|statement=
 
Умножение произвольной матрицы <tex>A</tex> на перестановочную соответственно меняет местами её столбцы.
 
Умножение произвольной матрицы <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>:
Строка 80: Строка 80:
 
}}
 
}}
  
{{Утверждение|statement=Квадрат элементарной матрицы перестановок есть единичная матрица
+
{{Утверждение|statement=Квадрат элементарной матрицы перестановок есть единичная матрица.
 
}}
 
}}
  
{{Утверждение|statement=Матрица перестановок  <tex>n</tex>-го порядка может быть представлена в виде произведения <tex>(n - 1)</tex> элементарных матриц перестановок
+
{{Утверждение|statement=Матрица перестановок  <tex>n</tex>-го порядка может быть представлена в виде произведения <tex>(n - 1)</tex> элементарных матриц перестановок.
|proof=
+
}}
Перестановка  <tex>n</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>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>,  

Версия 04:11, 23 декабря 2011

Определение

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


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


Каждая матрица перестановки размера [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_{\sigma \circ \pi}[/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]\sigma[/math], где на [math]i[/math] - том месте стоит элемент [math]k[/math], на перестановку [math]\pi[/math], где на [math]k[/math] - том месте стоит элемент [math]j[/math], то в полученной перестановке [math]{\sigma \circ \pi}[/math] на [math]i[/math] - том месте будет стоять элемент [math]j[/math]. В результате если [math]{(P_\sigma P_\pi)}_{i,j} = 1[/math], то [math]({P_{\sigma \circ \pi}})_{i,j} = 1[/math]. Аналогичные рассуждения можно провести когда [math]{(P_\sigma P_\pi)}_{i,j} = 0[/math], и также получим, что [math]({P_{\sigma \circ \pi}})_{i,j} = 0[/math]. Поэтому для любых [math]i,j[/math] справедливо [math]{(P_\sigma P_\pi)}_{i,j} = ({P_{\sigma \circ \pi}})_{i,j}[/math], а раз такое равентсво выполняется, то [math]P_\sigma P_\pi = P_{\sigma \circ \pi}[/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]\triangleleft[/math]
Утверждение:
Произведение матриц перестановок есть матрица перестановок.
[math]\triangleright[/math]
Произведение перестановок есть перестановка, значит и произведение матриц перестановок есть матрица перестановок.
[math]\triangleleft[/math]
Утверждение:
Умножение произвольной матрицы [math]A[/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]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],

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

Ссылки