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

Содержание

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

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

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

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

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

где [math]\mathbf{e}_{i}[/math] — вектор длины [math]n[/math], [math]i[/math]-й элемент которого равен 1, а остальные равны

нулю.

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

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

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

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

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

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

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