05. Знак подстановки и знак произведения
У перестановки-списка мы считали инверсии в одном ряду. У подстановки есть две строки. Чтобы определить её чётность независимо от порядка записи столбцов, будем считать инверсии в обеих строках вместе.
Знак двухстрочной записи
Пусть
Определение 25.1. В верхней строке инверсию образуют места , если . В нижней строке — те же условия для её чисел: . Каждую строку рассматриваем отдельно; пары из разных строк не сравниваем.
Обозначим число инверсий верхней строки через , нижней — через . Тогда общее число инверсий двух строк
Определение 25.2. Подстановка чётная при чётном и нечётная при нечётном . Её знак обозначают или :
Например, тождественная подстановка
имеет ноль инверсий в каждой строке, поэтому . Так тождественная подстановка оказывается чётной. Если записать её столбцы в другом порядке, обе строки останутся одинаковыми: в каждой будет одно и то же число инверсий, так что сумма будет удвоенным, то есть чётным, числом.
Почему знак не зависит от порядка столбцов
Сначала поменяем местами два числа только в одной строке, оставив другую строку прежней. По теореме 22.1 чётность числа инверсий этой строки изменится, следовательно, знак всей таблицы сменится на противоположный. При этом соответствия между верхними и нижними числами изменятся: мы получили другую подстановку.
Теперь поменяем местами два столбца целиком. Это одновременно обмен двух чисел в верхней строке и обмен двух чисел в нижней. Каждый обмен меняет чётность своей строки, поэтому общее число меняется на чётное число. Знак остаётся тем же. Это следствие 25.1:
Посмотрим на конкретные числа:
Справа первые два столбца поменялись местами. Слева верхняя строка имеет инверсий. В нижней их ровно две: и . Поэтому и знак . Справа верхняя строка имеет одну инверсию . В нижней их три: , и . Поэтому и знак опять .
Это важная тонкость: само число у разных записей одной подстановки может быть разным, но его чётность и знак совпадают. Любой порядок столбцов можно получить последовательными обменами двух столбцов. Поэтому следствие 25.2 утверждает, что знак — свойство самой подстановки, а не выбранной таблицы.
Для вычисления знака часто удобно перейти к каноническому виду: верхняя строка там и не имеет инверсий. Тогда достаточно посчитать инверсии нижней строки. Этот приём верен именно потому, что мы уже доказали независимость знака от перестановки столбцов.
Основное свойство: знак произведения
Теорема 25.1. Для любых подстановок на одном
Здесь сохраняется правило §24: в произведении сначала действует , затем .
Разберём доказательство со всеми промежуточными шагами. Поскольку порядок столбцов не влияет на знак, запишем канонически, а столбцы расположим так, чтобы её верхняя строка совпала с нижней строкой :
Так можно сделать: содержит каждое число один раз, и в верхней строке каждое из этих чисел тоже есть ровно один раз. По столбцам видно, что переходит сначала в , затем в . Поэтому
Пусть в списке ровно инверсий, а в — ровно . Тогда в таблице верхняя строка даёт инверсий, нижняя — ; в таблице верхняя даёт , нижняя — ; в таблице верхняя даёт , нижняя — . Значит,
Перемножим первые два знака:
Здесь чётно, поэтому его добавление не меняет знак. Это завершает доказательство.
Проверим формулу на подстановках из предыдущего урока:
У нижней строки , то есть , две инверсии: и . Поэтому . У нижней строки , то есть , три инверсии: , и . Поэтому . Чтобы получить , проследим, например, вход : , так что под в произведении окажется . Аналогично вход проходит , а вход — . По правилу §24
у его нижней строки единственная инверсия , то есть .
Из теоремы сразу следует полезная проверка обратной подстановки: поскольку и , числа и одинаковы. Действительно, каждое из них равно либо , либо , а их произведение равно .
Проверь себя
- Найди знак таблицы . Изменится ли он, если поставить столбцы в каноническом порядке?
- Пусть и . Какой знак должен иметь ? Проверь через его нижнюю строку.
Показать решение
1. Верхняя строка имеет одну инверсию , нижняя — три: , и . Всего , так что знак . Канонический вид имеет две инверсии в нижней строке — и — и тот же знак.
2. У одна инверсия и знак ; у тоже одна, , и знак . Поэтому . По порядку действий §24 получаем ; нижняя строка имеет две инверсии, и , что подтверждает ответ.
