bulgakov

06. Транспозиции: обмен двух чисел

Самая простая нетривиальная подстановка меняет местами ровно два числа, а остальные оставляет на месте. Из таких обменов можно собрать любую подстановку — так же, как колоду карт можно упорядочить, меняя местами по две карты.

Транспозиция

Столбец вида (ii)\binom{i}{i} называют тождественным: число ii остаётся на месте. У тождественной подстановки ε\varepsilon все столбцы тождественны, и это единственная такая подстановка. Если подстановка не тождественна, у неё не меньше двух нетождественных столбцов. Пусть ii переходит в j≠ij\ne i. Тогда jj уже не может перейти в себя: число jj в нижней строке стоит под ii, а повторяться там числа не могут. Значит, столбец с верхним числом jj тоже нетождественный.

Определение 26.1. Подстановку, которая получается из ε\varepsilon обменом двух чисел ii и jj в нижней строке, называют транспозицией и обозначают [i j]n[i\,j]_n или просто [i j][i\,j]:

[i j]n=(1⋯i⋯j⋯n1⋯j⋯i⋯n).[i\,j]_n= \begin{pmatrix} 1&\cdots&i&\cdots&j&\cdots&n\\ 1&\cdots&j&\cdots&i&\cdots&n \end{pmatrix}.

Например, при n=4n=4

[2 4]=(12341432).[2\,4]=\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}.

Она переводит 2↦42\mapsto4 и 4↦24\mapsto2, а числа 11 и 33 оставляет на месте.

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

Свойство 26.1. Каждая транспозиция нечётна: s([i j])=−1s([i\,j])=-1.

Нижняя строка ε\varepsilon не имеет инверсий, ε\varepsilon чётна. Транспозиция получается одним обменом двух чисел в этой строке, а по теореме 22.1 один обмен меняет чётность. Проверим на [2 4][2\,4]: в нижней строке (1,4,3,2)(1,4,3,2) три инверсии — (4,3)(4,3), (4,2)(4,2), (3,2)(3,2). Значит, знак −1-1.

Свойство 26.2. [i j]=[j i][i\,j]=[j\,i] и [i j][i j]=ε[i\,j][i\,j]=\varepsilon. Второй обмен возвращает числа на места, поэтому

[i j]−1=[i j].[i\,j]^{-1}=[i\,j].

Свойство 26.3. Умножение на транспозицию — это обмен в одной строке таблицы. Напомним правило курса: в произведении сначала действует левый множитель.

  • [i j] π[i\,j]\,\pi — сначала обмен, потом π\pi. В таблице π\pi меняются местами числа ii и jj в верхней строке.
  • π [i j]\pi\,[i\,j] — сначала π\pi, потом обмен. В таблице π\pi меняются местами числа ii и jj в нижней строке.

Проверим на π=(123231)\pi=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}:

[1 2] π=(213231)=(123321),[1\,2]\,\pi=\begin{pmatrix}2&1&3\\2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}, π [1 2]=(123132).\pi\,[1\,2]=\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}.

По определению произведения: ([1 2]π)(1)=π(2)=3([1\,2]\pi)(1)=\pi(2)=3 и (π[1 2])(1)=[1 2](π(1))=[1 2](2)=1(\pi[1\,2])(1)=[1\,2](\pi(1))=[1\,2](2)=1. Оба результата совпали с таблицами.

Любая подстановка — произведение транспозиций

Теорема 26.1. Каждая подстановка равна произведению конечного числа транспозиций. Можно обойтись не более чем n−1n-1 транспозициями.

Идея доказательства — сортировка обменами. Начнём с ε\varepsilon. По свойству 26.3 умножение справа на [a b][a\,b] меняет местами числа aa и bb в нижней строке. Идём по местам слева направо и каждый раз ставим на место нужное число одним обменом. Когда правильны первые n−1n-1 мест, последнее место заполнено единственным оставшимся числом и тоже правильно. Поэтому обменов не больше n−1n-1. Для самой ε\varepsilon можно написать ε=[1 2][1 2]\varepsilon=[1\,2][1\,2].

Пример. Разложим π=(12343142)\pi=\begin{pmatrix}1&2&3&4\\3&1&4&2\end{pmatrix}. Следим за нижней строкой:

Шаг Что нужно Обмен справа Нижняя строка
старт — — (1,2,3,4)(1,2,3,4)
место 1 число 33 [1 3][1\,3] (3,2,1,4)(3,2,1,4)
место 2 число 11 [1 2][1\,2] (3,1,2,4)(3,1,2,4)
место 3 число 44 [2 4][2\,4] (3,1,4,2)(3,1,4,2)

Итак, π=[1 3][1 2][2 4]\pi=[1\,3][1\,2][2\,4]. Проверим вход 33: [1 3][1\,3] переводит 3↦13\mapsto1, затем [1 2][1\,2] даёт 1↦21\mapsto2, затем [2 4][2\,4] даёт 2↦42\mapsto4. Получили π(3)=4\pi(3)=4.

Знак через число транспозиций

Следствие 26.1. Если π=τ1τ2⋯τk\pi=\tau_1\tau_2\cdots\tau_k, где все τi\tau_i — транспозиции, то

s(π)=(−1)k.\boxed{s(\pi)=(-1)^k.}

По теореме 25.1 знак произведения равен произведению знаков, а каждый множитель даёт −1-1. В примере выше k=3k=3, поэтому s(π)=−1s(\pi)=-1. Проверка инверсиями: в (3,1,4,2)(3,1,4,2) инверсии (3,1)(3,1), (3,2)(3,2), (4,2)(4,2) — их три, подстановка нечётна.

Разложение на транспозиции не единственно: например, ε=[1 2][1 2]=[1 3][1 3]\varepsilon=[1\,2][1\,2]=[1\,3][1\,3]. Число множителей может быть разным, но его чётность у одной подстановки всегда одна и та же — её определяет знак.

Проверь себя

  1. Запиши [2 3]4[2\,3]_4 таблицей. Каков её знак?
  2. Разложи π=(123312)\pi=\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix} в произведение транспозиций и найди s(π)s(\pi).
  3. Что произойдёт с таблицей π=(123231)\pi=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} при умножении справа на [1 3][1\,3]?
Показать решение

1. [2 3]4=(12341324)[2\,3]_4=\begin{pmatrix}1&2&3&4\\1&3&2&4\end{pmatrix}. В нижней строке одна инверсия (3,2)(3,2), знак −1-1 — как у любой транспозиции.

2. Из (1,2,3)(1,2,3): на место 1 нужно 33 — обмен [1 3][1\,3] даёт (3,2,1)(3,2,1); на место 2 нужно 11 — обмен [1 2][1\,2] даёт (3,1,2)(3,1,2). Значит, π=[1 3][1 2]\pi=[1\,3][1\,2], два множителя, s(π)=+1s(\pi)=+1. Проверка: в (3,1,2)(3,1,2) две инверсии.

3. Умножение справа меняет числа 11 и 33 в нижней строке: (2,3,1)→(2,1,3)(2,3,1)\to(2,1,3). Получаем π[1 3]=(123213)\pi[1\,3]=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}.

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