08. Циклы и разложение подстановки
Проследим, куда подстановка переводит одно число, затем его образ, и так далее. Например, : путь замкнулся в круг. Такой круг называют циклом. Любая подстановка распадается на несколько непересекающихся кругов, и по их длинам сразу виден знак.
Цикл
Определение 28.1. Пусть — различные числа из . Циклом называют подстановку, которая переводит
а все остальные числа оставляет на месте. Число — длина цикла. Если ясно из контекста, индекс не пишут.
Пример 28.1. При цикл — это подстановка
Цикл можно начинать с любого своего числа, сохраняя порядок обхода по кругу:
А вот — уже другой цикл: в нём , а не .
Транспозиция — это в точности цикл длины .
Цикл через транспозиции и его знак
Лемма 28.1. Цикл раскладывается в транспозиции с общим первым числом:
Здесь, как всегда в курсе, сначала действует левый множитель. Пример 28.2: . Проверим два входа:
- : даёт , затем даёт , затем оставляет . Итог , как в цикле.
- : первые два множителя не трогают, даёт . Итог , круг замкнулся.
Следствие 28.1. В цикле длины ровно транспозиций, поэтому
Обрати внимание на сдвиг на единицу: цикл нечётной длины — чётная подстановка. Цикл длины чётен, длины (транспозиция) — нечётен, длины — нечётен.
Независимые циклы
Определение 28.2. Циклы и независимы, если у них нет общих чисел.
Свойство 28.1. Независимые циклы перестановочны: . Каждый из них двигает только свои числа и не трогает числа другого, поэтому порядок применения не важен. Для зависимых циклов это неверно: .
Теорема 28.1. Каждая подстановка равна произведению попарно независимых циклов.
Как найти такое разложение:
- Возьми наименьшее число, которое подстановка двигает и которое ещё не попало ни в один цикл.
- Иди по стрелкам , пока не вернёшься к началу. Получился цикл.
- Повторяй, пока не кончатся сдвигаемые числа. Неподвижные числа в запись не входят.
Пример 28.3.
Начали с : . Следующее свободное число : . Затем . Все девять чисел учтены.
Знак по длинам циклов
Следствие 28.2. Если — произведение циклов длин , то
В примере 28.3 длины , сумма , знак .
Следствие 28.3. Если в разложение включить и неподвижные числа как циклы длины , так что сумма длин равна , то , где — число циклов. В примере 28.3 неподвижных чисел нет: , , .
Это самый быстрый способ найти знак большой подстановки: не нужно считать инверсии.
Проверь себя
- Разложи на независимые циклы и найди .
- Запиши цикл как произведение транспозиций.
- Какой знак у цикла длины ?
Показать решение
1. и , поэтому . Знак . Проверка: в три инверсии — , , .
2. По лемме 28.1 . Проверка входа : его не трогает, даёт .
3. : цикл длины чётен.
