bulgakov

08. Циклы и разложение подстановки

Проследим, куда подстановка переводит одно число, затем его образ, и так далее. Например, 5↦2↦8↦4↦55\mapsto2\mapsto8\mapsto4\mapsto5: путь замкнулся в круг. Такой круг называют циклом. Любая подстановка распадается на несколько непересекающихся кругов, и по их длинам сразу виден знак.

Цикл

Определение 28.1. Пусть i1,…,iki_1,\ldots,i_k — различные числа из NnN_n. Циклом [i1 i2 … ik]n[i_1\,i_2\,\ldots\,i_k]_n называют подстановку, которая переводит

i1↦i2↦i3↦⋯↦ik↦i1,i_1\mapsto i_2\mapsto i_3\mapsto\cdots\mapsto i_k\mapsto i_1,

а все остальные числа оставляет на месте. Число kk — длина цикла. Если nn ясно из контекста, индекс nn не пишут.

Пример 28.1. При n=9n=9 цикл [5 2 8 4][5\,2\,8\,4] — это подстановка

(528413679284513679).\begin{pmatrix}5&2&8&4&1&3&6&7&9\\2&8&4&5&1&3&6&7&9\end{pmatrix}.

Цикл можно начинать с любого своего числа, сохраняя порядок обхода по кругу:

[5 2 8 4]=[4 5 2 8]=[8 4 5 2]=[2 8 4 5].[5\,2\,8\,4]=[4\,5\,2\,8]=[8\,4\,5\,2]=[2\,8\,4\,5].

А вот [5 2 4 8][5\,2\,4\,8] — уже другой цикл: в нём 2↦42\mapsto4, а не 2↦82\mapsto8.

Транспозиция [i j][i\,j] — это в точности цикл длины 22.

Цикл через транспозиции и его знак

Лемма 28.1. Цикл раскладывается в транспозиции с общим первым числом:

[i1 i2 … ik]=[i1 i2][i1 i3]⋯[i1 ik].[i_1\,i_2\,\ldots\,i_k]=[i_1\,i_2][i_1\,i_3]\cdots[i_1\,i_k].

Здесь, как всегда в курсе, сначала действует левый множитель. Пример 28.2: [2 8 4 5]=[2 8][2 4][2 5][2\,8\,4\,5]=[2\,8][2\,4][2\,5]. Проверим два входа:

  • 88: [2 8][2\,8] даёт 8↦28\mapsto2, затем [2 4][2\,4] даёт 2↦42\mapsto4, затем [2 5][2\,5] оставляет 44. Итог 8↦48\mapsto4, как в цикле.
  • 55: первые два множителя 55 не трогают, [2 5][2\,5] даёт 5↦25\mapsto2. Итог 5↦25\mapsto2, круг замкнулся.

Следствие 28.1. В цикле длины kk ровно k−1k-1 транспозиций, поэтому

s([i1 … ik])=(−1)k−1.\boxed{s([i_1\,\ldots\,i_k])=(-1)^{k-1}.}

Обрати внимание на сдвиг на единицу: цикл нечётной длины — чётная подстановка. Цикл длины 33 чётен, длины 22 (транспозиция) — нечётен, длины 44 — нечётен.

Независимые циклы

Определение 28.2. Циклы [i1 … ik][i_1\,\ldots\,i_k] и [j1 … js][j_1\,\ldots\,j_s] независимы, если у них нет общих чисел.

Свойство 28.1. Независимые циклы перестановочны: στ=τσ\sigma\tau=\tau\sigma. Каждый из них двигает только свои числа и не трогает числа другого, поэтому порядок применения не важен. Для зависимых циклов это неверно: [1 2][2 3]≠[2 3][1 2][1\,2][2\,3]\ne[2\,3][1\,2].

Теорема 28.1. Каждая подстановка равна произведению попарно независимых циклов.

Как найти такое разложение:

  1. Возьми наименьшее число, которое подстановка двигает и которое ещё не попало ни в один цикл.
  2. Иди по стрелкам i↦π(i)↦π(π(i))↦⋯i\mapsto\pi(i)\mapsto\pi(\pi(i))\mapsto\cdots, пока не вернёшься к началу. Получился цикл.
  3. Повторяй, пока не кончатся сдвигаемые числа. Неподвижные числа в запись не входят.

Пример 28.3.

π=(123456789386521947),\pi=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&8&6&5&2&1&9&4&7\end{pmatrix}, π=[1 3 6] [2 8 4 5] [7 9].\pi=[1\,3\,6]\,[2\,8\,4\,5]\,[7\,9].

Начали с 11: 1↦3↦6↦11\mapsto3\mapsto6\mapsto1. Следующее свободное число 22: 2↦8↦4↦5↦22\mapsto8\mapsto4\mapsto5\mapsto2. Затем 7↦9↦77\mapsto9\mapsto7. Все девять чисел учтены.

Знак по длинам циклов

Следствие 28.2. Если π=σ1σ2⋯σr\pi=\sigma_1\sigma_2\cdots\sigma_r — произведение циклов длин ∣σ1∣,…,∣σr∣|\sigma_1|,\ldots,|\sigma_r|, то

s(π)=(−1)(∣σ1∣−1)+(∣σ2∣−1)+⋯+(∣σr∣−1).s(\pi)=(-1)^{(|\sigma_1|-1)+(|\sigma_2|-1)+\cdots+(|\sigma_r|-1)}.

В примере 28.3 длины 3,4,23,4,2, сумма (3−1)+(4−1)+(2−1)=6(3-1)+(4-1)+(2-1)=6, знак +1+1.

Следствие 28.3. Если в разложение включить и неподвижные числа как циклы длины 11, так что сумма длин равна nn, то s(π)=(−1)n−rs(\pi)=(-1)^{n-r}, где rr — число циклов. В примере 28.3 неподвижных чисел нет: n=9n=9, r=3r=3, (−1)6=+1(-1)^{6}=+1.

Это самый быстрый способ найти знак большой подстановки: не нужно считать инверсии.

Проверь себя

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

1. 1↦2↦3↦11\mapsto2\mapsto3\mapsto1 и 4↦5↦44\mapsto5\mapsto4, поэтому π=[1 2 3][4 5]\pi=[1\,2\,3][4\,5]. Знак (−1)2+1=−1(-1)^{2+1}=-1. Проверка: в (2,3,1,5,4)(2,3,1,5,4) три инверсии — (2,1)(2,1), (3,1)(3,1), (5,4)(5,4).

2. По лемме 28.1 [1 3 4]=[1 3][1 4][1\,3\,4]=[1\,3][1\,4]. Проверка входа 44: [1 3][1\,3] его не трогает, [1 4][1\,4] даёт 4↦14\mapsto1.

3. (−1)5−1=+1(-1)^{5-1}=+1: цикл длины 55 чётен.

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