Транспозиция перестановки

[RrX]

Транспозицией называется перестановка типа $(n-2, 1, 0, ..., 0)$, или перестановка двух элементов.

Как доказать, что любую перестановку можно представить в виду композиции транспозиций ?
Из определения этого не очень-то и видно( перестановка есть биекция множества $\{1,2,....n\}$ на себя ).

[cool.phenon]

Любую перестановку можно представить в виде произведения циклов, а цикл...

[RrX]

Цитата:

Любую перестановку можно представить в виде произведения циклов

Хмм, а это тоже надо доказать ведь?

Цитата:

а цикл...

можно разбить на композицию транспозиций.

[cool.phenon]

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

[RrX]

Цитата:

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

Погодите, но ведь цикл может быть одноэлементным. Его-то представить в виде транспозиции невозможно. А для двух и больше всё понятно.
Пусть дан цикл $(xyz...d)$, тогда его можно представить в виде композиции транспозиций $(xy)(yz)...(dx)$. Таким образом, любой цикл можно разбить на транспозиции, записав композицию всех возможных идущих друг за другом в цикле пар элементов.
Это, конечно, не доказательство, но тут вроде очевидно.

[cool.phenon]

А можете показать одноэлементный цикл? я пока не могу представить.

[RrX]

cool.phenon в сообщении #920037 писал(а):

А можете показать одноэлементный цикл? я пока не могу представить.

Элемент, не подвергающийся перестановке.
Тип перестановки же записывается в виде $(C_{1},C_{2},...C_{n})$, где $C_{k}$ - количество циклов длины $k$.

[cool.phenon]

Так это же тождественное преобразование, такие циклы в запись не включаются

[RrX]

Хорошо.
Опять же, по поводу "каждую перестановку можно представить в виде композиции циклов".
Попробую начать:
Примем за $U$ множество $\{1,2,...,k\}$. Есть перестановка $ f: U \to U $
Пусть $m$ - множество элементов, которые при перестановке отобразились сами в себя( одноэлементарные циклы, $m$ - натуральное число), $ n = \{x| x \in U \wedge x \notin m \} $
Докажем, что перестановку на $k$ можно представить в виде композиции циклов.
Допустим, что это неверно. Тогда нет таких двух элементов, которые взаимно поменялись местами. Но тогда...(очевидно, что это невозможно, но как доказать, не знаю )

[Sinoid]

Да к чему такие сложности? Берете любой элемент, не переходящий в себя и начинаете запись цикла. Ввиду конечности перестановки цикл тоже когда-то кончится.

[ewert]

RrX в сообщении #920010 писал(а):

Как доказать, что любую перестановку можно представить в виду композиции транспозиций ?

В любой нетривиальной перестановке несколько (возможно, ноль) начальных элементов отображаются каждый в себя, а следующий за ними -- уже во что-то другое. Но для того, чтобы вернуть его на место, достаточно именно транспозиции. И т.д.

[fiztech]

Всякая перестановка может быть разложена в произведение циклов. Всякий цикл можно представить в виде произведения транспозиций таким вот способом $(n_1n_2...n_k) =(1, n_1)(1, n_2).....(1,n_k)$ . Проверьте это.

[VAL]

fiztech в сообщении #920135 писал(а):

Всякий цикл можно представить в виде произведения транспозиций таким вот способом $(n_1n_2...n_k) =(1, n_1)(1, n_2).....(1,n_k)$ . Проверьте это.

... и убедитесь, что это не так.

Как, впрочем, и Ваше разложение:

Цитата:

$(xyz...d)=(xy)(yz)...(dx)$

Хотя оба внешне похожи на верное соотношение.

[RrX]

VAL
И почему же композиции неверны?

[Brukvalub]

Ваще не понимаю этих людей! Берем любой продвинутый курс алгебры (Кострикин, Винберг и т.п.), или почти любой учебник по теории групп, и в 5 сек. находим в нем необходимый факт, поскольку доказываемое является совсем уж стандартным фрагментом теории конечных групп (строение симметрической группы), и есть в любом приличном курсе.