Централизатор подстановки

[Alex_CAPS]

Приветствую!
Необходимо найти централизатор подстановки (1 2)(3 4) в группе $S_4$.
Начну с определения. Централизатор - множество элементов группы перестановочных с данным элементом. Для перестановочных элементов справедливо равенство $ab = ba$.
Обозначу данную в условии подстановку как
$ a = \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3\end{array} \right)$.
Выбирая различные подстановки, я выяснил, что перестановочными элементами НЕ являются перестановки с циклом длины 1. Например
$ b = \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 1 & 3 & 4 & 2\end{array} \right)$

$ ab = \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4\end{array} \right)$
$ ba = \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1\end{array} \right)$.

Не хотелось бы опускаться до брутфорса, но в голову не приходят методы проверки гипотезы, что централизатор состоит из элементов вида
$ c = \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ i_1 & i_2 & i_3 & i_4\end{array} \right)$, где $i_k \neq k$

[provincialka]

Ну, тождественная-то подстановка коммутирует с любой другой.
Кроме того, $a$ обратна самой себе, так что условие перестановочности можно переписать в виде $b(x)=a(b(a(x)))$. Например, $b(1)$ получается из $b(2)$ применением $a$. Осталось сообразить, какие значения может принимать пара $b(1),b(2)$.

[ИСН]

Централизатор - это разве не все перестановки с той же цикловой структурой?

[VAL]

Alex_CAPS в сообщении #764899 писал(а):

Приветствую!
Необходимо найти централизатор подстановки (1 2)(3 4) в группе $S_4$.
Начну с определения. Централизатор - множество элементов группы перестановочных с данным элементом. Для перестановочных элементов справедливо равенство $ab = ba$.
Обозначу данную в условии подстановку как
$ a = \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3\end{array} \right)$.

