Транспозиция пересекающихся циклов

[myltykritik]

Здравствуйте!
Решаю задачник Кострикина по алгебре и натолкнулась на следующую задачу:

Цитата:

Определить четность подстановки:
$(1473)(67248)(32)$

Будь это транспозиция непересекающихся циклов, я бы легко привела её к виду

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & x_8 \end{pmatrix}$$

и подсчитала количество инверсий.

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

Я пыталась склеить по третьей скобке $(3 2)$, но в первых скобках помимо этих чисел есть ещё повторяющиеся, которые не дают мне сделать преобразование.
Других подходящих методов больше не нашла.

Прошу направить на путь истинный!

[Sinoid]

myltykritik в сообщении #1187801 писал(а):

Будь это транспозиция непересекающихся циклов, я бы легко привела её к виду

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & x_8 \end{pmatrix}$$

и подсчитала количество инверсий.

А что мешает вам также поступить и в этом случае? Я думал, там нужно что-то этакое, а вы согласны на простой подсчет, ну дык и посчитайте, предварительно перемножив.

[Sonic86]

myltykritik в сообщении #1187801 писал(а):

Будь это транспозиция непересекающихся циклов, я бы легко привела её к виду

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & x_8 \end{pmatrix}$$

и подсчитала количество инверсий.

Но тут транспозиция пересекающихся циклов, поэтому так просто разобраться не получается.

Вычислять произведение циклов вообще, конечно, надо уметь, но для вычисления четности подстановки саму подстановку можно не вычислять.
http://www.algebraical.info/doku.php?id ... 0%BA%D0%B8
Вычислить все произведение можно через вычисление образа элементов $\pi(j)$ для каждого $j$.

myltykritik в сообщении #1187801 писал(а):

В учебниках, в основном, пишут про то, как обычный вид представить в качестве произведения скобок с двумя элементами, но не наоборот

Ну просто попробуйте обратите процесс да и все. Начните с того, как представить простой цикл $(a_1...a_n)$ в обычном виде $j\to \pi(j)$

[myltykritik]

В целом, не понимаю, как перемножить.
И говоря «перемножить», вы имеете виду: привести к обычному виду?

Типа:

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 4 & 2 & 1 & 7 & 5 & 6 & 3 & 8 \end{pmatrix}$$

умножить на

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 1 & 4 & 3 & 8 & 5 & 7 & 2 & 6 \end{pmatrix}$$

и потом на третью скобочку?
И уже у этого посчитать инверсию?

Sinoid в сообщении #1187808 писал(а):

myltykritik в сообщении #1187801 писал(а):

Будь это транспозиция непересекающихся циклов, я бы легко привела её к виду

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & x_8 \end{pmatrix}$$

и подсчитала количество инверсий.

А что мешает вам также поступить и в этом случае? Я думал, там нужно что-то этакое, а вы согласны на простой подсчет, ну дык и посчитайте, предварительно перемножив.

[Sonic86]

myltykritik в сообщении #1187835 писал(а):

И говоря «перемножить», вы имеете виду: привести к обычному виду?

Мне без разницы - к любому виду, лишь бы умножение исчезло.

myltykritik в сообщении #1187835 писал(а):

И уже у этого посчитать инверсию?

Для решения исходной задачи я предлагаю вообще ничего не перемножать, а вычислять инверсию сразу, от произведения: $\sigma(\pi_1\cdot \pi_2)=\sigma(\pi_1)\cdot \sigma(\pi_2)$ ($\sigma$ - четность перестановки, $\pi_j$ - перестановки)

myltykritik в сообщении #1187835 писал(а):

В целом, не понимаю, как перемножить.

Ну елки, так начните с самого простого.
Перестановки - это биекции на множестве $\{1,2,...,n\}$, произведение перестановок - это обычная композиция функций: т.е. если $\pi_1(a)=b, \pi_2(b)=c$, то $(\pi_2\cdot\pi_1)(a)=\pi_2(\pi_1)(a))=c$. Например, если $\pi_1 = \binom{1 \ 2 \ 3}{2 \ 3 \ 1}, \pi_2=\binom{1 \ 2 \ 3}{3 \ 1 \ 2}$, то $\pi_2\pi_1(1)=\pi_2(2)=1,$ $\pi_2\pi_1(2)=2,\pi_2\pi_1(3)=3$, итого $\pi_2\pi_1 = \binom{1 \ 2 \ 3}{1 \ 2 \ 3}$.
Потом рассмотрите запись перестановки в виде цикла и вытащите оттуда правило умножения перестановок в виде циклов.

[vpb]

А что такое "транспозиция циклов", хоть пересекающихся, хоть нет? Разве есть такой термин? Что такое "транспозиция"?

[Brukvalub]

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

[myltykritik]

vpb, тему разбираю недавно, но, кажется, в учебниках именно так называется перемножение циклов.

-- 30.01.2017, 16:08 --

Brukvalub, а как это применимо к моему примеру? Не могу понять, как перемножать эти скобочки.

-- 30.01.2017, 16:11 --

Sonic86, спасибо!

-- 30.01.2017, 16:14 --

Sonic86 в сообщении #1187839 писал(а):

