bulgakov

05. Знак подстановки и знак произведения

У перестановки-списка мы считали инверсии в одном ряду. У подстановки есть две строки. Чтобы определить её чётность независимо от порядка записи столбцов, будем считать инверсии в обеих строках вместе.

Знак двухстрочной записи

Пусть

π=(i1i2⋯inj1j2⋯jn).\pi=\begin{pmatrix} i_1&i_2&\cdots&i_n\\ j_1&j_2&\cdots&j_n \end{pmatrix}.

Определение 25.1. В верхней строке инверсию образуют места p<qp<q, если ip>iqi_p>i_q. В нижней строке — те же условия для её чисел: jp>jqj_p>j_q. Каждую строку рассматриваем отдельно; пары из разных строк не сравниваем.

Обозначим число инверсий верхней строки через II, нижней — через JJ. Тогда общее число инверсий двух строк

t=I+J.t=I+J.

Определение 25.2. Подстановка чётная при чётном tt и нечётная при нечётном tt. Её знак обозначают sgn⁡(π)\operatorname{sgn}(\pi) или s(π)s(\pi):

s(π)=(−1)t={+1,t чётно,−1,t нечётно.s(\pi)=(-1)^t= \begin{cases} +1,&t\text{ чётно},\\ -1,&t\text{ нечётно}. \end{cases}

Например, тождественная подстановка

ε=(123123)\varepsilon=\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}

имеет ноль инверсий в каждой строке, поэтому s(ε)=+1s(\varepsilon)=+1. Так тождественная подстановка оказывается чётной. Если записать её столбцы в другом порядке, обе строки останутся одинаковыми: в каждой будет одно и то же число инверсий, так что сумма будет удвоенным, то есть чётным, числом.

Почему знак не зависит от порядка столбцов

Сначала поменяем местами два числа только в одной строке, оставив другую строку прежней. По теореме 22.1 чётность числа инверсий этой строки изменится, следовательно, знак всей таблицы сменится на противоположный. При этом соответствия между верхними и нижними числами изменятся: мы получили другую подстановку.

Теперь поменяем местами два столбца целиком. Это одновременно обмен двух чисел в верхней строке и обмен двух чисел в нижней. Каждый обмен меняет чётность своей строки, поэтому общее число tt меняется на чётное число. Знак остаётся тем же. Это следствие 25.1:

s(таблицы после обмена двух столбцов)=s(исходной таблицы).s(\text{таблицы после обмена двух столбцов})=s(\text{исходной таблицы}).

Посмотрим на конкретные числа:

(123231)⟶(213321).\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} \quad\longrightarrow\quad \begin{pmatrix}2&1&3\\3&2&1\end{pmatrix}.

Справа первые два столбца поменялись местами. Слева верхняя строка имеет 00 инверсий. В нижней (2,3,1)(2,3,1) их ровно две: (2,1)(2,1) и (3,1)(3,1). Поэтому t=2t=2 и знак +1+1. Справа верхняя строка (2,1,3)(2,1,3) имеет одну инверсию (2,1)(2,1). В нижней (3,2,1)(3,2,1) их три: (3,2)(3,2), (3,1)(3,1) и (2,1)(2,1). Поэтому t=1+3=4t=1+3=4 и знак опять +1+1.

Это важная тонкость: само число tt у разных записей одной подстановки может быть разным, но его чётность и знак совпадают. Любой порядок столбцов можно получить последовательными обменами двух столбцов. Поэтому следствие 25.2 утверждает, что знак — свойство самой подстановки, а не выбранной таблицы.

Для вычисления знака часто удобно перейти к каноническому виду: верхняя строка там (1,2,…,n)(1,2,\ldots,n) и не имеет инверсий. Тогда достаточно посчитать инверсии нижней строки. Этот приём верен именно потому, что мы уже доказали независимость знака от перестановки столбцов.

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

Теорема 25.1. Для любых подстановок π,σ\pi,\sigma на одном NnN_n

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

Здесь сохраняется правило §24: в произведении πσ\pi\sigma сначала действует π\pi, затем σ\sigma.

Разберём доказательство со всеми промежуточными шагами. Поскольку порядок столбцов не влияет на знак, запишем π\pi канонически, а столбцы σ\sigma расположим так, чтобы её верхняя строка совпала с нижней строкой π\pi:

