2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Транспозиция перестановки
Сообщение17.10.2014, 22:48 


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

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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 22:50 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:01 


09/10/14
53
Цитата:
Любую перестановку можно представить в виде произведения циклов

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

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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:05 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:16 


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

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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:21 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:26 


09/10/14
53
cool.phenon в сообщении #920037 писал(а):
А можете показать одноэлементный цикл? я пока не могу представить.

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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:31 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение17.10.2014, 23:50 


09/10/14
53
Хорошо.
Опять же, по поводу "каждую перестановку можно представить в виде композиции циклов".
Попробую начать:
Примем за $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 


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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение18.10.2014, 06:49 
Заслуженный участник


11/05/08
32166
RrX в сообщении #920010 писал(а):
Как доказать, что любую перестановку можно представить в виду композиции транспозиций ?

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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение18.10.2014, 11:05 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение18.10.2014, 13:05 
Заслуженный участник


27/06/08
4058
Волгоград
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 


09/10/14
53
VAL
И почему же композиции неверны?

 Профиль  
                  
 
 Re: Транспозиция перестановки
Сообщение18.10.2014, 18:45 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group