2016.10.28_subst-1-solutions (Семинары с решением 2016)

Новосибирский государственный университетМеханико-математический факультетКафедра алгебры и математической логики, 2016–2017г.Перестановки28 октября • 16135 группа1. (Выполните) умножение()1 2 3 41 2 3 4а)·.4 1 3 23 2 4 1() ()1 2 3 4 51 2 3 4 5б)·.2 4 5 1 35 3 4 1 2()−1()a1 a2 . . . a na a . . . anв)· [цикл!] (a1a2 . . . an) · 1 2.b 1 b 2 . . . bnb1 b2 . . . b n() () ()1 2 3 41 2 3 41 2 3 4Решение. а)·=.4 1 3 23 2 4 11 3 4 2() () ()1 2 3 4 51 2 3 4 51 2 3 4 5б)·=.2 4 5 1 35 3 4 1 23 1 2 5 4(a1 a2 . . .в)b1 b2 . . .(b b= 1 2a1 a2)−1)(ana a . .

. an· (a1a2 . . . an) · 1 2bnb1 b2 . . . bn)) () (a a . . . ana a . . . an. . . bn· 1 2· 1 2b1 b2 . . . bn. . . ana2 a3 . . . a 1)(b b . . . bn= (b1b2 . . . bn).= 1 2b2 b3 . . . b 12. (Вычислите)2()1001 2 3 41 2 3 4 5 6 7 8 9 10а),б).2 3 4 13 5 4 1 7 10 2 6 9 8() () ()1 2 3 41 2 3 41 2 3 4Решение. а)·=.2 3 4 12 3 4 13 4 1 2б) Обозначим данную перестановку через σ, нам нужно вычислить σ 100. Легко проверить, что σ 3 = e — тождественная перестановка (как до этого догадаться, см. задачу №9).

Тогдаσ 100 = σ · (σ 3)33 = σ · e = σ.13. Докажите, что любую перестановку можно разложить напроизведение транспозиций, т.е. перестановок такого вида:()1 2 ... i ... j ... n(ij) =.1 2 ... j ... i ... nПервое доказательство. Можно вести индукцию по n. Слу( )1чай n = 1 может быть не ясен (единственная перестановка1есть пустое произведение транспозиций), разложим обе перестановки при n = 2:( )( )1 21 2= (12)(12),= (12).1 22 1Если 1 под действием перестановки σ ∈ Sn остаётся на месте,можно считать, что σ есть перестановка элементов множества{2, 3, . .

. , n}, состоящего из n − 1 элементов, для него по индукционному предположению всё доказано. Пусть 1 под действием σ переходит в число i ̸= 1. Представим σ как σ = σ ′(1i) или σ ′ = σ(1i).Несложно понять, что в перестановке σ ′ элемент 1 остаётся на месте, а значит, как мы отметили выше, σ ′ разлагается в произведениетранспозиций τ1τ2 . . . τk . Тогда σ = σ ′(1i) = τ1τ2 . . . τk (1i) — искомоеразложение.Второе доказательство. Достаточно воспользоваться задачами №4 и №5б.

По задаче №4 разложим произвольную перестановку σ ∈ Sn в произведение независимых циклов σ = δ1δ2 . . . δk .Каждый цикл вида (a1a2 . . . as) по задаче №5б есть(a1a2 . . . as) = (a1a2)(a1a3) . . . (a1an−1)(a1an).4. Докажите, что любую перестановку можно разложить напроизведение независимых циклов.Доказательство. Рассмотрим только действительно перемещаемые элементы (формально можно и остающиеся на месте элементы воспринимать как элементы цикла длины один: (i)). Если есть, то рассмотрим наименьший действительно перемещаемыйэлемент, пусть это i1.

Он переходит в i2. Смотрим далее, куда перейдёт i2 и т.д., пока не зациклимся, т.е. найдётся ik , переходящее в i1. Описанный процесс обязанзациклиться, поскольку не2более, чем за n шагов мы перечислим все элементы множества{1, 2, 3, . . . , n}. Если процесс закончится, но элемент a1 так и невстретиться, это будет означать, что наша “перестановка” перевеламножество {i1, i2, . . . , ik } в меньшее множество {i2, i3, . . . , ik }. Этопротиворечит тому, что перестановка есть биекция (взаимно однозначное соответствие).Значит, выделив цикл (i1i2 . .

. ik ), смотрим, остались ли ещё действительно перемещаемые элементы. Если есть, то рассмотрим наименьший оставшийся действительно перемещаемый элемент, смотрим, в какой элемент он переходит и т.д. Ясно, что процесс конечен,а элементы полученных циклов не повторяются. Это и будет разложение изначальной перестановки в произведение независимыхциклов (т.е. циклов, не имеющих обших элементов).5.