π=(12⋯nj1j2⋯jn),σ=(j1j2⋯jnk1k2⋯kn).\pi= \begin{pmatrix} 1&2&\cdots&n\\ j_1&j_2&\cdots&j_n \end{pmatrix}, \qquad \sigma= \begin{pmatrix} j_1&j_2&\cdots&j_n\\ k_1&k_2&\cdots&k_n \end{pmatrix}.

Так можно сделать: (j1,…,jn)(j_1,\ldots,j_n) содержит каждое число NnN_n один раз, и в верхней строке σ\sigma каждое из этих чисел тоже есть ровно один раз. По столбцам видно, что ii переходит сначала в jij_i, затем в kik_i. Поэтому

πσ=(12⋯nk1k2⋯kn).\pi\sigma= \begin{pmatrix} 1&2&\cdots&n\\ k_1&k_2&\cdots&k_n \end{pmatrix}.

Пусть в списке (j1,…,jn)(j_1,\ldots,j_n) ровно JJ инверсий, а в (k1,…,kn)(k_1,\ldots,k_n) — ровно KK. Тогда в таблице π\pi верхняя строка даёт 00 инверсий, нижняя — JJ; в таблице σ\sigma верхняя даёт JJ, нижняя — KK; в таблице πσ\pi\sigma верхняя даёт 00, нижняя — KK. Значит,

s(π)=(−1)J,s(σ)=(−1)J+K,s(πσ)=(−1)K.s(\pi)=(-1)^J,\qquad s(\sigma)=(-1)^{J+K},\qquad s(\pi\sigma)=(-1)^K.

Перемножим первые два знака:

s(π)s(σ)=(−1)J(−1)J+K=(−1)2J+K=(−1)K=s(πσ).s(\pi)s(\sigma) =(-1)^J(-1)^{J+K} =(-1)^{2J+K} =(-1)^K =s(\pi\sigma).

Здесь 2J2J чётно, поэтому его добавление не меняет знак. Это завершает доказательство.

Проверим формулу на подстановках из предыдущего урока:

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

У нижней строки π\pi, то есть (2,3,1)(2,3,1), две инверсии: (2,1)(2,1) и (3,1)(3,1). Поэтому s(π)=+1s(\pi)=+1. У нижней строки σ\sigma, то есть (3,2,1)(3,2,1), три инверсии: (3,2)(3,2), (3,1)(3,1) и (2,1)(2,1). Поэтому s(σ)=−1s(\sigma)=-1. Чтобы получить πσ\pi\sigma, проследим, например, вход 11: 1→π2→σ21\xrightarrow{\pi}2\xrightarrow{\sigma}2, так что под 11 в произведении окажется 22. Аналогично вход 22 проходит 2→3→12\to3\to1, а вход 33 — 3→1→33\to1\to3. По правилу §24

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

у его нижней строки единственная инверсия (2,1)(2,1), то есть s(πσ)=−1=(+1)(−1)s(\pi\sigma)=-1=(+1)(-1).

Из теоремы сразу следует полезная проверка обратной подстановки: поскольку ππ−1=ε\pi\pi^{-1}=\varepsilon и s(ε)=1s(\varepsilon)=1, числа s(π)s(\pi) и s(π−1)s(\pi^{-1}) одинаковы. Действительно, каждое из них равно либо +1+1, либо −1-1, а их произведение равно 11.

Проверь себя

  1. Найди знак таблицы (213321)\begin{pmatrix}2&1&3\\3&2&1\end{pmatrix}. Изменится ли он, если поставить столбцы в каноническом порядке?
  2. Пусть α=(123213)\alpha=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix} и β=(123132)\beta=\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}. Какой знак должен иметь αβ\alpha\beta? Проверь через его нижнюю строку.
Показать решение

1. Верхняя строка имеет одну инверсию (2,1)(2,1), нижняя — три: (3,2)(3,2), (3,1)(3,1) и (2,1)(2,1). Всего t=4t=4, так что знак +1+1. Канонический вид (123231)\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} имеет две инверсии в нижней строке — (2,1)(2,1) и (3,1)(3,1) — и тот же знак.

2. У α\alpha одна инверсия (2,1)(2,1) и знак −1-1; у β\beta тоже одна, (3,2)(3,2), и знак −1-1. Поэтому s(αβ)=(−1)(−1)=+1s(\alpha\beta)=(-1)(-1)=+1. По порядку действий §24 получаем αβ=(123312)\alpha\beta=\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}; нижняя строка имеет две инверсии, (3,1)(3,1) и (3,2)(3,2), что подтверждает ответ.

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