Теоремы о транспозиции

Теоремы о транспозиции

Прежде чем мы будем рассматривать теоремы о транспозиции, попытаемся сформулировать само понятие транспозиции. Транспозицией называется перемена местами двух элементов перестановки .

Теорема 1

Все  n! перестановок длин  n можно расположить одну за другой так, что каждая последующая получается из предыдущей  1 (одной) транспозицией, начинать можно с любой перестановки.

Доказательство

Доказательство будем проводить индукцией по  n.
База индукции:  n= 2, то получаем перестановки  (1, 2), (2, 1), тогда расположения будут иметь вид  (1, 2, 2, 1) и  (2, 1, 1, 2), теорема справедлива.
Предположение индукции:  n \le m,  m \ge 2.
Шаг индукции:  n= m+1  (i_1, i_2,, i_{m+1}). Рассмотрим все перестановки, где на первом месте стоит  i_1.
(i_1, {i`}_2,, {i`}_{m+1});
({i`}_2, i_1,, {i`}_{m+1});
({i`}_2, {i`}_1,, {i``}_{m+1});
Таких  m!(m+1)= (m+1)! перестановок.
Следствие:
Пусть  n \ge 2 , тогда число  \frac{n!}{2} чётных равно числу  \frac{n!}{2} нечётных перестановок.

Для следующей теоремы нам понадобятся знания таких понятий, как “инверсия”, “чётность перестановок”.

Теорема 2

Любая транспозиция меняет чётность перестановки.

Доказательство

Рассмотрим перестановку …, i, j, …, где  i и  j транспонируемые символы, стоящие рядом. В результате транспозиции получим новую перестановку …, j, i , …, при этом в данных перестановках каждый из символов  i и  j составит одинаковые инверсии с символами, остающимися на месте, количество таких инверсий  n. В случае, если до этого  i и  j не составляли инверсий, то с новой перестановкой появится и новая инверсия (число инверсий будет равным  n+1 ), в противном случае, число инверсий на  1 уменьшиться. И в том и в другом случаях чётность перестановки меняется.
Теперь рассмотрим вариант, когда между  i,  j расположено s символов  (s>0) , т.е. перестановка имеет вид … i, k_1, k_2, …,  k_s, j,…. Транспозицию символов  i,  j получим последовательным выполнением  2s+1 транспозиции элементов, стоящих рядом. В итоге, мы меняем четность перестановки нечетное число раз, и по-этому перестановки
…,  i, k_1, k_2, …,  k_s, j,… и …,  j, k_1, k_2, …,  k_s, i,… будут противоположной чётности.

Пример

 (2,5,4,1,3) \Rightarrow (1,5,4,2,3) \Rightarrow (1,2,4,5,3) \Rightarrow
 (1,2,3,5,4) \Rightarrow (1,2,3,4,5).
Здесь, перестановка (2,5,4,1,3) приведена к начальной за  4 транспозиции и она четная, т.к.  \tau(2,5,4,1,3)= 6

Тест о теоремах о транспозиции

Данный тест поможет проверить, как вы усвоили материал данной статьи

Источники

  1. Г.С.Белозеров.Конспект лекций
  2. В.В.Воеводин. Линейная алгебра. Второе издание, физико-математическая литература, 1980. Стр. 122-124.
  3. А.Г.Курош. Курс линейной алгебры. Издание тринадцатое, 2004. Стр.28-37.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *