Разложение подстановки в произведение транспозиций

Primary tabs

Forums:

Разложение подстановок на транспозиции. Покажем, что всякую подстановку можно представить в виде произведения нескольких транспозиций, т.е. подстановок, перемещающих две цифры и оставляющих остальные цифры неизменными. Выше мы видели, что всякую подстановку можно представить в виде произведения циклов. Поэтому достаточно проверить наше утверждение для цикла. Последнее проверить нетрудно. В самом деле:
$$
(123) = (12)(13),\
(1234) = (12)(13)(14)\
. \
(123 . m) = (12)(13) . (1m)
$$
Обратим здесь внимание на то, что циклы с четным числом цифр разлагаются на нечетное число транспозиций, с нечетным числом цифр — на четное число транспозиций.

Поэтому для каждой данной подстановки мы можем высчитать, разложится ли она на четное или на нечетное число транспозиций. Действительно, если подстановка состоит из циклов порядков:
$$n_1, n_2, ldots, n_k ;;;; (n_1 + n_2 + ldots +n_k=n)$$
то четность получаемого числа транспозиций зависит от того, будет ли число (разница между числом элементов в подстановке и числом циклов):
$$
(n_1-1)+(n_2-1)+ldots+(n_k-1)=n-k
$$

четным или нечетным. При этом мы должны также принять в расчет и одночленные циклы.

Пример. Подстановка $(123)(45)(67)(8)$. Число $(n-k)$ здесь равно $8-4=4$, а потому подстановка разлагается на четное число транспозиций.

Здравствуйте! Не могу понять, как раскладывать подстановку в произведение транспозиций. $$egin 1 & 2& 3& 4& 5\ 2 & 3& 1& 5& 4 end=(123)cdot(45)$$ Здесь транспозицией является только (45), но цикл (123) как раскладывать в произведение транспозиий?

задан 8 Фев ’15 17:32

ubuntu
53 ● 1 ● 7
85&#037 принятых

2 ответа

Разложение подстановки в произведение независимых циклов устроено просто, поэтому достаточно уметь представлять цикл произвольной длины в виде произведения транспозиций. Закономерность здесь достаточно простая: (abc)=(ab)(ac); (abcd)=(ab)(ac)(ad); (abcde)=(ab)(ac)(ad)(ae), и так далее. Каждое из равенств легко проверяется непосредственно.

Читайте также  Сбросить пароль eset nod32

Смысл у этого дела такой: если на полке стоят тома с номерами 1, 2, . , n по порядку, и надо том 1 поставить на последнее место без нарушения порядка следования других томов, то достаточно поменять местами 1 и 2, потом 1 и 3, и так далее, и в конце 1 и n. Это требует n-1 шага. Быстрее сделать нельзя, даже если разрешить менять местами два тома, не стоящие рядом.

отвечен 8 Фев ’15 17:53

falcao
243k ● 1 ● 34 ● 48

Спасибо! Как я понял, вы пользовались правилом композиции $$(pi varphi) (i) =
ho (pi (i))$$?

@ubuntu: композицию преобразований можно рассматривать по-разному, в зависимости от принятого соглашения. Когда мы пишем $%fcirc g$%, то первым может выполняться как $%f$%, так и $%g$%. Перестановки же обычно перемножаются справа налево. Скажем, (12)(13)=(123), так как 2 при первом преобразовании переходит в 1, а 1 при втором переходит в 3, то есть при композиции 2 перешло в 3.

Понял. Просто нас учили перемножать слева направо, тогда цикл (abcd) = (ad)(ac)(ab)?

@ubuntu: прошу прощения, я оговорился — сказал наоборот. Конечно, имелось в виду слева направо, то есть всё совпадает. При этом (abcd)=(ab)(ac)(ad).

Объясните пожалуйста доступным языком как раскладывать подстановки в произведение транспозиций?

Насколько я понял если есть подстановка:
1 2 3 4
2 1 4 3

То её транспозиция это
1 2 3 4
1 2 4 3

То есть просто в нижней перестановке делаем одну транспозицию. Данную транспозицию можно записать как (2 1).
А вот как разложить подстановку на произведение транспозиций я не понимаю(((

В учебнике Куроша есть пример с разложением перестановки на произведение транспозиций. Я заметил такую вещь что само по себе произведение транспозиций в чистом виде не может служить алгоритмом для приведения перестановки к тождественной:

Ссылка на основную публикацию
Adblock
detector