ФЭНДОМ


Матрица перестановки (или подстановки) — квадратная бинарная матрица, в каждой строке и столбце которой находится лишь один единичный элемент. Каждая матрица перестановки размера 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}_{\pi(1)}\\
\mathbf{e}_{\pi(2)}\\
\vdots \\
\mathbf{e}_{\pi(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_\sigma P_\pi = P_{\sigma \circ \pi}

Матрицы перестановки ортогональны, так что для каждой такой матрицы существует обратная:

P_\sigma^{-1} = P_\sigma^T

Умножение произвольной матрицы M на перестановочную соответственно меняет местами её строки.

Умножение перестановочной матрицы на произвольную M меняет местами столбцы в M.



Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Матрица перестановки. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .


Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики