В двухстрочной таблице каждому числу сопоставлено ровно одно число. Теперь можно выполнить одно соответствие, а затем другое. Например, если первый шаг отправил 1 в 3, а второй отправляет 3 в 2, то результат двух шагов отправит 1 в 2.
Наше правило записи
В §23 мы назвали двухстрочную таблицу подстановкой. При изучении произведения ту же таблицу можно назвать перестановкой как отображением: она взаимно однозначно переставляет элементы Nn. Это отличается от перестановки-списка (i1,…,in) из §22, где важен порядок записи чисел. Здесь слово «подстановка» будет означать именно двухстрочное соответствие.
Каноническую таблицу
π=(1a12a2⋯⋯nan)
удобно читать как правило: π(k)=ak. Например,
π=(122331)⟺π(1)=2,π(2)=3,π(3)=1.
Каждое число 1,…,n встречается среди выходов один раз, поэтому подстановка переводит Nn в себя взаимно однозначно.
Произведение: сначала левый множитель
Примем следующий порядок действий:
(σπ)(i)=π(σ(i)).
Чтобы вычислить σπ, сначала применяем левую подстановку σ, затем правуюπ. Поэтому в записи πσ порядок другой:
(πσ)(i)=σ(π(i)).
Это определение произведения. В других книгах для композиции отображений встречается и обратный порядок записи; в этом уроке все вычисления идут по приведённому правилу. Обычное умножение чисел здесь не подразумевается.
Почему результат опять подстановка? Разные входы после σ дают разные промежуточные числа, а после π они остаются разными. Поскольку входов и выходов по n, каждое число Nn вновь встречается среди выходов ровно один раз. Следовательно, таблица произведения допустима.
Вычислим оба порядка
Возьмём подстановки:
σ=(132231),π=(122331).
Для σπ проследим путь каждого входа:
Вход i
Сначала σ(i)
Затем π(σ(i))
1
3
π(3)=1
2
2
π(2)=3
3
1
π(1)=2
Итак,
σπ=(112332).
Теперь переставим множители. В πσ первым действует π, затем σ:
Порядок множителей в общем случае менять нельзя. При этом порядок столбцов внутри каждой таблицы можно менять, если двигать столбцы целиком: соответствия σ(i) и π(i) от этого не меняются, значит, не меняется и произведение.
Свойство 24.1, ассоциативность. Для любых π,σ,ρ на одном Nn выполняется
(πσ)ρ=π(σρ).
Докажем равенство по действию на произвольное число i. В левой записи сначала действует π, затем σ, затем ρ:
((πσ)ρ)(i)=ρ((πσ)(i))=ρ(σ(π(i))).
В правой записи сначала действует π, после неё произведение σρ:
(π(σρ))(i)=(σρ)(π(i))=ρ(σ(π(i))).
Для каждого i получился один и тот же результат. Значит, подстановки равны. Скобки в произведении трёх или более подстановок можно опускать, сохраняя порядок множителей. Ассоциативность не означает, что можно поменять множители местами.
Нейтральная и обратная подстановки
Определение 24.2. Тождественная подстановка ε оставляет каждое число на месте:
ε=(1122⋯⋯nn),ε(i)=i.
Если переставить её столбцы целиком, обе строки по-прежнему совпадут и подстановка останется той же.
Свойство 24.2, нейтральность. Применение ε до или после π не меняет результат:
πε=επ=π.
Действительно, по принятому порядку
(επ)(i)=π(ε(i))=π(i), а
(πε)(i)=ε(π(i))=π(i).
Свойство 24.3. У каждой подстановки π существует обратная π−1, для которой
ππ−1=π−1π=ε.
Если π сопоставляет i числу j, обратная возвращает j к i. Для её записи достаточно поменять строки таблицы местами целиком, а при желании затем расположить столбцы в каноническом порядке:
π=(122331),π−1=(213213)=(132132).
Проверим обе стороны, не полагаясь только на рисунок таблицы. Если π(i)=j, то π−1(j)=i. Следовательно,
(ππ−1)(i)=π−1(π(i))=i.
И наоборот, если π−1(j)=i, то π(i)=j, поэтому
(π−1π)(j)=π(π−1(j))=j.
Оба произведения действуют как ε на каждом числе. Например, в нашем случае 1π2π−11 и 2π−11π2.
Проверь себя
Пусть
α=(122133),β=(112332).
Какая подстановка действует первой в αβ? Найди αβ.
Найди βα. Совпало ли произведение с ответом пункта 1?
Чему равна α−1?
Показать решение
1. Первой действует α. Пути 1→2→3, 2→1→1, 3→3→2 дают αβ=(132132).
2. Для βα пути дают 1→1→2, 2→3→3, 3→2→1. Поэтому βα=(122331); произведения различаются.
3.α меняет 1 и 2, а 3 оставляет на месте. Повторное применение возвращает все числа, значит, α−1=α.