Подстановка является (может быть представлена) либо циклом, либо произведением циклов - теорема

Теорема. Подстановка является (может быть представлена) либо циклом, либо произведением циклов.

Пусть
$$
A=\begin{pmatrix}
1 && 2 && ... && n \\
a_1 && a_2 && ... && a_n
\end{pmatrix}.
$$
Подстановка $A$ является элементом [конечного порядка] [конечной] симметрической группы $\mathfrak{S}_n$.
Отсюда получаем, что
$$
\{h\in\mathbb{N} \ | \ A^h(1)=1\}\neq\emptyset.
$$
Пусть $k$ --- наименьшее число из этого множества (это может быть и 1).
Можно доказать, что среди элементов $1,\ A(1),\ A^2(1),\ ...,\ A^{k-1}(1)$ не может быть двух равных.
$$
A_1=\left(1 \ \ A(1)\ \ A^2(1) \ \ ...\ \ A^{k-1}(1)\right)
$$
будет циклом.
Цикл $A_1$ сам принадлежит симметрической группе. $A_1$ совпадает (как отображение) с $A$ на элементах $1,\ A(1),\ A^2(1),\ ...,\ A^{k-1}(1)$.

$A_1$ совпадает (как отображение) с тождественной подстановкой на множестве
$$
\{1,\ ...,\ n\} \setminus \{1,\ A(1),\ A^2(1),\ ...,\ A^{k-1}(1)\}.
$$

Возьмём следующую цифру из множества
$$
\{1,\ ...,\ n\} \setminus \{1,\ A(1),\ A^2(1),\ ...,\ A^{k-1}(1)\}
$$
и построим следующий цикл, и так далее.
Так каждая цифра будет принадлежать какому-то циклу (быть может, состоящему
из одной цифры).

ПРИМЕЧАНИЕ: Эти циклы не могут попарно пересекаться, так как принадлежность двух элементов к одному и тому же циклу является отношением эквивалентности, что можно показать. Поэтому они перестановочны.
Произведение получившихся циклов будет совпадать с исходной подстановкой $A$.

vedro-compota's picture

(Теорема добавлена участником участником math2 в ответ на этот вопрос)

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

...симметрической группы .....

определения такой группы тут нет. Надо будет разобраться с этим

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

Отсюда получаем, что
$$
\{h\in\mathbb{N} \ | \ A^h(1)=1\}\neq\emptyset.
$$

то есть, что не пусто множество таких $h$, что для данного элемент (перестановки) $A$....
вообще что такое $A(1)$ - отображение некоего элемента, а $A(1) = 1$ его отображение в себя?

_____________
матфак вгу и остальная классика =)

$A(1)$---это цифра из $\{1,\ 2,\ ...,\ n\}$
Здесь подстановки рассматриваются как отображения из
$\{1,\ 2,\ ...,\ n\}$ в $\{1,\ 2,\ ...,\ n\}$.
И $A^2(1)=A\left(A(1)\right)$.
Так как порядок группы $\mathfrak{S}_n$ конечен, то и любой элемент этой группы имеет
конечный порядок.
$$
A^k=J,
$$
где $k$---порядок элемента $A$, $J$---тождественное отображение.
Поэтому $A^k(1)=J(1)=1$.

vedro-compota's picture

$A2(1)=A(A(1))$

это я сразу понял)

$A(1)$---это цифра из $\{1, 2, ..., n\}$

а вот это нет, но теперь понял) Спасибо)

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

J---тождественное отображение

по-идее можно показать что только тождественное отображение может быть "единицей" в этой группе, да?

_____________
матфак вгу и остальная классика =)

быть "единицей" в этой группе

О какой группе идёт речь?

Можно показать, что единица подгруппы $H$ группы $G$ совпадает с единицей группы $G$.

vedro-compota's picture

О какой группе идёт речь?

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

_____________
матфак вгу и остальная классика =)

Конечно. В любой группе подстановок только тождественная подстановка является единицей.

