Алгебра-1. Лекция 1

Что такое алгебра

Мы будем изучать алгебру. Со школы все знают, что алгебра – это то, что не геометрия, но у нас будет немножко другое понимание того, чем мы занимаемся. Исторически алгебра – наука о решении всевозможных уравнений. Со временем оказалось, что для изучения решений уравнений нужны дополнительные структуры, напрямую с уравнениями вроде бы не связанные. Когда Галуа и Абель доказывали неразрешимость уравнения пятой степени в радикалах – что нельзя взять произвольное уравнение пятой степени с вещественными коэффициентами и написать явную формулу его корней, используя только корни какой-нибудь степени из чего-нибудь, – оказалось, что этот факт непосредственно следует из теории так называемых групп. Это будет уже сильно позже и, видимо, не в рамках этого курса, но после изучения некоторых алгебраических вещей это не очень сложно сделать.

Что такое алгебраическая структура? Грубо говоря, множество с какими-то операциями на нём, удовлетворяющими каким-то свойствам. Люди замечают, что многие объекты обладают очень похожими свойствами, и логично объединить их в один класс, изучать этот класс целиком, а уже потом применять к конкретным объектам. Самая базовая, на мой взгляд, алгебраическая структура – группа.

Группы

Определение (Группа). Группа – произвольное множество $G$ (от первой буквы слова «группа») с одной бинарной операцией (она берёт на вход два элемента группы, упорядоченно, и делает по ним третий элемент), традиционно называемой умножением, $G \times G \to G$ , $(g_{1}, g_{2}) \mapsto g_{1} g_{2}$ , со следующими свойствами:

ассоциативность: $g_{1} (g_{2} g_{3}) = (g_{1} g_{2}) g_{3}$ для любых $g_{1}, g_{2}, g_{3} \in G$ : скобки можно перекидывать;
существует выделенный элемент $e \in G$ (нейтральный) такой, что $e g = g e = g$ для любого $g \in G$ ;
для любого $g \in G$ существует обратный элемент $g^{- 1} \in G$ такой, что $g g^{- 1} = g^{- 1} g = e$ .

Если к тому же выполнено 4. $g_{1} g_{2} = g_{2} g_{1}$ для любых $g_{1}, g_{2}$ , то есть неважно, в каком порядке перемножать, то группа называется абелевой.

Значок умножения в абстрактной группе будем опускать и писать $g_{1} g_{2}$ вместо $g_{1} \cdot g_{2}$ , точно так же, как в школе. Значок $\exists$ означает «существует», $\forall$ – «для любого».

Замечание (единственность). Нейтральный элемент и обратный $g^{- 1}$ определены однозначно; аналогично единица и обратные элементы в кольце и в поле, о которых ниже. Пусть в группе два элемента $e_{1}$ , $e_{2}$ со свойством нейтрального. Перемножим их: $e_{1} e_{2}$ . С одной стороны, $e_{1}$ нейтральный, поэтому при умножении второй элемент не меняет: $e_{1} e_{2} = e_{2}$ . С другой стороны, $e_{2}$ нейтральный: $e_{1} e_{2} = e_{1}$ . Итого $e_{1} = e_{2}$ . С обратными то же самое: пусть $g_{1}^{- 1}$ и $g_{2}^{- 1}$ оба обратны к $g$ ; посчитаем $g_{1}^{- 1} g g_{2}^{- 1}$ двумя способами. Расставив скобки как $(g_{1}^{- 1} g) g_{2}^{- 1}$ , получаем $e g_{2}^{- 1} = g_{2}^{- 1}$ ; расставив как $g_{1}^{- 1} (g g_{2}^{- 1})$ (по ассоциативности мы это можем), получаем $g_{1}^{- 1} e = g_{1}^{- 1}$ . Они равны. Поэтому если вы доказали, что какой-то элемент удовлетворяет свойству обратного, то это и есть обратный.

Ещё одно замечание о группах в целом: если $g = g_{1} g_{2} \dots g_{k}$ , то

g^{- 1} = g_{k}^{- 1} g_{k - 1}^{- 1} \dots g_{1}^{- 1}

то есть элементы в обратном порядке и в минус первой степени. Если перемножить $g$ с этим элементом, всё посокращается: $g_{k}$ с $g_{k}^{- 1}$ , затем $g_{k - 1}$ с $g_{k - 1}^{- 1}$ , и так далее, и получится нейтральный элемент.

