F) Циклы
Рассмотрим
теперь частный, но важный случай
подстановки. Циклической
подстановкой
или циклом
называется такая подстановка, что при
повторении её достаточное число раз
всякий из действительно перемещаемых
ею элементов может быть переведён в
любой другой их этих элементов. k-членный
цикл переводит элемент 1
в элемент 2,
отличный от 1,
2
– в число 3,
отличный от 2,
…, k–1
– в элемент k,
отличный от k–1,
и k
– в исходный элемент 1,
а прочие элементы оставляет на месте.
Циклическая подстановка обозначает
символом
.
Например,
есть четырёхчленная циклическая подстановка (1234).
Очевидно, что транспозиция (ij), есть не что иное, как двучленная циклическая подстановка.
Тождественную подстановку E можно рассматривать как одночленный цикл (), где – любое из чисел 1, 2, …, n.
Два цикла называются независимыми, если они не имеют общих действительно перемещаемых элементов. Понятно, что при перемножении независимых циклов порядок множителей не влияет на результат.
Всякая подстановка может быть единственным способом разложена в произведение независимых циклов. Доказательство этого утверждения не представляет затруднений. Практически разложение осуществляется следующим образом: начинаем с любого из действительно перемещаемых элементов и выписываем за ним те элементы, в которые он переходит при повторении подстановки, пока не вернемся к исходному элементу. После этого «закрытия» цикла начинаем с одного из оставшихся действительно перемещаемых элементов, получаем второй цикл и т.д.
Пример 2.16. Представить подстановки в виде произведения независимых циклов:
а)
,
б)
,
в)
.
Обратно, для всякой подстановки, заданной разложением в независимые циклы, можно найти запись в обычной форме (при условии, что степень этой подстановки известна). Например,
,
если известно, что степень этой подстановки есть 7.
В свою очередь, всякий цикл можно представить в виде произведения транспозиций, но такое произведение уже не будет разложением на независимые циклы. Т.о., порядок следования транспозиций имеет уже существенное значение.
Например, цикл (2356) можно разложить следующим образом на транспозиции:
.
Действительно, первая транспозиция (23) переводит 2 в 3, а остальные транспозиции (25) и (26) число 3 не изменяют. Следовательно, произведение (23)(25)(26) число 2 переводит в 3. Затем число 3 транспозицией (23) переводится в 2, после чего 2 транспозицией (25) переводится в 5, а 5 транспозицией (26) не изменяется. Значит, произведение (23)(25)(26) число 3 переводит в 5. Далее, число 5 транспозицией (23) не изменяется, а транспозицией (25) переводится в 2, после чего 2 транспозицией (26) переводится в 6. Наконец, (23) и (25) число 6 не изменяют, а (26) число 6 переводит в 2; поэтому (23)(25)(26) переводит 6 в исходное число 2. Отсюда получается, что .
Вообще,
рассуждая подобным образом, можно
убедиться, что всякий
k-членный
цикл
разлагается в следующее произведение
(k–1)
транспозиций:
.
Предложение 4. Всякую подстановку из n чисел 1,2,…,n можно разложить на n–s транспозиций, где s – число независимых циклов (включая и одночленные), на которые разлагается данная подстановка.
Пусть подстановка
распадается в произведение независимых циклов:
.
Но каждый k-членный цикл разлагается на k–1 транспозиций, поэтому рассматриваемая подстановка A разлагается на
транспозиций, что и требовалось доказать.
Разность n–s называется декрементом подстановки и обладает следующим свойством.
Предложение 5. Чётность подстановки совпадает с чётностью декремента этой подстановки.
Предположим, что дано разложение подстановки A в s независимые циклы. В соответствие с предложением 4 эту подстановку можно разложить на n–s транспозиций. Это означает, что подстановку A можно разложить в произведение транспозиций, число которых равно декременту, а потому чётность подстановки будет определяться чётностью декремента.
Пример 2.17. Определить чётность подстановки
,
Решение. Найдём декремент подстановки, для чего разложим её на независимые циклы:
.
Получилось, что s=3, декремент n–s=6–3=3 есть нечётное число. Щначит, рассматриваемый член имеет знак минус.