Перестановки - это биекции на множестве $\{1,2,...,n\}$, произведение перестановок - это обычная композиция функций: т.е. если $\pi_1(a)=b, \pi_2(b)=c$, то $(\pi_2\cdot\pi_1)(a)=\pi_2(\pi_1)(a))=c$. Например, если $\pi_1 = \binom{1 \ 2 \ 3}{2 \ 3 \ 1}, \pi_2=\binom{1 \ 2 \ 3}{3 \ 1 \ 2}$, то $\pi_2\pi_1(1)=\pi_2(2)=1,$ $\pi_2\pi_1(2)=2,\pi_2\pi_1(3)=3$, итого $\pi_2\pi_1 = \binom{1 \ 2 \ 3}{1 \ 2 \ 3}$.
Потом рассмотрите запись перестановки в виде цикла и вытащите оттуда правило умножения перестановок в виде циклов.

У вас здесь пример с циклами, которые я умею перемножать.
Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним.

[Sinoid]

myltykritik в сообщении #1188609 писал(а):

Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним.

Так это ничего не меняет. Смотрим, ага, в первом множителе 1 переходит в 4, во втором множителе 4 переходит в 8, в третьем множителе 8 вообще ни во что не переходит. Значит, в произведении (конечном) 1 переходит в...

-- 30.01.2017, 19:10 --

Кстати, а порядок умножения-то слева направо?

[vpb]

Да, именно так, как Вы писали в посте от 21:42 27.01, и сделайте. Если по Кострикину вдруг непонятно, как обращаются с подстановками, почитайте Куроша "Курс высшей алгебры", самое начало, там еще проще. Или ван дер Варден "Алгебра", начало гл.2.

[arseniiv]

myltykritik в сообщении #1188609 писал(а):

У вас здесь пример с циклами, которые я умею перемножать.
Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним.

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

[Sinoid]

arseniiv в сообщении #1188663 писал(а):

А совет просто в том, чтобы проследить, какой элемент в какой переходит по определению композиции перестановок.

Да тут недопонимание самого

arseniiv в сообщении #1188663 писал(а):

определения композиции перестановок

[myltykritik]

Sinoid в сообщении #1188648 писал(а):

Кстати, а порядок умножения-то слева направо?

А вот это вопрос. Уточнять буду, потому что, вроде бы, в каких-то примерах я и справа налево умножала.

-- 31.01.2017, 12:58 --

vpb в сообщении #1188660 писал(а):

Да, именно так, как Вы писали в посте от 21:42 27.01, и сделайте. Если по Кострикину вдруг непонятно, как обращаются с подстановками, почитайте Куроша "Курс высшей алгебры", самое начало, там еще проще. Или ван дер Варден "Алгебра", начало гл.2.

А вот тут ещё подняли вопрос: порядок умножения же тоже должен быть важен?
Или если я привожу к стандартному виду, то уже нет?

-- 31.01.2017, 13:03 --

arseniiv в сообщении #1188663 писал(а):

myltykritik в сообщении #1188609 писал(а):

У вас здесь пример с циклами, которые я умею перемножать.
Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним.

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

Пример, как перемножить

$$\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix}$$

и

$$\begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix}$$

встречается чуть ли не первым в учебниках, а вот $(1473)(67248)(32)$ — нет.

-- 31.01.2017, 13:04 --

Да тут недопонимание самого

arseniiv в сообщении #1188663 писал(а):

определения композиции перестановок

[/quote]

Возможно.

[arseniiv]

myltykritik в сообщении #1188832 писал(а):

а вот $(1473)(67248)(32)$ — нет

Тут всё совершенно аналогично. Будем пока так же предполагать, что умножение справа налево. Начнём, скажем, с 1: $1\mapsto1\mapsto1\mapsto4$. Будем сразу получать циклы результата, потому дальше проверим 4: $4\mapsto4\mapsto8\mapsto8$. Дальше: $8\mapsto8\mapsto6\mapsto6$. Цикл не хочет заканчиваться, ну что ж: $6\mapsto6\mapsto7\mapsto3$; $3\mapsto2\mapsto4\mapsto7$; $7\mapsto7\mapsto2\mapsto2$; $2\mapsto3\mapsto3\mapsto1$. Всё, мы знаем, что результат — это произведение цикла $(1486372)$ и ещё, возможно, каких-то непересекающихся (и с ним, и друг с другом). Здесь видно, что больше никаких, потому что больше никаких точек ни один из циклов в исходном произведении не двигал. Если бы там нашлась, скажем, 5 или 11, мы бы пошли с неё искать следующий цикл, и так до тех пор, пока необработанные точки, встречавшиеся в циклах, не кончатся.

Теперь найдите произведение $(123)(412)$.

(Ответ)

$(13)(24)$

[Sonic86]

myltykritik в сообщении #1188832 писал(а):

А вот тут ещё подняли вопрос: порядок умножения же тоже должен быть важен?

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

myltykritik в сообщении #1188832 писал(а):

Пример, как перемножить

$$\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix}$$

и

$$\begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix}$$

встречается чуть ли не первым в учебниках, а вот $(1473)(67248)(32)$ — нет.

В этих задачах нет решительно никакой разницы. Ну в крайнем случае можно циклы преобразовать в перестановки и потом их стандартно перемножить.