Пример (группы).

Целые числа по сложению, $(Z, +)$ . Здесь роль умножения абстрактной группы играет сложение: складывая целые числа, получаем целые, сложение ассоциативно, есть нуль, который ничего не меняет, у любого числа есть противоположное. По умножению $Z$ группой, конечно, не является: почти ни у кого нет обратного, тем более у нуля: на нуль делить нельзя нигде вообще.
Рациональные числа по сложению $(Q, +)$ и ненулевые рациональные числа по умножению $(Q^{*}, \cdot)$ . Значок $Q^{*}$ стандартно обозначает $Q$ без нуля: нуль оставлять нельзя, делить на него невозможно, а если его выкинуть, всё становится замечательно.
То же для вещественных чисел: $(R, +)$ и $(R^{*}, \cdot)$ .
Движения плоскости с операцией композиции: композиция движений есть движение, обратное к движению есть движение, тождественное движение служит нейтральным элементом, а ассоциативность есть по определению того, как устроена композиция.
Более общо, все взаимно однозначные отображения какого-нибудь множества $X$ в себя, тоже с композицией. Или, наоборот, не все движения плоскости, а часть: симметрии многоугольников, многогранников и так далее.
Для тех, кто читал: линейные группы матриц: $GL_{n}$ (обратимые матрицы $n \times n$ , по умножению), $SL_{n}$ (с определителем единица), $SU_{n}$ и тому подобное.
Важный частный случай примера 5, когда $X = {1, \dots, n}$ , – группа $S_{n}$ . Мы сегодня займёмся ею очень подробно.

Замечание (аддитивная запись). В нескольких примерах роль операции играет сложение. Явление настолько частое, что, кроме мультипликативной записи, которая работает всегда, есть аддитивная: операцию записывают через $+$ , нейтральный элемент $0$ , обратный $- g$ . Так делают только для абелевых групп. В группе движений плоскости знак плюс никто никогда не пишет: операция некоммутативна, движения в разном порядке дают разные композиции.

Кольца

Следующая по важности и распространённости структура – кольцо. Тут есть расхождения в терминологии; сначала более общепринятый вариант, потом вариации.

Определение (Кольцо). Кольцо – множество $R$ (от ring) с двумя бинарными операциями, сложением $+$ и умножением $\cdot$ , такими, что:

1–4. $R$ – абелева группа по сложению: $a + b = b + a$ ; $(a + b) + c = a + (b + c)$ ; существует $0$ с $a + 0 = a$ ; для любого $a$ существует $- a$ с $a + (- a) = 0$ ; 5. обе дистрибутивности: $(a + b) c = a c + b c$ и $a (b + c) = ab + a c$ ; 6. умножение ассоциативно: $(ab) c = a (b c)$ .

Раз сложение обозначено плюсом, оно обязано быть абелевым, как уже говорилось. В аддитивной записи обратный элемент – это $- a$ , а не $a^{- 1}$ . Больше я не буду писать, что все элементы лежат в кольце, – только там, где неочевидно, какой элемент где лежит.

Где точно нет расхождений: в кольце обязаны выполняться обе дистрибутивности. В большинстве случаев кольцо по умолчанию считается ассоциативным; объекты, где выполнены первые пять аксиом, а шестая нет, называются неассоциативными кольцами, но бывают источники, где ассоциативность не входит в базовый набор аксиом, и тогда кольцо с шестой аксиомой называют ассоциативным. Если дополнительно

$ab = ba$ , то есть множители можно менять местами,

кольцо называется коммутативным (не «абелевым»). Если

существует единица $1$ такая, что $1 \cdot a = a \cdot 1 = a$ для любого $a$ ,

говорят, что это кольцо с единицей. Бывает, что выполнено только $1 \cdot a = a$ ; тогда в кольце есть левая единица. Если только $a \cdot 1 = a$ , то правая. В англоязычной литературе кольцом обычно считается всё, что удовлетворяет первым шести аксиомам и ещё с единицей; кольцо без единицы там обозначают словом rng – ring, из которого выкинули i, то есть единицу, – которое и произнести нормально нельзя. В общем, каждый раз приходится отдельно смотреть, какие именно кольца рассматриваются; в книжке по коммутативной алгебре по умолчанию всегда есть единица и умножение коммутативно, и это проговаривается в самом начале.

