06. Транспозиции: обмен двух чисел
Самая простая нетривиальная подстановка меняет местами ровно два числа, а остальные оставляет на месте. Из таких обменов можно собрать любую подстановку — так же, как колоду карт можно упорядочить, меняя местами по две карты.
Транспозиция
Столбец вида называют тождественным: число остаётся на месте. У тождественной подстановки все столбцы тождественны, и это единственная такая подстановка. Если подстановка не тождественна, у неё не меньше двух нетождественных столбцов. Пусть переходит в . Тогда уже не может перейти в себя: число в нижней строке стоит под , а повторяться там числа не могут. Значит, столбец с верхним числом тоже нетождественный.
Определение 26.1. Подстановку, которая получается из обменом двух чисел и в нижней строке, называют транспозицией и обозначают или просто :
Например, при
Она переводит и , а числа и оставляет на месте.
Три свойства, которые нужно помнить
Свойство 26.1. Каждая транспозиция нечётна: .
Нижняя строка не имеет инверсий, чётна. Транспозиция получается одним обменом двух чисел в этой строке, а по теореме 22.1 один обмен меняет чётность. Проверим на : в нижней строке три инверсии — , , . Значит, знак .
Свойство 26.2. и . Второй обмен возвращает числа на места, поэтому
Свойство 26.3. Умножение на транспозицию — это обмен в одной строке таблицы. Напомним правило курса: в произведении сначала действует левый множитель.
- — сначала обмен, потом . В таблице меняются местами числа и в верхней строке.
- — сначала , потом обмен. В таблице меняются местами числа и в нижней строке.
Проверим на :
По определению произведения: и . Оба результата совпали с таблицами.
Любая подстановка — произведение транспозиций
Теорема 26.1. Каждая подстановка равна произведению конечного числа транспозиций. Можно обойтись не более чем транспозициями.
Идея доказательства — сортировка обменами. Начнём с . По свойству 26.3 умножение справа на меняет местами числа и в нижней строке. Идём по местам слева направо и каждый раз ставим на место нужное число одним обменом. Когда правильны первые мест, последнее место заполнено единственным оставшимся числом и тоже правильно. Поэтому обменов не больше . Для самой можно написать .
Пример. Разложим . Следим за нижней строкой:
| Шаг | Что нужно | Обмен справа | Нижняя строка |
|---|---|---|---|
| старт | — | — | |
| место 1 | число | ||
| место 2 | число | ||
| место 3 | число |
Итак, . Проверим вход : переводит , затем даёт , затем даёт . Получили .
Знак через число транспозиций
Следствие 26.1. Если , где все — транспозиции, то
По теореме 25.1 знак произведения равен произведению знаков, а каждый множитель даёт . В примере выше , поэтому . Проверка инверсиями: в инверсии , , — их три, подстановка нечётна.
Разложение на транспозиции не единственно: например, . Число множителей может быть разным, но его чётность у одной подстановки всегда одна и та же — её определяет знак.
Проверь себя
- Запиши таблицей. Каков её знак?
- Разложи в произведение транспозиций и найди .
- Что произойдёт с таблицей при умножении справа на ?
Показать решение
1. . В нижней строке одна инверсия , знак — как у любой транспозиции.
2. Из : на место 1 нужно — обмен даёт ; на место 2 нужно — обмен даёт . Значит, , два множителя, . Проверка: в две инверсии.
3. Умножение справа меняет числа и в нижней строке: . Получаем .
