Материал из Викиконспекты
Определение
| Определение: |
| Матрица перестановки — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица. |
Каждая матрица перестановки размера [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]-й элемент которого равен 1, а остальные равны
нулю.
Пример
Перестановка:
- [math]\pi = \begin{pmatrix}
1 && 2 && 3 && 4\\
4 && 2 && 1 && 3
\end{pmatrix}[/math]
Соответствующая матрица:
- [math]P = \begin{pmatrix}
0 && 0 && 0 && 1 \\
0 && 1 && 0 && 0 \\
1 && 0 && 0 && 0 \\
0 && 0 && 1 && 0 \\
\end{pmatrix}[/math]
Свойства
- Для любых двух перестановок [math]\sigma, \pi[/math] их матрицы обладают свойством:
- [math]P_\sigma P_\pi = P_{\sigma \circ \pi}[/math]
- Матрицы перестановки ортогональны, так что для каждой такой матрицы существует обратная:
- [math]P_\sigma^{-1} = P_\sigma^T[/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} \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].
Видно, что вторая и третья строки поменялись местами.
Ссылки