Пример (кольца).

Целые числа $Z$ – самый базовый пример: можно складывать, умножать.
$Q$ , $R$ , для знающих – комплексные числа $C$ .
Чуть интереснее: $Z / n Z$ – множество остатков при делении на $n$ . Остатки можно складывать и умножать, все аксиомы выполняются.
Матрицы размера $n \times n$ , для тех, кто знает, что это такое (мы это ещё обсудим): их можно складывать и умножать. Это пример некоммутативного кольца, но с единицей.
Кольцо без единицы: $2 Z$ , чётные числа. Их можно складывать и умножать, они остаются чётными, но единица нечётна, и её там нет.

Поля и тела

В кольцах сложение максимально хорошее: можно не только складывать, но и вычитать. А делить далеко не всегда. Поля – это кольца, где можно делить.

Определение (Поле). Поле – множество $F$ с двумя операциями, сложением и умножением, удовлетворяющее десяти аксиомам:

1–4. $F$ – абелева группа по сложению (коммутативность, ассоциативность, нуль, противоположный элемент $- a$ ); 5–8. аналогичные аксиомы для умножения: $ab = ba$ ; $(ab) c = a (b c)$ ; существует $1$ с $1 \cdot a = a$ , аналог нуля для умножения (вторую разность писать не надо, коммутативность уже дана); для любого $a \neq = 0$ существует $a^{- 1}$ с $a a^{- 1} = 1$ ; 9. дистрибутивность $(a + b) c = a c + b c$ : связывает сложение с умножением, скобки раскрывать можно; 10. $1 \neq = 0$ .

В восьмой аксиоме обязательно « $a \neq = 0$ »: на нуль делить нельзя нигде, а все ненулевые элементы обратимы, на них смело можно делить. Десятая аксиома выглядит странно. Зачем она? Чтобы было минимум два элемента: несложно показать – каждый может сделать это на досуге, или будет такая задача, – что если $1 = 0$ и все остальные аксиомы выполнены, то в поле ровно один элемент. Само по себе это ничем не плохо, но вся линейная алгебра над таким «полем» работает совершенно не так, как над нормальными, и в тьме-тьмущей теорем пришлось бы говорить «пусть $F$ – поле, отличное от вот этого». Проще сразу сказать, что это не поле, и не захламлять голову.

Определение (Тело). Тело – кольцо с единицей, в котором все ненулевые элементы обратимы по умножению. Грубо говоря, поле без коммутативности умножения.

Пример (поля и тела).

$Q$ , $R$ , $C$ .
$Z / p Z$ для простого $p$ : по модулю простого числа есть и деление.
Рациональные дроби, то есть рациональные функции над каким-нибудь полем, отношения многочленов; можно и не от одной переменной, а от десяти: вещественнозначные рациональные функции переменных $t_{1}, \dots, t_{10}$ – тоже поле. Остальные примеры – на потом.
Тел на текущем уровне мы можем предъявить немного; из школы, наверное, ни одного. Самый известный пример – кватернионы; их мы, скорее всего, рассматривать не будем.

Векторные пространства и модули

Определение (Векторное пространство). Векторное пространство над полем $F$ – множество $V$ с двумя операциями: сложением $V \times V \to V$ и умножением на скаляр $F \times V \to V$ (на вход не два вектора, а число и вектор), такими, что:

1–4. $V$ – абелева группа по сложению: $u + v = v + u$ ; $(u + v) + w = u + (v + w)$ ; существует нулевой вектор $0$ с $v + 0 = v$ ; для любого $v$ существует $- v$ с $v + (- v) = 0$ ; 5. $(α β) v = α (β v)$ : умножить сначала на одно число, потом на другое то же, что сразу на произведение; 6. $α (u + v) = α u + α v$ ; 7. $(α + β) v = α v + β v$ ; 8. $1 \cdot v = v$ .

Векторы привычнее называть буквами $u, v, w$ . Вокруг этого понятия построена целая наука, линейная алгебра.

Пример (векторные пространства).