(Разложите следующиеперестановки на независимые циклы:)1 2 3 4 5а),б) (12)(13)(14)(15)(16),4 1 5 2 3()()1 2 3 4 5 61 2 3 4 5 6в),г),6 5 1 4 2 34 5 6 1 2 3()1 2 3 4 . . . 2n − 3 2n − 2 2n − 1 2nд).3 4 5 6 . . . 2n − 1 2n12()1 2 3 4 5Решение. а)= (142)(35),4 1 5 2 3б) (12)(13)(14)(15)(16)() = (123456),1 2 3 4 5 6в)= (163)(25),6 5 1 4 2 3)(1 2 3 4 5 6= (14)(25)(36),г)4 5 6 1 2 3)(1 2 3 4 . . .

2n − 3 2n − 2 2n − 1 2nд)3 4 5 6 . . . 2n − 1 2n12= (135 . . . (2n − 3) (2n − 1))(246 . . . (2n − 2) 2n).6. В задании 5 вычислите чётность перестановок.NrealРешение.Поформулеsgn(σ)=(−1)− ncycle имеем)(1 2 3 4 5= sgn [(142)(35)] = (−1)5−2 = −1,а) sgn4 1 5 2 33б) sgn [(12)(13)(14)(15)(16)]= (−1)6−1 = −1,()1 2 3 4 5 6в) sgn= sgn [(163)(25)] = (−1)5−2 = −1,6 5 1 4 2 3()1 2 3 4 5 6г) sgn= sgn [(14)(25)(36)] = (−1)6−3 = −1,4 5 6 1 2 3)(1 2 3 4 . .

. 2n − 3 2n − 2 2n − 1 2nд) sgn3 4 5 6 . . . 2n − 1 2n12= sgn [(135 . . . (2n − 3) (2n − 1))(246 . . . (2n − 2) 2n)] = (−1)2n−2 = 1.7. Докажите, что sgn(σπ) = sgn(σ) · sgn(π).Доказательство. Пусть σ = τ1τ2 . . . τk , π = τ1′ τ2′ . . . τl′ — разложения перестановок σ и π в произведение транспозиций. Тогда sgn (σ) = (−1)k , sgn (π) = (−1)l . Легко получить разложениеσπ в произведение транспозиций: σπ = τ1τ2 . . . τk τ1′ τ2′ .

. . τl′, тогдаsgn (σπ) = (−1)k+l . Остаётся понять, что утверждение задачи эквивалентно равенству (−1)k · (−1)l = (−1)k+l , что очевидно.8. Докажите, что если некоторая степень s цикла равна единице,то s делится на длину цикла.Доказательство. Пусть σ = (a1a2 . . . as). Заметим, что в перестановке σ k элемент a1 переходит в ak+1 mod s, где x mod s означает остаток при делении x на s. При k < s элемент a1 не равенa1, а k = s — наименьшая степень, когда элемент a1 переходит всебя, также, как и все остальные ai.

Значит, |σ| = s. Утверждениезадачи следует из задачи №4, Группы-2.9. Докажите, что порядок перестановки равен НОКу длин циклов, входящих в разложение перестановки.Доказательство. Пусть перестановка σ разлагается в произведение независимых циклов: σ = δ1δ2 . . . δk и li — длина цикла δi. Если k = 1, утверждение было фактически доказано в решении задачи №8.

Если k = 2, то утверждение задачи следуетиз задачи 7б, Группы-2. При k > 2 легко получить утверждение по индукции. Обозначим δk−1δk через π. Тогда по индукционному предположению и свойству НОКа [l1, l2, . . . , lk−2, [lk−1, lk ]] =4[l1, l2, . . . , lk−2, lk−1, lk ] имеем|σ| = |δ1δ2 . . .

δk−2π| = [l1, l2, . . . , lk−2, |π|]= [l1, l2, . . . , lk−2, [lk−1, lk ]] = [l1, l2, . . . , lk−2, lk−1, lk ].10. Докажите, что любая перестановка разлагается на произведениеа) транспозиций вида (1i),б) тройных циклов вида (ijk), если перестановка чётная;в) тройных циклов вида (12k), если перестановка чётная;Доказательство. а) По задаче №3 любая перестановка разлагается в произведение транспозиций, а всякая транспозиция (ij)разлагается в произведение транспозиций указанного вида: (ij) =(1i)(1j(1i)).б) По задаче №3 и определению чётной перестановки произвольная чётная перестановка есть σ = τ1τ2τ3τ4 . . .

τ2k−1τ2k , при этом можем считать, никакие две соседние транспозиции не равны (иначеих произведение равно e и такую пару можно сократить). Докажем,что произведение соседних транспозиций разлагается в произведение тройных циклов. Пусть нас интересует произведение (ij)(kl).Если среди чисел i, j, k, l есть повторяющееся, например, i = k, тогда (ij)(il) = (ijl) — тройный цикл. Если среди чисел i, j, k, l нетповторений, тогда (ij)(kl) = (ijk)(ilk).в) По п.

а) чётная перестановка разлагается в произведение чётного числа транспозиций вида (1i) (также полагаем, что никакиедве соседние транспозиции не совпадают). Соберём их, как в п. б), впары. Пусть нас интересует произведение (1i)(1j), оно равно (1ij).Если i = 2, утверждение доказано. Пусть i ̸= 2. Если j = 2, то(1i2) = (12i)(12i).

Пусть j ̸= 2, тогда (1ij) = (12i)(12i)(12j).5.