Матрица перестановки

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Ма́трица перестано́вки (или подстано́вки) — квадратная бинарная матрица, в каждой строке и столбце которой находится лишь один единичный элемент. Каждая матрица перестановки размера n \times n является матричным представлением перестановки порядка n.

Определение[править | править вики-текст]

Пусть дана перестановка \sigma порядка n:

\begin{pmatrix}
1 && 2&& \ldots && n\\
\sigma(1)&& \sigma(2) && \ldots && \sigma(n)
\end{pmatrix}

Соответствующей матрицей перестановки является матрица n \times n вида:

P_\sigma = \begin{pmatrix}
\mathbf{e}_{\sigma(1)}\\
\mathbf{e}_{\sigma(2)}\\
\vdots \\
\mathbf{e}_{\sigma(n)}
\end{pmatrix},

где \mathbf{e}_{i}вектор длины n, i-й элемент которого равен 1, а остальные равны нулю.

Пример[править | править вики-текст]

Перестановка:

\pi = \begin{pmatrix}
1 && 2 && 3 && 4\\
4 && 2 && 1 && 3
\end{pmatrix}

Соответствующая матрица:

P = \begin{pmatrix}
0 && 0 && 0 && 1 \\
0 && 1 && 0 && 0 \\
1 && 0 && 0 && 0 \\
0 && 0 && 1 && 0 \\
\end{pmatrix}

Свойства[править | править вики-текст]

  • Для любых двух перестановок \sigma, \pi их матрицы обладают свойством:

' Pπ Pσ = Pσ o π

  • Матрицы перестановки ортогональны, так что для каждой такой матрицы существует обратная:
    P_\sigma^{-1} = P_\sigma^T
  • Умножение произвольной матрицы M на перестановочную соответственно меняет местами её столбцы.
  • Умножение перестановочной матрицы на произвольную M меняет местами строки в M.
  • Определитель перестановочной матрицы равен чётности перестановки. Определитель чётной перестановки равен 1, определитель нечётной перестановки - -1.