bulgakov

04. Произведение подстановок: порядок действий

В двухстрочной таблице каждому числу сопоставлено ровно одно число. Теперь можно выполнить одно соответствие, а затем другое. Например, если первый шаг отправил 11 в 33, а второй отправляет 33 в 22, то результат двух шагов отправит 11 в 22.

Наше правило записи

В §23 мы назвали двухстрочную таблицу подстановкой. При изучении произведения ту же таблицу можно назвать перестановкой как отображением: она взаимно однозначно переставляет элементы NnN_n. Это отличается от перестановки-списка (i1,…,in)(i_1,\ldots,i_n) из §22, где важен порядок записи чисел. Здесь слово «подстановка» будет означать именно двухстрочное соответствие.

Каноническую таблицу

π=(12⋯na1a2⋯an)\pi= \begin{pmatrix} 1&2&\cdots&n\\ a_1&a_2&\cdots&a_n \end{pmatrix}

удобно читать как правило: π(k)=ak\pi(k)=a_k. Например,

π=(123231)⟺π(1)=2, π(2)=3, π(3)=1.\pi=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} \quad\Longleftrightarrow\quad \pi(1)=2,\ \pi(2)=3,\ \pi(3)=1.

Каждое число 1,…,n1,\ldots,n встречается среди выходов один раз, поэтому подстановка переводит NnN_n в себя взаимно однозначно.

Произведение: сначала левый множитель

Примем следующий порядок действий:

(σπ)(i)=π(σ(i)).\boxed{(\sigma\pi)(i)=\pi(\sigma(i)).}

Чтобы вычислить σπ\sigma\pi, сначала применяем левую подстановку σ\sigma, затем правую π\pi. Поэтому в записи πσ\pi\sigma порядок другой:

(πσ)(i)=σ(π(i)).(\pi\sigma)(i)=\sigma(\pi(i)).

Это определение произведения. В других книгах для композиции отображений встречается и обратный порядок записи; в этом уроке все вычисления идут по приведённому правилу. Обычное умножение чисел здесь не подразумевается.

Почему результат опять подстановка? Разные входы после σ\sigma дают разные промежуточные числа, а после π\pi они остаются разными. Поскольку входов и выходов по nn, каждое число NnN_n вновь встречается среди выходов ровно один раз. Следовательно, таблица произведения допустима.

Вычислим оба порядка

Возьмём подстановки:

σ=(123321),π=(123231).\sigma=\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}, \qquad \pi=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}.

Для σπ\sigma\pi проследим путь каждого входа:

Вход ii Сначала σ(i)\sigma(i) Затем π(σ(i))\pi(\sigma(i))
11 33 π(3)=1\pi(3)=1
22 22 π(2)=3\pi(2)=3
33 11 π(1)=2\pi(1)=2

Итак,

σπ=(123132).\sigma\pi=\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}.

Теперь переставим множители. В πσ\pi\sigma первым действует π\pi, затем σ\sigma:

(πσ)(1)=σ(π(1))=σ(2)=2,(πσ)(2)=σ(π(2))=σ(3)=1,(πσ)(3)=σ(π(3))=σ(1)=3.\begin{aligned} (\pi\sigma)(1)&=\sigma(\pi(1))=\sigma(2)=2,\\ (\pi\sigma)(2)&=\sigma(\pi(2))=\sigma(3)=1,\\ (\pi\sigma)(3)&=\sigma(\pi(3))=\sigma(1)=3. \end{aligned}

Значит,

πσ=(123213)≠(123132)=σπ.\pi\sigma=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix} \ne \begin{pmatrix}1&2&3\\1&3&2\end{pmatrix} =\sigma\pi.

Порядок множителей в общем случае менять нельзя. При этом порядок столбцов внутри каждой таблицы можно менять, если двигать столбцы целиком: соответствия σ(i)\sigma(i) и π(i)\pi(i) от этого не меняются, значит, не меняется и произведение.

В интерактивной модели композиции можно выбрать входное число и проследить оба шага по таблицам.

Скобки можно расставлять по-разному

Свойство 24.1, ассоциативность. Для любых π,σ,ρ\pi,\sigma,\rho на одном NnN_n выполняется

(πσ)ρ=π(σρ).(\pi\sigma)\rho=\pi(\sigma\rho).