Самый простой пример – пространство из одного элемента, нуля: его можно складывать с собой сколько угодно раз и умножать на любое число, получая его же.
Поле над самим собой: всё, что написано в аксиомах, – часть аксиом поля.
Более общо, любое поле над своим подполем – подмножеством поля с теми же операциями, самим являющимся полем: $Q \subset R$ , $R \subset C$ . А $Z \subset Q$ подполем не является: это не поле.
Свободные векторы на евклидовой плоскости. Что такое вектор? Отрезок с выбранными началом и концом; в школе мы научились отождествлять векторы, говоря, что один равен другому, и после этого – складывать их и умножать на числа. Множество классов векторов, которые можно двигать куда угодно, удовлетворяет всем аксиомам.
Многочлены над полем $F$ .
Для $F = R$ есть множество примеров из анализа: непрерывные, дифференцируемые, гладкие функции, определённые на одном и том же множестве (функции на $[0, 1]$ и на $[2, 3]$ не сложить, а на одном отрезке – можно), пространства $L^{2}$ и всякие такие. Ещё тьма примеров из дифференциальных уравнений.

Замечание (модули). В этом определении от поля требовалось только складывать и умножать его элементы; деления нигде нет. Так зачем брать именно поле, а не кольцо? Для кольца понятие тоже осмысленно, только называется по-другому: модуль – «векторное пространство над кольцом». Точное определение – упражнение: подумайте, какие аксиомы нужны. Модули нам будут очень активно нужны буквально через три лекции.

Алгебры

Последняя структура, которая будет встречаться в курсе.

Определение (Алгебра над полем). Алгебра над полем $F$ – векторное пространство $A$ над $F$ с одной дополнительной структурой: умножением $A \times A \to A$ уже элементов самой алгебры, таким, что

$(a + b) c = a c + b c$ и $a (b + c) = ab + a c$ для $a, b, c \in A$ ;
$(α a) (β b) = (α β) (ab)$ для $α, β \in F$ , $a, b \in A$ : согласованность с умножением на элементы поля.

Одним предложением: умножение билинейно, линейно по каждому аргументу; можно раскрывать скобки и выносить множители. Поле $F$ обычно не является подмножеством в $A$ ; иногда его можно отождествить с подмножеством – если в алгебре есть единица, элементу поля $α$ сопоставляется $α \cdot 1$ , и в этом смысле поле вкладывается в алгебру, – но вообще говоря, это необязательно.

Пример (алгебры). Поле над самим собой тривиально и неинтересно. Интересных базовых примера два: многочлены, которые можно умножать не только на числа, но и друг на друга; и, для знатоков, алгебра матриц – матрицы можно не только складывать и умножать на числа, но и перемножать между собой.

Это было вводное о том, чем занимается алгебра: изучением вот таких структур. Конечно, перечислены не все, но, по-моему, самые важные, те, что будут постоянно возникать в курсе. Теперь конкретно к группам; ближайшие сколько-то занятий проведём с ними.

Симметрическая группа

Определение (Подстановка). Подстановка, или перестановка, – взаимно однозначное отображение множества первых $n$ натуральных чисел в себя:

σ : {1, 2, \dots, n} \to {1, 2, \dots, n} .

Подстановки образуют группу относительно композиции – симметрическую группу $S_{n}$ .

Термины синонимичны; мне чуть больше нравится «подстановка», из лингвистических ощущений, что подстановка – это закон, который что-то куда-то отображает, а перестановка – результат применения этого закона. Подстановки я буду обозначать греческими буквами.

Что это группа: композиция взаимно однозначных отображений множества в себя есть снова такое отображение; обратное определено и взаимно однозначно; тождественная подстановка, переводящая каждый элемент в себя, – нейтральный элемент: если сначала ничего не переставлять, а потом переставить, получится вторая подстановка, и наоборот.

Коммутативна ли эта группа? Возьмём $n = 3$ , $σ_{1}$ меняет местами $1$ и $2$ , $σ_{2}$ меняет местами $2$ и $3$ . Поскольку операция есть композиция отображений, произведение читается справа налево: в $σ_{1} \circ σ_{2}$ сначала применяется $σ_{2}$ , потом $σ_{1}$ . Тогда $σ_{1} \circ σ_{2}$ : $1 \mapsto 1 \mapsto 2$ , $2 \mapsto 3 \mapsto 3$ , $3 \mapsto 2 \mapsto 1$ . А $σ_{2} \circ σ_{1}$ : $1 \mapsto 2 \mapsto 3$ , $2 \mapsto 1 \mapsto 1$ , $3 \mapsto 3 \mapsto 2$ . Уже по первому элементу видно, что они действуют по-разному. Итак, $S_{n}$ неабелева при $n \geq 3$ .

