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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Применение)
(Свойства)
Строка 38: Строка 38:
  
 
* Для любых двух перестановок <tex>\sigma, \pi</tex> их матрицы обладают свойством:
 
* Для любых двух перестановок <tex>\sigma, \pi</tex> их матрицы обладают свойством:
*: <tex>P_\sigma P_\pi = P_{\sigma \circ \pi}</tex>
+
*: <tex>P_\sigma P_\pi = P_{\sigma \circ \pi}</tex> , где <tex>\circ</tex> - операция умножения двух перестановок
* Матрицы перестановки ортогональны, так что для каждой такой матрицы существует обратная:
+
* Для любой матрицы перестановок существует обратная:
*: <tex>P_\sigma^{-1} = P_\sigma^T</tex>
+
*: <tex>P_\sigma^{-1} = P_\sigma^T</tex> , где <tex>P^T</tex> - транспонированная матрица <tex>P</tex>
 +
* Для любой матрицы перестановок справедливо:
 +
*: <tex>P^T P = P P^T = E</tex> , где <tex>E</tex> - единичная матрица
 +
* Произведение матриц перестановок одного и того же порядка есть матрица перестановок
 +
* Матрица перестановок  <tex>n</tex>-го порядка может быть представлена в виде произведения <tex>(n - 1)</tex> элементарных матриц перестановок
 +
* Квадрат элементарной матрицы перестановок есть единичная матрица
 
* Умножение произвольной матрицы <tex>M</tex> на перестановочную соответственно меняет местами её столбцы.
 
* Умножение произвольной матрицы <tex>M</tex> на перестановочную соответственно меняет местами её столбцы.
 
* Умножение перестановочной матрицы на произвольную <tex>M</tex> меняет местами строки в <tex>M</tex>.
 
* Умножение перестановочной матрицы на произвольную <tex>M</tex> меняет местами строки в <tex>M</tex>.

Версия 07:20, 21 декабря 2011

Определение

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


Каждая матрица перестановки размера [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]P_\sigma^{-1} = P_\sigma^T[/math] , где [math]P^T[/math] - транспонированная матрица [math]P[/math]
  • Для любой матрицы перестановок справедливо:
    [math]P^T P = P P^T = E[/math] , где [math]E[/math] - единичная матрица
  • Произведение матриц перестановок одного и того же порядка есть матрица перестановок
  • Матрица перестановок [math]n[/math]-го порядка может быть представлена в виде произведения [math](n - 1)[/math] элементарных матриц перестановок
  • Квадрат элементарной матрицы перестановок есть единичная матрица
  • Умножение произвольной матрицы [math]M[/math] на перестановочную соответственно меняет местами её столбцы.
  • Умножение перестановочной матрицы на произвольную [math]M[/math] меняет местами строки в [math]M[/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],

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

Ссылки