В принципе, ничего нам не мешает расставить их сначала одним способом, затем раздать всем новые номера в соответствии с порядком в новом ряду и снова расставить. Теперь попробуем расставить не людей, а скажем, пронумерованные мешки с говном. Понятное дело, что свойства номеров при расставлении в ряд никак не изменятся. Более того, не изменятся и свойства того, куда какой объект ставится, если мы изначально будем не нумеровать, а давать имя по алфавиту. Проще говоря, нам сейчас интересны не сами объекты, над которыми производятся операции, а свойства отображений между ними.
Такие отображения, которые множество M отображают само в себя (целиком) так, что никакие два элемента не перешли в одинаковые, называются перестановками. Очень удобно писать перестановки в виде двух строк, в первой пишутся числа от 1 до n, а во второй строке пишутся их образы при перестановке. Например:
1 2 3 4 5
5 3 2 1 4
Заметим, что в самом начале мы потребовали, чтобы никакие два числа во второй строке не встречались по несколько раз. Такие штуки можно перемножать, то есть брать их композицию как отображений. Например, запись
1 2 3 4 5 1 2 3 4 5
5 3 2 1 4 * 4 3 1 5 2
означает, что мы сначала 1 переводим в 5, а потом 5 переводим в 2. То есть в итоге 1 переходит в 2. 2 сначала переходит в 3, потом 3 в 1, значит, 2 переходит в 1. Аналогично 3 переходит в 2, потом в 3, то есть 3 переходит в себя. Аналогично 4 и 5 переходят в себя (проверьте сами, не все же мне за вас делать). Таким образом, получилась перестановка
1 2 3 4 5
2 1 3 4 5
Такие перестановки, которые меняют только два элемента местами, а остальные оставляют на месте, называются транспозициями. Аналогично, если, например, перестановка сдвигает 3 элемента по циклу, то она называется циклом длины 3 (аналогично 4, 5, …):
1 2 3 4 5 6 7 8
1 2 4 5 6 7 3 8
- цикл длины пять.
Любопытно, что если взять произвольную перестановку, то можно заметить, что в ней некоторые элементы бегают по циклам, в которых не участвуют другие элементы, например, в перестановке
1 2 3 4 5 6 7 8 9
6 3 4 2 1 5 7 9 8
есть отдельный цикл, в котором задействованы только числа 1, 6, 5, отдельный цикл, в котором задействованы только числа 2, 3, 4, транспозиция 8 и 9 и 7 переходит сама в себя. Такое разложение на непересекающиеся циклы позволяет записывать перестановки более компактным способом, например, вместо цикла 1 -> 6, 6 -> 5, 5 -> 1 будем писать просто (165). Тогда вся перестановка, описанная выше, будет записана так: (165)(234)(89). Обычно в такой записи элемент, переходящий в себя (он называется неподвижным), не пишется.
Понятное дело, что разницы в том, в каком порядке писать циклы (например, можно было написать (234)(98)(651)) нет. Тем не менее, обычно пишут так, чтобы первое число в скобке было наименьшим, а по всем скобкам первые числа были чем меньше, тем левее. Это очень удобно, когда начинаешь в такой записи перемножать перестановки:
(1234)(67) * (13)(264)(57) = (1657432) (я сам охренел, что получился цикл длины 7, числа были рандомные).
Перестановка, которая каждый элемент переводит самого в себя, называется единичной или тождественной, а еще для каждой подстановки можно найти такую, что при перемножении они дадут тождественную, например, в записи циклами можно просто все циклы записать в обратном порядке. Ну и да, можно расставлять скобки между операциями умножения подстановок. Эти три свойства означают, что перестановки обладают групповым свойством, то есть являются группой.
Данный факт является наиважнейшим в теории групп, перестановки там возникают на каждом шагу, а теорема Кэли вообще утверждает, что всякая конечная группа является подгруппой некоторой группы подстановок.
Ну если вы не убедились в охерительности данной структуры, то вот вам самое классное ее свойство – четность и нечетность.
Сначала определим четность циклов. Все просто, четность цикла – это обычная четность его длины + 1. То есть цикл длины 3 четный, длины 4 нечетный, 5 – четный и так далее. А четность самой подстановки определяется как четность количества нечетных циклов. То есть всё как с обычными числами, если два нечетных цикла, то подстановка четная, если три нечетных цикла, то нечетная и так далее.
Так вот, удивительным образом четность перестановки возникает повсеместно – когда считаешь определитель, в анализе, в тензорах и так далее.
Спасибо за то, что вы с нами.
С любовью, Рителлинг favorite