Знакомая картина
Вам дана подстановка в коротком, информативном, кратком и удобном для работы виде, а Вы, первым делом, переходите к двухстрочному, который хуже во всех возможных отношениях (включая громоздкость набора в TeX'е).
Аргумент "мне так понятнее" не годится. Он означает лишь то, что Вы пока не умеете работать с подстановками.

-- 18 сен 2013, 05:29 --

ИСН в сообщении #764918 писал(а):

Централизатор - это разве не все перестановки с той же цикловой структурой?

Разумеется, нет.
Например, $(1 \ 3 \ 2 \ 4)$ и $(1 \ 2)$ имеет другую цикловую структуру, но лежат в централизаторе. А тождественная подстановка вообще имеет уникальную цикловую структуру, но лежит в централизаторе каждой подстановки.

Ту же цикловую структуру имеют подстановки, сопряженные с данной.

[provincialka]

Почему $(1,3,4,2)$? Проверю через "двустрочный", функциональный подход.
Сначала $a$, потом $b$. Имеем $1\to 2\to 1$.
Сначала $b$, потом $a$. Тогда $1\to 3\to 4$. Результат другой.
Может, вы имели в виду $(1,3,2,4)$?

Лично мне проще описать все нужные перестановки функционально, оставлю пока это автору.

[VAL]

provincialka в сообщении #764949 писал(а):

Почему $(1,3,4,2)$? Проверю через "двустрочный", функциональный подход.
Сначала $a$, потом $b$. Имеем $1\to 2\to 1$.
Сначала $b$, потом $a$. Тогда $1\to 3\to 4$. Результат другой.
Может, вы имели в виду $(1,3,2,4)$?

Конечно, это очепятка. Спасибо, исправил.

Цитата:

Лично мне проще описать все нужные перестановки функционально, оставлю пока это автору.

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

-- 18 сен 2013, 07:53 --

PS: Придумал новый аргумент в бесконечном споре о том, какая форма записи подстановки удобнее:
Цикловая подстановки запись примерно настолько же прозрачнее матричной, насколько понятие "конечная циклическая группа" прозрачнее и проще понятия "конечная группа".

[provincialka]

Спорить не буду, не будучи специалистом. Тем не менее, я сразу увидела опечатку, именно потому, что представила подстановки как преобразования (перестановки элементов).

Но как удобно перемножать циклы все же не вижу.

-- 18.09.2013, 08:25 --

Насчет примера с группами. Ну, так не всякая группа - циклическая. Также и не всякую задачу легче решать с помощью циклов.

[VAL]

provincialka в сообщении #764963 писал(а):

Спорить не буду

Обещание не выполнено

Цитата:

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

Клянусь, я сделал ее не по причине использования циклового вида, а в силу:
природной рассеянности;
раннего часа (см. время поста).

Цитата:

Но как удобно перемножать циклы все же не вижу.

-- 18.09.2013, 08:25 --

Исключительно просто. Причем не обязательно перемножать за один раз только две подстановки. Сколько угодно!
Действовать можно исключительно на основании определения композиции отображений:
открываем скобку и пишем единичку;
движемся (взглядом) слева направо и ищем куда перешла единица, образ единицы, образ образа..., пока не дойдем до конца;
пишем тот элемент с которым пришли к конец записи и повторяем описанную процедуру для него;
если добрались до первого элемента цикла пишем вместо него закрывающую скобку;
если остались невыписанные элементы, пишем открывающую скобку и первый из таких элементов;
и т.д.
Остается добавить, что одноэлементные циклы принято опускать.

Цитата:

Насчет примера с группами. Ну, так не всякая группа - циклическая.

Вы не поверите, Я в курсе!
Но, согласитесь, из всех групп циклические устроены наиболее просто.

Цитата:

Также и не всякую задачу легче решать с помощью циклов.

Приведите пример.
Допускаю, что такие могут найтись. Но в тогда это будут очень специальные, экзотические примеры.
Дело в том, что цикловой вид перестановки естественнее других не только с точки зрения теории групп.
Но и с точки зрения комбинаторики (например, числа Стирлинга первого рода).
И с точки зрения самого определения понятия "подстановка". Это ведь биекция конечного множества на себя. Так вот цикловой вид показывает, что на самом деле исходное множество можно разбить на подмножества, на каждом из которых имеется своя, независимая от других простейшая биекция.

[provincialka]

Думаю, у нас спор о терминах. Я искала произведение именно так. Что во что переходит, это я и назвала "функциональным подходом". Так что мир, дружба, жвачка! И циклические группы!

[provincialka]

Еще мысль пришла. Да, исходные данные удобней в виде циклов. Но результат -нет. Например, я могу числам 1 и 2 поставить в соответствие пару 1,2 или 3,4. Остальные -второй паре. Например, подойдет подстановка со второй строкой $(4,3,1,2)$. А уж какие в ней циклы - второй вопрос, тут надо немного подумать. Получаем цикл $(1,4,2,3)$, но это уже преобразованный ответ.

[VAL]

provincialka в сообщении #765038 писал(а):

Еще мысль пришла. Да, исходные данные удобней в виде циклов. Но результат -нет. Например, я могу числам 1 и 2 поставить в соответствие пару 1,2 или 3,4. Остальные -второй паре. Например, подойдет подстановка со второй строкой $(4,3,1,2)$. А уж какие в ней циклы - второй вопрос, тут надо немного подумать. Получаем цикл $(1,4,2,3)$, но это уже преобразованный ответ.

Пример не убедил. Может, я просто не въехал в какой-то нюанс, но не ясно, чем ответ в виде второй строки лучше.
Я ожидал немного другого примера. А именно перемножения подставок на компе. Алгоритм перемножения подстановок, заданных второй строкой (первая подразумевается упорядоченной) прост до неприличия. Например, на maple это будет так

for i to n do C[i]:=B[A[i]] od:

Перемножение в цикловой форме, конечно, тоже легко запрограммировать. Но не так легко. С таким примером я бы согласился

PS: Продолжая занудствовать отмечу, что элементы подстановок при записи в цикловом виде, как правило, а в матричном виде никогда не разделяются запятыми. (При компьютерной реализации можно.)

[provincialka]

Ну, считайте, что я робот.

[VAL]

provincialka в сообщении #765125 писал(а):

Ну, считайте, что я робот.

Не верю (с).
На робота больше похож топикстартер с его манерой задать вопрос (не только в этой теме) и исчезнуть.

[Alex_CAPS]

Две строки... одна строка... В форме циклов действительно удобнее писать.
$a = (1, 2)(3, 4)$, $b = (1, 4, 2, 3)$
$ab = (1, 3, 2, 4)$
$ba = (1, 3, 2, 4)$
$b$ принадлежит централизатору.
А вот для $b = (1)(2, 3, 4)$ дела обстоят иначе:
$ab = (1, 3, 2)(4)$
$ba = (1, 2, 4)(3)$
Аналогичные результаты для $(1, 2, 4)(3)$ и прочих подстановках, обладающих циклами длины 1.
Это наталкивает на мысль, что в централизаторе должны быть элементы вида $(l, m)(n, o)$ и $(l, m, n, o)$

[VAL]

Alex_CAPS в сообщении #765220 писал(а):

Две строки... одна строка... В форме циклов действительно удобнее писать.
$a = (1, 2)(3, 4)$, $b = (1, 4, 2, 3)$
$ab = (1, 3, 2, 4)$
$ba = (1, 3, 2, 4)$
$b$ принадлежит централизатору.
А вот для $b = (1)(2, 3, 4)$ дела обстоят иначе:
$ab = (1, 3, 2)(4)$
$ba = (1, 2, 4)(3)$
Аналогичные результаты для $(1, 2, 4)(3)$ и прочих подстановках, обладающих циклами длины 1.

Дело не в цикле длины 1. Скорее уж, в цикле длины 3. Ведь я уже приводил Вам пример подстановок, имеющей циклы длины 1 и лежащей в централизаторе. Просто циклы длины 1 (петли) принято опускать при записи подстановки в цикловом виде. Вот Вы их и не заметили. На самом деле в централизаторе будет целых 3 подстановки, имеющих циклы длины 1.

Цитата:

Это наталкивает на мысль, что в централизаторе должны быть элементы вида $(l, m)(n, o)$ и $(l, m, n, o)$

Чтобы понять, как устроен централизатор, можно начать с вопроса в каких коммутативных подгруппах группы $S_4$ лежит данный в условии элемент. При этом полезно учесть, что подгруппа порядка 4 всегда коммутативна. А также то, что в $S_4$ нет коммутативных подгрупп большего порядка.
(Последнее замечание не значит, что централизатор будет иметь порядок 4.)