2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 22:50 
Аватара пользователя
Любую перестановку можно представить в виде произведения циклов, а цикл...

 
 
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:01 
Цитата:
Любую перестановку можно представить в виде произведения циклов

Хмм, а это тоже надо доказать ведь?
Цитата:
а цикл...

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

 
 
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:05 
Аватара пользователя
Доказать по частям будет попроще, тем более, что для каждого цикла его разбиение на транспозиции выписывается сразу.

 
 
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:16 
Цитата:
Доказать по частям будет попроще, тем более, что для каждого цикла его разбиение на транспозиции выписывается сразу.

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

 
 
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:21 
Аватара пользователя
А можете показать одноэлементный цикл? я пока не могу представить.

 
 
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:26 
cool.phenon в сообщении #920037 писал(а):
А можете показать одноэлементный цикл? я пока не могу представить.

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

 
 
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:31 
Аватара пользователя
Так это же тождественное преобразование, такие циклы в запись не включаются

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

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

 
 
 
 Re: Транспозиция перестановки
Сообщение18.10.2014, 06:49 
RrX в сообщении #920010 писал(а):
Как доказать, что любую перестановку можно представить в виду композиции транспозиций ?

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

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

 
 
 
 Re: Транспозиция перестановки
Сообщение18.10.2014, 13:05 
fiztech в сообщении #920135 писал(а):
Всякий цикл можно представить в виде произведения транспозиций таким вот способом $(n_1n_2...n_k) =(1, n_1)(1, n_2).....(1,n_k)$ . Проверьте это.
... и убедитесь, что это не так.

Как, впрочем, и Ваше разложение:
Цитата:
$(xyz...d)=(xy)(yz)...(dx)$

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

 
 
 
 Re: Транспозиция перестановки
Сообщение18.10.2014, 18:25 
VAL
И почему же композиции неверны?

 
 
 
 Re: Транспозиция перестановки
Сообщение18.10.2014, 18:45 
Аватара пользователя
Ваще не понимаю этих людей! :shock: Берем любой продвинутый курс алгебры (Кострикин, Винберг и т.п.), или почти любой учебник по теории групп, и в 5 сек. находим в нем необходимый факт, поскольку доказываемое является совсем уж стандартным фрагментом теории конечных групп (строение симметрической группы), и есть в любом приличном курсе.

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group