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




Главная
Новости
Статьи
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




02.03.2021


02.03.2021


01.03.2021


01.03.2021


28.02.2021


27.02.2021


26.02.2021


26.02.2021


25.02.2021


25.02.2021





Яндекс.Метрика
         » » Матрица перестановки

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

01.01.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.