Матрица перестановки (или подстановки) — квадратная бинарная матрица, в каждой строке и столбце которой находится ровно один единичный элемент. Каждая матрица перестановки размера n × n {displaystyle n imes n} является матричным представлением перестановки из n {displaystyle n} элементов.
Определение
Пусть дана перестановка σ {displaystyle sigma } из n {displaystyle n} элементов:
( 1 2 … n σ ( 1 ) σ ( 2 ) … σ ( n ) ) {displaystyle {egin{pmatrix}1&&2&&ldots &&nsigma (1)&&sigma (2)&&ldots &&sigma (n)end{pmatrix}}}Соответствующей матрицей перестановки является матрица n × n {displaystyle n imes n} вида:
P σ = ( e σ ( 1 ) e σ ( 2 ) ⋮ e σ ( n ) ) , {displaystyle P_{sigma }={egin{pmatrix}mathbf {e} _{sigma (1)}mathbf {e} _{sigma (2)}vdots mathbf {e} _{sigma (n)}end{pmatrix}},}где e i {displaystyle mathbf {e} _{i}} — вектор размерности n {displaystyle n} , i {displaystyle i} -й элемент которого равен 1, а остальные равны нулю.
Пример
Перестановка:
π = ( 1 2 3 4 4 2 1 3 ) {displaystyle pi ={egin{pmatrix}1&&2&&3&&44&&2&&1&&3end{pmatrix}}}Соответствующая матрица:
P = ( 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 ) {displaystyle P={egin{pmatrix}0&&0&&1&&0 &&1&&0&&0 &&0&&0&&11&&0&&0&&0end{pmatrix}}}Свойства
- Для любых двух перестановок σ , π {displaystyle sigma ,pi } их матрицы обладают свойством: P π P σ = P σ ∘ π . {displaystyle P_{pi }P_{sigma }=P_{sigma circ pi }.}
- Матрицы перестановки ортогональны, так что для каждой такой матрицы существует обратная: P σ − 1 = P σ T . {displaystyle P_{sigma }^{-1}=P_{sigma }^{T}.}
- Умножение произвольной матрицы M {displaystyle M} на перестановочную соответственно меняет местами её столбцы.
- Умножение перестановочной матрицы на произвольную M {displaystyle M} меняет местами строки в M {displaystyle M} .
- Определитель перестановочной матрицы равен чётности перестановки. Определитель чётной перестановки равен 1, определитель нечётной перестановки - -1.