Запись подстановок

Подстановку можно рисовать диаграммой со стрелками, но это неудобно. Первый способ – табличка $2 \times n$ : сверху числа от $1$ до $n$ в каком-то порядке, под каждым – то, куда оно переходит:

σ = (a_{1} σ (a_{1}) a_{2} σ (a_{2}) \dots \dots a_{n} σ (a_{n})) .

Способов записи много: верхнюю строчку можно переставлять как угодно; обычно её упорядочивают по возрастанию, зачем изобретать велосипед. Но иногда удобно, наоборот, упорядочить по возрастанию нижнюю строчку, а сверху – как получится. Например, обратную подстановку в такой записи получить легко: если $σ$ переводила $a_{i}$ в $b_{i}$ , то $σ^{- 1}$ переводит $b_{i}$ в $a_{i}$ , – надо просто поменять строчки местами.

Как в таких терминах перемножать:

(14233241) \circ (12233144) = (13223441) :

$1$ переходит в $2$ , а $2$ – в $3$ , итого $1 \mapsto 3$ ; $2 \mapsto 3 \mapsto 2$ ; $3 \mapsto 1 \mapsto 4$ ; $4 \mapsto 4 \mapsto 1$ . Стандартное умножение, очень простое.

Циклы и транспозиции

Определение (Цикл). Подстановка $σ$ называется циклом, если существуют элементы $a_{1}, a_{2}, \dots, a_{k} \in {1, \dots, n}$ такие, что

σ (a_{1}) = a_{2}, σ (a_{2}) = a_{3}, \dots, σ (a_{k - 1}) = a_{k}, σ (a_{k}) = a_{1},

а всякий $b$ , не совпадающий ни с одним из $a_{i}$ , остаётся на месте: $σ (b) = b$ . Такая подстановка записывается $(a_{1}, a_{2}, \dots, a_{k})$ ; число $k$ – длина цикла. Цикл длины два называется транспозицией.

Видим такую запись и сразу понимаем: первый в второй, второй в третий, …, $k$ -й в первый, остальные стоят на месте. Так $σ_{1} = (1, 2)$ и $σ_{2} = (2, 3)$ из примера выше. Транспозиция переставляет два элемента, остальные не трогает.

Чем хороши транспозиции? Они порождают всю группу.

Теорема (Разложение в транспозиции). Любой элемент $S_{n}$ – произведение транспозиций.

Идея: любую перестановку можно сделать, каждый раз меняя два элемента местами; это сортировка. Сначала поменяем так, чтобы последний элемент пришёл куда нужно, потом предпоследний, и так далее.

Доказательство. Сделаем наоборот: возьмём подстановку $σ$ и с помощью транспозиций превратим её в тождественную. Пусть $σ$ переводит $1 \mapsto σ (1)$ , …, $n \mapsto σ (n)$ . Если $σ (n) = n$ , с этим столбиком ничего делать не нужно, переходим к следующему. Если нет, домножим $σ$ слева на транспозицию $(n, σ (n))$ . Чего мы добились? Раньше $n$ переходило в $σ (n)$ , а транспозиция отправляет $σ (n)$ обратно в $n$ : в подстановке $τ = (n, σ (n)) \circ σ$ элемент $n$ переходит в $n$ . Как $τ$ действует на первых элементах, мы точно не знаем – она что-то там поменяла, – но $n \mapsto n$ уж точно. Дальше смотрим на $τ (n - 1)$ : если не совпадает с $n - 1$ , домножаем на $(n - 1, τ (n - 1))$ , после чего последние два элемента переходят в себя. Действуя так, получаем

τ_{k} \circ \dots \circ τ_{2} \circ τ_{1} \circ σ = id

для некоторых транспозиций $τ_{i}$ . Транспозиция сама себе обратна: переставить два элемента, а потом их же снова, как будто ничего не делали. Поэтому, домножив равенство слева на $τ_{k}$ , мы убиваем $τ_{k}$ слева и она появляется справа; затем $τ_{k - 1}$ , и так далее:

