Группы подстановок

Пусть

Вычислите следующие выражения.

Пусть

Представьте $\alpha$, $\beta$ и $\alpha \beta$ в виде произведений независимых циклов и в виде произведений 2-циклов.

Представьте каждую из следующих подстановок в виде произведения независимых циклов.

Найдите порядок каждой из следующих подстановок.

Каков порядок каждой из следующих подстановок?

Каков порядок каждой из следующих подстановок?

Каков порядок произведения двух независимых циклов длин 4 и 6? А произведения трёх независимых циклов длин 6, 8 и 10?

Определите, являются ли следующие подстановки чётными или нечётными.

Представьте $((14562)(2345)(136)(235))^{10}$ в виде произведения независимых циклов.

Представьте $(13)(1245)(13)$ и $(24)(13456)(24)$ в виде произведений независимых циклов. Дайте простое описание того, как полученный цикл связан со средним циклом в каждом произведении.

Пусть $n$ — положительное целое число. Если $n$ нечётно, является ли $n$-цикл чётной или нечётной подстановкой? А если $n$ чётно?

Если $\alpha$ чётна, докажите, что $\alpha^{-1}$ чётна. Если $\alpha$ нечётна, докажите, что $\alpha^{-1}$ нечётна.

Покажите, что отображение конечного множества $S$ в себя инъективно тогда и только тогда, когда оно сюръективно. Верно ли это для бесконечного $S$? (На эту задачу ссылаются в главе 6.)

Сколько при $n \geq 4$ в $S_n$ элементов, переводящих 1 в 2, 2 в 3, а 3 в 1? Сколько таких элементов в $A_n$ при $n \geq 5$?

Пусть $\alpha$ и $\beta$ принадлежат $S_n$. Докажите, что $\alpha \beta$ чётна тогда и только тогда, когда $\alpha$ и $\beta$ либо обе чётны, либо обе нечётны.

Сопоставьте чётной подстановке число $+1$, а нечётной — число $-1$. Проведите аналогию между результатом умножения двух подстановок и результатом умножения соответствующих им чисел $+1$ или $-1$.

Пусть $n$ — произвольное целое число, а $\alpha$ нечётна. Дополните утверждение: $\alpha^n$ нечётна тогда и только тогда, когда .

Пусть в $S_n$ подстановка $\alpha$ является $r$-циклом, $\beta$ — $s$-циклом, а $\gamma$ — $t$-циклом. Дополните утверждения: $\alpha \beta$ чётна тогда и только тогда, когда $r + s$ ; $\alpha \beta \gamma$ чётна тогда и только тогда, когда $r + s + t$ .

Пусть $\alpha$ и $\beta$ принадлежат $S_n$. Докажите, что $\alpha^{-5}\beta \alpha^3$ нечётна тогда и только тогда, когда $\beta$ нечётна.

Пусть $\alpha$ и $\beta$ принадлежат $S_n$. Докажите, что $\beta \alpha \beta^{-1}$ и $\alpha$ либо обе чётны, либо обе нечётны.

Дополните утверждение: произведение циклов является чётной подстановкой тогда и только тогда, когда число циклов чётной длины .

Каково наименьшее $n$, при котором в $S_n$ есть элемент порядка 30? А в $A_n$?

Каковы возможные порядки элементов $S_6$ и $A_6$? А элементов $A_7$? (На эту задачу ссылаются в главе 24.)

Найдите элемент порядка 15 в $A_8$. Найдите элемент порядка 30 в $A_{12}$.

Пусть $\beta = (1, 3, 5, 7, 9, 8, 6)(2, 4, 10)$. Каково наименьшее положительное целое $n$, для которого $\beta^n = \beta^{-5}$?

Какой цикл равен $(a_1 a_2 \cdots a_n)^{-1}$?

Покажите, что если $H$ — подгруппа $S_n$, то либо каждый элемент $H$ является чётной подстановкой, либо ровно половина элементов чётна. (На эту задачу ссылаются в главе 24.)

