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

Определение

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

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

Каждая матрица перестановки размера [math]n \times n[/math] является матричным представлением перестановки порядка [math]n[/math].

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

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

, где — двоичный вектор длины , -й элемент которого равен единице, а остальные равны нулю.

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

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

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

Благодаря последним свойствам, матрицам перестановок нашлось применение в линейной алгебре:

пусть задана матрица перестановки (она соответствует перестановке ), и матрица ,

тогда перемножив получим:

видно, что вторая и третья строки поменялись местами;

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