σ = τ_{1} \circ τ_{2} \circ \dots \circ τ_{k} .

Теорема ничего не говорит о единственности такого разложения: у любой подстановки бесконечное множество разных разложений в транспозиции.

Независимые подстановки

Есть и другое разложение, через циклы, и оно уже почти единственно.

Определение (Независимые подстановки). Подвижные элементы подстановки – те, которые переходят не в себя. Подстановки $σ$ и $τ$ называются независимыми, если множества их подвижных элементов не пересекаются.

Группа $S_{n}$ неабелева, и даже очень сильно. А вот независимые подстановки всегда коммутируют.

Лемма (Независимые подстановки коммутируют). Если $σ$ и $τ$ независимы, то $σ \circ τ = τ \circ σ$ .

Доказательство. Это два отображения; чтобы доказать, что они одинаковы, достаточно проверить, что они переводят каждый элемент в одно и то же: $σ (τ (a)) = τ (σ (a))$ для любого $a$ . Разбираем случаи.

$a$ неподвижен для обеих. Тогда и $τ$ , и $σ$ оставляют $a$ на месте; обе композиции дают $a$ .

$a$ неподвижен для $σ$ , подвижен для $τ$ . Слева: $σ$ не меняет $a$ , потом $τ$ сдвигает его в $τ (a)$ ; итого $τ (σ (a)) = τ (a)$ . Справа: сначала $τ (a)$ , а потом $σ$ ; про то, что $σ$ делает с $τ (a)$ , мы пока ничего не знаем. Покажем, что $τ (a)$ неподвижен для $σ$ . Элемент $τ (a)$ заведомо подвижен для $τ$ : $τ$ переводит $a$ в $τ (a)$ , и если бы $τ (a)$ был неподвижен, то и $τ (a)$ переходил бы в $τ (a)$ – два разных элемента ( $a \neq = τ (a)$ ) переходили бы в один, а подстановка – биекция. Значит, $τ (a)$ подвижен для $τ$ , а тогда он не может быть подвижен для $σ$ : по независимости у них совсем разные подвижные элементы. Итак, $σ (τ (a)) = τ (a)$ – совпало.

$a$ подвижен для $σ$ , неподвижен для $τ$ : абсолютно аналогично.

$a$ подвижен для обеих: такого не бывает по независимости.

Обратное неверно: коммутирующие подстановки не обязаны быть независимыми: $g$ коммутирует с $g$ и с $g^{- 1}$ .

Разложение в независимые циклы

Теорема (Разложение в независимые циклы). Любая подстановка представляется в виде произведения независимых циклов, причём единственным образом с точностью до перестановки множителей.

Оговорка про перестановку нужна: как мы только что видели, независимые циклы можно переставлять как угодно, произведение от этого не зависит. (Ещё одна причина, почему мне больше нравится слово «подстановка»: иначе в формулировке было бы две «перестановки».) Кроме того, циклы можно по-разному записывать: $(1, 2, 3)$ – то же самое, что $(2, 3, 1)$ , разница только в том, с какого элемента начинать обход; на подстановку это не влияет, и фиксировать это мы не будем. Наконец, циклы из одного элемента не записываются – они ни на что не влияют, а если их записывать, единственность нарушится.

Доказательство. Существование. Построим разложение. Смотрим на элемент $1$ . Если он неподвижен, переходим дальше. Пусть $1$ переходит в $σ (1) \neq = 1$ ; напишем его за единицей. Элемент $σ (1)$ подстановка тоже куда-то отправляет – в $σ (σ (1))$ ; потом $σ (σ (σ (1)))$ , и так далее. Когда-нибудь мы точно зациклимся: множество конечное, и рано или поздно получится повторение. Повторением может оказаться только единица: если бы какой-то элемент отобразился, скажем, в $σ (σ (1))$ , то в этот элемент перешли бы и $σ (1)$ , и он – а это биекция. Значит, зациклиться можно только в единице, и налицо построенный цикл $(1, σ (1), σ (σ (1)), \dots)$ .

