113
правок
Изменения
Нет описания правки
Так как перестановки являются группой, то для любой перестановки существует обратная. Так как любая перестановка имеет свою матрицу перестановки, то утверждение о существовании обратной матрицы перестановки также справедливо.
}}
{{Утверждение|statement=Для любой матрицы перестановок <tex>P</tex> справедливо:
<center><tex>P^T P = P P^T = E</tex></center> где <tex>E</tex> — единичная матрица.
Теперь в обратную сторону <tex>{(P^T P)}_{ij} = \sum\limits_{k = 1}^{n}{(P^T)}_{ik} {(P)}_{kj} = \sum\limits_{k=1}^{n} {(P)}_{ki} {(P)}_{kj} = {\delta}_{ij} = {E} </tex>
где <tex> {\delta}_{ij} </tex> — символ Кронекера. }}
{{Утверждение|statement=Произведение матриц перестановок есть матрица перестановок.
|proof=
Каждой матрице перестановок соответствует своя перестановка. Так как произведение перестановок также дает перестановку, значит и произведение матриц перестановок есть такая же матрица.}}
{{Утверждение|statement=
При умножение слева элементарной матрицы перестановок <tex> {P}_{ij} </tex> на матрицу <tex>A </tex> происходит перестановка <tex> {i} </tex> - й и <tex> {j} </tex> - й строк матрицы <tex>A</tex>. Умножение справа элементарной матрицы перестановок <tex> {P}_{ij} </tex> на матрицу <tex>A </tex> приводит к перестановке <tex> {i} </tex> - го и <tex> {j} </tex> - го столбцов матрицы <tex>A</tex>.
|proof=
Рассмотрим сначала умножение слева, т.е. матрицу <tex> {P}_{ij}{A} </tex>, которую обозначим <tex> {B} = {b}_{kl} </tex>. Посчитаем чему равны элементы этой матрицы:
\end {cases} </tex>
Действительно, по определению элементарной матрицы перестановок единица в строке стоит на <tex> {k} </tex> - м месте, если , <tex> {k \ne i,j} </tex>, на <tex> {j} </tex> - м месте, если <tex> {k = i} </tex>, и на <tex> {i} </tex> - м месте, если <tex> {k = j} </tex>. Итак, если <tex> {k \ne i,j} </tex>, то <tex> {k} </tex> - я строка матрицы <tex>B </tex> просто совпадает с <tex> {k} </tex> - й строкойматрицы <tex>A</tex>. Далее, <tex> {i} </tex> - я строка матрицы <tex>B </tex> совпадает с <tex> {j} </tex> - й строкой матрицы <tex>A</tex>, инаоборот. Поэтому <tex>B </tex> получается из <tex>A </tex> перестановкой <tex> {i} </tex> - й и <tex> {j} </tex> - й строк.
Теперь рассмотрим умножение справа. Пусть <tex> {B} = {A}{P}_{ij} </tex>.
\end {cases} </tex>
По определению элементарной матрицы перестановок единица в столбце стоит на <tex> {l} </tex> - м месте, если <tex> {l \ne i,j} </tex>, на <tex> {j} </tex> - м месте,
если <tex> {l = i} </tex>, и на <tex> {i} </tex> - м месте, если <tex> {l = j} </tex>.
Итак, если <tex> {l \ne i,j} </tex>, то <tex> {l} </tex> - й столбец матрицы B просто совпадает с <tex> {l} B</tex> - м столбцомматрицы A. Далее, <tex> {i} </tex> - й столбец матрицы B просто совпадает с <tex> {jl} </tex> - м столбцом матрицы A, инаоборот. Поэтому B получается из A перестановкой <tex> {i} </tex> - го и <tex> {j} </tex> - го столбцов.}} {{Утверждение|statement=Умножение справа матрицы перестановок на произвольной матрицу <tex>A</tex> соответственно меняет местами её столбцы.Умножение слева матрицы перестановок на произвольную матрицу <tex>A</tex> меняет местами строки в этой матрице.|proof=Рассмотрим произвольную матрицу <tex>A</tex> и матрицу перестановки <tex>P</tex>:возьмем Далее, <tex>{i} </tex> - тую строчку матрицы <tex>A</tex> и умножим на <tex>j</tex> - тый столбец <tex>P</tex>,так как <tex>j</tex> - тый й столбец матрицы <tex>PB</tex> это двоичный вектор совпадает с одной единицей, то от <tex>i{j} </tex> - той строчки м столбцом матрицы <tex>A</tex> выживет один элемент, причем на <tex>j</tex> - том местеинаоборот.Умножив Поэтому <tex>iB</tex> - тую строчку матрицы получается из <tex>A</tex>, на остальные столбцы матрицы <tex>P</tex>, получим, что в перестановкой <tex>{i} </tex> - той строке матрицы го и <tex>A{j} </tex> элементы поменяются местами. Умножая другие строки матрицы <tex>A</tex>, будем наблюдать похожее (так как умножаем на те же самые столбцы матрицы <tex>P</tex>). Таким образом получим, что в матрице <tex>A</tex> столбцы поменялись местами. Доказательство второго утверждения аналогично- го столбцов.
}}
*[http://portal.tpu.ru/SHARED/k/KONVAL/Sites/Russian_sites/1/23.htm Матрица перестановки]
*[https://en.wikipedia.org/wiki/Permutation_matrix Permutation matrix]
* Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Cambridge: Cambridge University Press. стр. 2, 19.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