Можно показать, что если для элемента $U$ некоторой группы $\mathfrak{G}$ выполняется условие $U^2=U$, то он равен $J$.

Имеем $U U = U$.
Для $U$ в группе $\mathfrak{G}$ имеется правый обратный $X$: $UX=J$.
Умножим предпоследнее равенство справа на $X$. Получим:
$$
UUX=UX.
$$
Далее используем ассоциативность умножения в группе.
$$
U(UX)=UX.
$$
$$
UJ=J.
$$
$$
U=J.
$$

vedro-compota's picture

кстати, \varnothing смотрится красивее, чем \emptyset (сайт в данный момент оба поддерживает) =)

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

Пусть k --- наименьшее число из этого множества

то есть тут $k$ - есть порядок элемента $A$. да ведь?

_____________
матфак вгу и остальная классика =)

Нет.

Имеется в виду не то, что $A^k=J$, а лишь
$$
A^k(1)=1.
$$

$k$ будет порядком цикла, которому принадлежит цифра 1.

vedro-compota's picture

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

Можно доказать , что среди элементов $1,\ A(1),\ A^2(1),\ ...,\ A^{k-1}(1)$ не может быть двух равных.

с этим проблема (с ходу не могу показать) - буду благодарен за подсказку.

_____________
матфак вгу и остальная классика =)

Ряд
$$
1,\ A(1),\ A^2(1),\ ...,\ A^{k-1}(1)
$$

содержит лишь одну цифру 1, по определению числа $k$:
если бы этот ряд содержал две единицы, то $k$ не было бы наименьшим натуральным
числом, для которого $A^k(1)=1$.

Предположим теперь, что $A^s(1)=A^t(1)$, где $0\lt s\lt t\lt k$. Тогда применяя к цифре $A^s(1)$ подстановку $A$ несколько раз, можно было бы придти к $A^s(1)$ двумя путями:
--- первый путь не содержит цифру 1:
$$
A^s(1),\ A^{s+1}(1),\ ...,\ A^t(1)
$$
--- второй путь --- содержит:
$$
A^t(1),\ A^{t+1}(1),\ ...,\ A^{k-1}(1),\ 1,\ A(1),\ ... ,\ A^s(1).
$$
Но это невозможно, так как отображение $A$ определено однозначно.

vedro-compota's picture

Эти циклы не могут попарно пересекаться.

можно ли это как-то показать?

_____________
матфак вгу и остальная классика =)

Возможно, нам следует несколько строже подойти к определению цикла. Что значит, что два числа $i$, $j$ принадлежат одному и тому же циклу? Это значит, что существует такой $s\in\mathbb{Z}$, $s\ge 0$, что $(i)A^s=j$, то есть мы можем придти от $i$ к $j$ применяя несколько раз подстановку $A$.

Определение. Будем говорить, что $i$ принадлежит тому же циклу, что и $j$, если существует такой $s\in\mathbb{Z}$, $s\ge 0$, что $(i)A^s=j$.

Принадлежность числа циклу является отношением эквивалентности.

Обозначим длину цикла через $k$. Если $s\lt 0$, то мы можем взять вместо s его остаток от деления на $k$.

  1. Рефлексивность. Действительно, любое число $i$ принадлежит тому же циклу, что и $i$. Цикл числа $i$ вычисляется однозначно.
  2. Симметричность. Пусть $i$ лежит в одном цикле с $j$, то есть $(i)A^s=j$. Тогда и $(j)A^{-s}=i$.
  3. Транзитивность. Пусть $(i)A^s=j,\ \ (j)A^t=k.$ Тогда $(i)A^{s+t}=k$, то есть $i$ и $k$ принадлежат одному циклу.

Отношение эквивалентности разбивает множество на попарно непересекающиеся классы.

vedro-compota's picture

Перенёс данное определение сюда и добавил в глоссарий.

_____________
матфак вгу и остальная классика =)