Пусть $H$ — подгруппа $S_n$ нечётного порядка. Докажите, что $H$ — подгруппа $A_n$.

Укажите две причины, по которым множество нечётных подстановок в $S_n$ не является подгруппой.

Пусть $\alpha$ и $\beta$ принадлежат $S_n$. Докажите, что $\alpha^{-1}\beta^{-1}\alpha \beta$ является чётной подстановкой.

Сколько в $A_8$ элементов порядка 2, имеющих разложение на независимые циклы вида

?

Сколько при $n \geq 5$ в $S_n$ нечётных подстановок порядка 5?

Сколько элементов порядка 2 в $A_6$? Сколько элементов порядка 6 в $A_7$?

Пусть $H = \left\{ x^2 \mid x \in A_4\right\}$. Докажите, что $H$ не является подгруппой $A_4$. (Сравните с примером 5 главы 3.)

Каково наименьшее $n$, при котором уравнение $x^5 = (12345)$ имеет решение в $S_n$? Приведите пример решения. Сколько решений существует при найденном $n$?

Пусть $\alpha = (1, 3, 5, 7, 9)(2, 4, 6)(8, 10)$. Если $\alpha^m$ является 5-циклом, что можно сказать о $m$?

Сколько в $S_6$ элементов порядка 4? Сколько в $S_6$ элементов порядка 2?

Докажите, что $(1234)$ не является произведением 3-циклов. Обобщите.

Пусть $\beta \in S_7$ и $\beta^4 = (2143567)$. Найдите $\beta$. Каковы возможные значения $\beta$, если $\beta \in S_9$?

Пусть $\beta = (123)(145)$. Представьте $\beta^{99}$ в виде произведения независимых циклов.

Пусть $(a_1 a_2 a_3 a_4)$ и $(a_5 a_6)$ — независимые циклы в $S_{10}$. Покажите, что в $S_{10}$ нет элемента $x$, для которого $x^2 = (a_1 a_2 a_3 a_4)(a_5 a_6)$.

Если $\alpha$ и $\beta$ — различные 2-циклы, каковы возможные значения $\left|\alpha \beta \right|$?

Пусть $G$ — группа подстановок множества $X$. Для $a \in X$ положим $\operatorname {stab}(a) = \left\{ \alpha \in G \mid \alpha (a) = a\right\}$. Назовём $\operatorname {stab}(a)$ стабилизатором $a$ в $G$ (поскольку он состоит из всех элементов $G$, оставляющих $a$ неподвижным). Докажите, что $\operatorname {stab}(a)$ — подгруппа $G$. (Эту подгруппу ввёл Галуа в 1832 году.) На эту задачу ссылаются в главе 7.

Пусть $H = \left\{ \beta \in S_5 \mid \beta (1) = 1 \text{ и } \beta (3) = 3\right\}$. Докажите, что $H$ — подгруппа $S_5$. Сколько элементов в $H$? Сохраняется ли ваше рассуждение при замене $S_5$ на $S_n$ для $n \geq 3$? Сколько элементов в $H$ при замене $S_5$ на $A_n$ для $n \geq 4$?

Для $n \geq 3$ положим $H = \left\{ \beta \in S_n \mid \beta (1) = 1 \text{ или } 2 \text{ и } \beta (2) = 1 \text{ или } 2\right\}$. Докажите, что $H$ — подгруппа $S_n$. Определите $\left|H\right|$.

Пусть $\alpha$ — 12-цикл. Опишите цикловую структуру $\alpha^2, \alpha^3, \alpha^4$ и $\alpha^6$. Более общо, если $\alpha$ — $n$-цикл и $k$ делит $n$, опишите цикловую структуру $\alpha^k$.

Пусть $\alpha$ — $n$-цикл, а $k$ — положительное целое число. Докажите, что $\alpha^k$ является $n$-циклом тогда и только тогда, когда $\gcd (n, k) = 1$.

