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

Определение

Определение:

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

Определение:

Если матрица перестановок [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_{k = 1}^{n}{({P_\sigma}_{i,k} {P_\pi}_{k,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]\triangleleft[/math]

// разработка

• Для любой матрицы перестановок существует обратная:

  [math]P_\sigma^{-1} = P_\sigma^T[/math] , где [math]P^T[/math] - транспонированная матрица [math]P[/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],

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

Ссылки

• Матрица перестановки — Википедия
• Матрица перестановки