Докажем равенство по действию на произвольное число ii. В левой записи сначала действует π\pi, затем σ\sigma, затем ρ\rho:

((πσ)ρ)(i)=ρ((πσ)(i))=ρ(σ(π(i))).((\pi\sigma)\rho)(i) =\rho((\pi\sigma)(i)) =\rho(\sigma(\pi(i))).

В правой записи сначала действует π\pi, после неё произведение σρ\sigma\rho:

(π(σρ))(i)=(σρ)(π(i))=ρ(σ(π(i))).(\pi(\sigma\rho))(i) =(\sigma\rho)(\pi(i)) =\rho(\sigma(\pi(i))).

Для каждого ii получился один и тот же результат. Значит, подстановки равны. Скобки в произведении трёх или более подстановок можно опускать, сохраняя порядок множителей. Ассоциативность не означает, что можно поменять множители местами.

Нейтральная и обратная подстановки

Определение 24.2. Тождественная подстановка ε\varepsilon оставляет каждое число на месте:

ε=(12⋯n12⋯n),ε(i)=i.\varepsilon= \begin{pmatrix} 1&2&\cdots&n\\ 1&2&\cdots&n \end{pmatrix}, \qquad \varepsilon(i)=i.

Если переставить её столбцы целиком, обе строки по-прежнему совпадут и подстановка останется той же.

Свойство 24.2, нейтральность. Применение ε\varepsilon до или после π\pi не меняет результат:

πε=επ=π.\pi\varepsilon=\varepsilon\pi=\pi.

Действительно, по принятому порядку (επ)(i)=π(ε(i))=π(i)(\varepsilon\pi)(i)=\pi(\varepsilon(i))=\pi(i), а (πε)(i)=ε(π(i))=π(i)(\pi\varepsilon)(i)=\varepsilon(\pi(i))=\pi(i).

Свойство 24.3. У каждой подстановки π\pi существует обратная π−1\pi^{-1}, для которой

ππ−1=π−1π=ε.\pi\pi^{-1}=\pi^{-1}\pi=\varepsilon.

Если π\pi сопоставляет ii числу jj, обратная возвращает jj к ii. Для её записи достаточно поменять строки таблицы местами целиком, а при желании затем расположить столбцы в каноническом порядке:

π=(123231),π−1=(231123)=(123312).\pi=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}, \qquad \pi^{-1} =\begin{pmatrix}2&3&1\\1&2&3\end{pmatrix} =\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}.

Проверим обе стороны, не полагаясь только на рисунок таблицы. Если π(i)=j\pi(i)=j, то π−1(j)=i\pi^{-1}(j)=i. Следовательно,

(ππ−1)(i)=π−1(π(i))=i.(\pi\pi^{-1})(i)=\pi^{-1}(\pi(i))=i.

И наоборот, если π−1(j)=i\pi^{-1}(j)=i, то π(i)=j\pi(i)=j, поэтому

(π−1π)(j)=π(π−1(j))=j.(\pi^{-1}\pi)(j)=\pi(\pi^{-1}(j))=j.

Оба произведения действуют как ε\varepsilon на каждом числе. Например, в нашем случае 1→π2→π−111\xrightarrow{\pi}2\xrightarrow{\pi^{-1}}1 и 2→π−11→π22\xrightarrow{\pi^{-1}}1\xrightarrow{\pi}2.

Проверь себя

Пусть

α=(123213),β=(123132).\alpha=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}, \qquad \beta=\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}.
  1. Какая подстановка действует первой в αβ\alpha\beta? Найди αβ\alpha\beta.
  2. Найди βα\beta\alpha. Совпало ли произведение с ответом пункта 1?
  3. Чему равна α−1\alpha^{-1}?
Показать решение

1. Первой действует α\alpha. Пути 1→2→31\to2\to3, 2→1→12\to1\to1, 3→3→23\to3\to2 дают αβ=(123312)\alpha\beta=\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}.

2. Для βα\beta\alpha пути дают 1→1→21\to1\to2, 2→3→32\to3\to3, 3→2→13\to2\to1. Поэтому βα=(123231)\beta\alpha=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}; произведения различаются.

3. α\alpha меняет 11 и 22, а 33 оставляет на месте. Повторное применение возвращает все числа, значит, α−1=α\alpha^{-1}=\alpha.

ПрактикаЗагружаем тест…