Затем берём первый элемент, ещё не выписанный, допустим $2$ . Если он переходит в себя, пропускаем; иначе строим цикл $(2, σ (2), σ (σ (2)), \dots)$ . Снова по конечности мы должны прийти в уже выписанный элемент; в первый цикл попасть нельзя – противоречие с биективностью, туда уже кто-то переходит, – и в элемент нового цикла, отличный от $2$ , тоже нельзя; значит, только в $2$ . Так в какой-то момент переберём все элементы: каждый либо входит в один из построенных циклов, либо неподвижен и нам не нужен. По построению циклы не пересекаются – они независимы, – и их произведение есть $σ$ : если элемент входит в цикл, следующий за ним в цикле – это по определению $σ$ от него, а если не входит, он неподвижен.

Единственность. Пусть $σ = σ_{1} \circ \dots \circ σ_{k} = σ_{1}^{'} \circ \dots \circ σ_{k^{'}}^{'}$ – два разложения в независимые циклы ( $k$ и $k^{'}$ могут быть разными). Возьмём элемент $a$ . Если $σ (a) = a$ , то $a$ не входит ни в один цикл ни того, ни другого разложения. Если $a$ подвижен, в первом разложении есть цикл, содержащий $a$ , и устроен он так: $a$ , за ним $σ (a)$ , потом $σ (σ (a))$ , и так далее. Но ровно такой же цикл должен быть и во втором разложении. Одинаковые циклы сокращаем, переходим к оставшимся – по индукции всё сократится.

Довольно тривиальное утверждение, но очень полезное.

Пример (случайная подстановка).

σ = (1224354751637886) .

Единица переходит в $2$ , $2$ в $4$ , $4$ в $7$ , $7$ в $8$ , $8$ в $6$ , $6$ в $3$ , $3$ в $5$ , $5$ в $1$ : $σ = (1, 2, 4, 7, 8, 6, 3, 5)$ , почему-то один цикл. Какова вероятность этого? Всего подстановок $n!$ : куда переходит первый элемент, можно выбрать $n$ способами, куда второй – $n - 1$ , и так далее. Циклов длины $n$ , содержащих все элементы: единицу можно перевести в любой из $n - 1$ остальных, тот – в любой из оставшихся, …, а последний обязан переходить в единицу; итого $(n - 1)!$ . Вероятность – $1/ n$ , здесь $1/8$ .

Возведение в степень

Зачем нужны разложения в независимые циклы? Одна из причин: подстановку становится очень легко возводить в степень. Вообще говоря, в произвольной группе $(ab)^{k} = a^{k} b^{k}$ неверно: слева написано $ab ab \dots ab$ ( $k$ раз), справа – сначала $k$ раз $a$ , потом $k$ раз $b$ , и почему одно равно другому, ниоткуда не следует. Но если $a$ и $b$ коммутируют, можно переставить множители так, чтобы все $a$ оказались слева, а все $b$ справа, и равенство верно. Независимые циклы коммутируют, поэтому если $σ = σ_{1} \circ \dots \circ σ_{k}$ – разложение в независимые циклы, то

σ^{m} = σ_{1}^{m} \circ σ_{2}^{m} \circ \dots \circ σ_{k}^{m} .

А циклы возводить в степень одно удовольствие. Цикл длины $k$ в $k$ -й степени – тождественная подстановка: мы применяем его $k$ раз, каждый раз сдвигая элементы по циклу на один; если правильный $k$ -угольник повернуть $k$ раз на одну вершину, он совместится сам с собой. Значит, тождественны и степени $2 k$ , $3 k$ , …, и чтобы возвести цикл в большую степень $m$ , надо поделить $m$ на его длину с остатком и возвести в степень остатка.

Верно ли, что степень цикла снова один цикл той же длины? Нет:

(1, 2, 3, 4)^{2} = (1, 3) \circ (2, 4) :

$1 \mapsto 2 \mapsto 3$ , $3 \mapsto 4 \mapsto 1$ , и аналогично $2 \mapsto 4$ , $4 \mapsto 2$ . При возведении в степень циклы иногда распадаются на независимые циклы, но это не страшно: задача всё равно резко стала проще – не надо тысячу раз смотреть, куда что переходит, а надо один раз разложить в независимые циклы и посмотреть, что произошло с каждым.

