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

13.03.2021

Матрица перестановки (или подстановки) — квадратная бинарная матрица, в каждой строке и столбце которой находится ровно один единичный элемент. Каждая матрица перестановки размера 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.


Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru © 2020
При цитировании и использовании любых материалов ссылка на сайт обязательна