Найдите в $S_3$ элементы $\alpha$ и $\beta$, для которых $\left|\alpha \right| = 2$, $\left|\beta \right| = 2$ и $\left|\alpha \beta \right| = 3$.

Найдите в $S_5$ элементы $\alpha$ и $\beta$, для которых $\left|\alpha \right| = 3$, $\left|\beta \right| = 3$ и $\left|\alpha \beta \right| = 5$.

Представьте группу симметрий равностороннего треугольника как группу подстановок его вершин (см. пример 3).

Докажите, что $S_n$ неабелева при всех $n \geq 3$. Докажите, что $A_n$ неабелева при всех $n \geq 4$.

Покажите, что в $S_n$ ($n \geq 4$) уравнение $x^2 = (1234)$ не имеет решений, а в $S_7$ уравнение $x^3 = (1234)$ имеет три решения.

Докажите теорему 5.6.

(Теорема 5.6, чётные подстановки образуют группу: множество чётных подстановок в $S_n$ образует подгруппу $S_n$.)

Пусть $(ab)$ и $(cd)$ — различные 2-циклы в $S_n$. Докажите, что $(ab)$ и $(cd)$ коммутируют тогда и только тогда, когда они независимы.

Найдите в $S_4$ циклическую подгруппу порядка 4 и нециклическую подгруппу порядка 4.

Пусть в $S_{100}$ заданы $\alpha = (1, 2, 3, \ldots , 100)$ и $\beta = (1, 50, 100)$. Чему равно $\left|\alpha \beta \right|$? Приведите пример двух элементов $S_{100}$, каждый из которых имеет порядок 100, а их произведение имеет порядок 3.

Рассматривая элементы $D_4$ как группу подстановок вершин квадрата, помеченных 1, 2, 3, 4, как описано в примере 3, определите, какие геометрические симметрии соответствуют чётным подстановкам.

Рассматривая элементы $D_5$ как группу подстановок вершин правильного пятиугольника, последовательно помеченных 1, 2, 3, 4, 5, определите, какая геометрическая симметрия соответствует подстановке $(14253)$. Какая симметрия соответствует подстановке $(25)(34)$?

Пусть $n$ — нечётное целое число, большее 1. Рассматривая $D_n$ как группу подстановок вершин правильного $n$-угольника, последовательно помеченных $1, 2, \ldots , n$, объясните, почему подгруппа поворотов группы $D_n$ является подгруппой $A_n$. Является ли $D_5$ подгруппой $A_5$? Если да, укажите отражение из $D_5$, принадлежащее $A_5$. Почему это доказывает, что $D_5$ — подгруппа $A_5$? Является ли $D_7$ подгруппой $A_7$? Если да, укажите отражение из $D_7$, принадлежащее $A_7$.

Покажите, что каждый элемент $A_n$ при $n \geq 3$ можно представить в виде 3-цикла или произведения 3-циклов.

При $n \geq 4$ пусть $B_n$ — множество всех элементов $S_n$, которые можно записать как произведение чётного числа 4-циклов. Докажите, что $B_n$ — подгруппа $A_n$.

Для $B_n$, определённого в предыдущей задаче, докажите, что каждый 3-цикл в $A_n$ ($n \geq 4$) является произведением двух 4-циклов.

Пусть $B_n$ ($n \geq 4$) — подгруппа $A_n$, определённая в задаче 61. Докажите, что $B_n = A_n$.

Пусть $\alpha_1, \alpha_2$ и $\alpha_3$ — 2-циклы. Докажите, что $\alpha_1 \alpha_2 \alpha_3 \neq \varepsilon$. Обобщите.

Покажите, что в $A_5$ есть 24 элемента порядка 5, 20 элементов порядка 3 и 15 элементов порядка 2. (На эту задачу ссылаются в главе 24.)