TikZ diagram — Поворот квадрата на $9 0^{\circ}$ по часовой стрелке – цикл $(1, 2, 3, 4)$ на вершинах. Повернуть дважды значит применить центральную симметрию: она меняет местами $1$ и $3$ , $2$ и $4$ , два независимых цикла.

Чётность подстановки

Ещё одно важнейшее свойство подстановок: их чётность. Запишем $σ$ в стандартном виде, с верхней строчкой $1, 2, \dots, n$ .

Определение (Инверсия, чётность, знак). Инверсия подстановки $σ$ – пара чисел $i < j$ таких, что $σ (i) > σ (j)$ : правильно упорядоченная пара после подстановки становится неправильно упорядоченной: большее число стоит в нижней строчке левее меньшего. Чётность подстановки – чётность числа её инверсий. Знак подстановки –

sgn (σ) = (- 1)^{σ} = (- 1)^{число инверсий σ},

плюс для чётных и минус для нечётных; $sgn$ от слова sign, оба обозначения стандартны.

(Это не «беспорядок»: беспорядком называют подстановку, у которой ни один элемент не переходит в себя.)

Теорема (Умножение на транспозицию меняет знак). Пусть $τ$ – транспозиция. Тогда чётности и знаки подстановок $σ$ и $τ \circ σ$ различны.

Иными словами, если в нижней строчке переставить два элемента местами, знак поменяется.

Доказательство. Пусть $τ$ меняет местами $σ (i)$ и $σ (j)$ , $i < j$ : в $τ \circ σ$ элемент $i$ переходит в $σ (j)$ , $j$ – в $σ (i)$ , а все остальные переходят, как переходили. Посмотрим, что произошло с инверсиями – где исчезли, где появились, где не изменились. Для пары $k < l$ проверяем, есть ли инверсия в $σ$ и в $τ \circ σ$ .

Ни $k$ , ни $l$ не совпадают с $i$ , $j$ . Их образы $τ$ не трогает: инверсия, если была, осталась, если не было, не появилась. Число таких инверсий не изменилось.
$k = i$ , $l = j$ . Если инверсия была, после перестановки она исчезает; если не было, появляется. Число инверсий изменилось на $\pm 1$ .
$k < i$ , $l \in {i, j}$ . Если была инверсия в паре $(k, i)$ , то есть $σ (k) > σ (i)$ , то после перестановки то же неравенство даёт инверсию в паре $(k, j)$ , и наоборот: инверсии с $i$ и с $j$ меняются местами, а отсутствие инверсии переходит в отсутствие. Число инверсий не изменилось.
$l > j$ , $k \in {i, j}$ . То же самое: инверсии с $i$ и с $j$ меняются ролями, число не меняется.
$i < k < j$ , второй элемент пары равен $i$ или $j$ . Смотрим, как $σ (k)$ расположен относительно $σ (i)$ и $σ (j)$ . Если $σ (k)$ больше обоих, то и до, и после перестановки в парах $(i, k)$ и $(k, j)$ ровно одна инверсия – число не меняется; если меньше обоих – аналогично, снова ровно одна. Если $σ (k)$ зажат между ними – скажем, $σ (i) < σ (k) < σ (j)$ , – то до перестановки эти три элемента стояли по порядку и инверсий в парах с $k$ не было, а после появляются сразу две; в противоположном случае две исчезают. Итого для каждого такого $k$ число меняется на $0$ или на $\pm 2$ .

Складываем: одна $\pm 1$ и сколько-то $\pm 2$ и нулей дают нечётное число. Число инверсий у $σ$ и $τ \circ σ$ отличается на нечётное число, чётность поменялась, знак поменялся.

Теорема (Следствие). Чётная подстановка – произведение чётного числа транспозиций, нечётная – нечётного. Произведение двух чётных подстановок чётно, двух нечётных – чётно, чётной и нечётной в любом порядке – нечётно.

Доказательство. У тождественной подстановки ровно нуль инверсий, она чётная. Каждое домножение на транспозицию меняет чётность: после нечётного числа транспозиций получается нечётная подстановка, после чётного – чётная. Отсюда второе: произведение двух чётных подстановок – произведение чётного числа транспозиций, и так же с остальными случаями. Чётность ведёт себя точно так же, как при сложении чисел: сумма чётных чётна, сумма нечётных чётна, чётного и нечётного – нечётна.

Related works