Найдите циклическую подгруппу $A_6$ порядка 4. Найдите нециклическую подгруппу $A_8$ порядка 4.

Покажите, что подстановка нечётного порядка обязательно чётна.

Вычислите порядок каждого элемента $A_4$. Как связаны арифметически эти порядки с порядком $A_4$?

Для любого нечётного целого $n$, не меньшего 3, представьте $(2, n)(3, n - 1) \cdots ((n+1)/2, (n+3)/2)(12 \cdots n)$ в виде произведения независимых циклов. Заметим, что $\left|(2, n)(3, n - 1) \cdots ((n+1)/2, (n+3)/2)\right| = 2$ и $\left|(12 \cdots n)\right| = n$, а их произведение имеет порядок 2. Если вершины правильного $n$-угольника пометить $1, 2, \ldots , n$ против часовой стрелки, как в примере 3, какие элементы $D_n$ соответствуют $(2, n)(3, n - 1) \cdots ((n+1)/2, (n+3)/2)$ и $(12 \cdots n)$?

Покажите, что при $n \geq 3$ имеем $Z(S_n) = \left\{ \varepsilon \right\}$.

Проверьте утверждение, сделанное при обсуждении схемы контрольной цифры Верхуффа на основе $D_5$: $a * \sigma (b) \neq b * \sigma (a)$ для различных $a$ и $b$. С его помощью докажите, что $\sigma^i(a) * \sigma^{i+1}(b) \neq \sigma^i(b) * \sigma^{i+1}(a)$ для всех $i$. Докажите, что отсюда следует обнаружение всех ошибок, состоящих в перестановке соседних цифр.

(Напомним схему Верхуффа: цифры от 0 до 9 рассматриваются как элементы группы диэдра $D_5$ порядка 10; используются подстановка $\sigma = (01589427)(36)$ и групповая операция $*$ в $D_5$. К строке цифр $a_1 a_2 \ldots a_{n-1}$ приписывается контрольная цифра $a_n$ так, чтобы $\sigma (a_1) * \sigma^2(a_2) * \cdots * \sigma^{n-1}(a_{n-1}) * \sigma^n(a_n) = 0$, где $\sigma^2(x) = \sigma (\sigma (x))$, $\sigma^3(x) = \sigma (\sigma^2(x))$ и так далее. Поскольку $\sigma$ обладает свойством $\sigma^i(a) \neq \sigma^i(b)$ при $a \neq b$, все ошибки в одной цифре обнаруживаются автоматически.)

Используя схему контрольной цифры Верхуффа на основе $D_5$, припишите контрольную цифру к 45723.

Докажите, что каждый элемент $S_n$ ($n > 1$) можно записать как произведение элементов вида $(1k)$.

(Математическое соревнование колледжей Индианы) Машина для тасования карт всегда переставляет карты одним и тем же способом относительно порядка, в котором они в неё поступили. Все червовые карты, расположенные по порядку от туза до короля, поместили в машину, а затем полученные карты снова поместили в неё для тасования. Если после этого карты вышли в порядке 10, 9, Q, 8, K, 3, 4, A, 5, J, 6, 2, 7, в каком порядке они располагались после первого тасования?

Определите целые $n$, для которых $H = \left\{ \alpha \in A_n \mid \alpha^2 = \varepsilon \right\}$ является подгруппой $A_n$.

Найдите пять подгрупп $S_5$ порядка 24.

Почему из того, что порядки элементов $A_4$ равны 1, 2 и 3, следует $\left|Z(A_4)\right| = 1$?

Пусть $\alpha$ принадлежит $S_n$. Докажите, что $\left|\alpha \right|$ делит $n!$.

Зашифруйте сообщение ATTACK POSTPONED с помощью подстановки $\alpha = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 5 & 3 & 4 \end{bmatrix}$.

Сообщение VAADENWCNHREDEYA зашифровано с помощью подстановки $\alpha = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{bmatrix}$. Расшифруйте его.