Упражнения. 1. Проверить, что, s s+1x =s x, s s+2x =s 2x, s -1x = s s-1x, , s(О(x))=О(х), s k(О(х)) = О(x), О(sx) =О(х)

1. Проверить, что, s ^s+1x =s x, s ^s+2x =s ²x, s ^-1x = s ^s-1x, …, s(О(x))=О(х), s ^k(О(х)) = О(x), О(sx) =О(х), О(s ^kх) = О(x), О(х) = {s ^kx| k =0,1, 2,…, s-1 } = {s ^kx| k Î Z }.

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

Таким образом, множество Х разбивается в объединение непересекающихся циклов.

Пусть х = a₁, s x = a₂ , s ²x = a₃ , s ³x = a₄ ,…, s ^s-1x = a_s, и соответственно цикл О(х) ={a₁, a₂ ,.., a_s}. Тогда s(О(x))= О(х), и s на О(x) является биекцией, которую можно записать в виде таблицы или в виде таблицы с одной строкой: (a₁, a₂, a₃,…, a_s). Запись s в виде такой строки означает, что s a₁= a₂, s a₂= a₃ ,…,s a_s-1= a_s, s a_s= a₁ . Записывая подстановку на каждом цикле в виде одной строки, получим циклическую запись подстановки. Так, например, подстановка

s = в циклической записи имеет вид s =(1, 4, 2, 5)(3)(6, 8, 7).

Определение. Транспозицией будем называть подстановку t_ij такую, что t_ij (i)= j, t_ij (j) = i, t_ij (k) = k при k ¹ i, k¹j.

Очевидно, t_ij^-1 = t_ij, t_ij² = t_ij.

Утверждение. Любую подстановку s Î S_n, п ³ 2, можно разложить в композицию транспозиций.

Доказательство по индукции.

1. При п =2 утверждение очевидно, так как S₂ состоит из двух элементов: id и t_ij.

2. Пусть для п – 1 утверждение верно. Рассмотрим s Î S_n. Пусть s(п) = q, и s₁ = t_qns. Тогда s₁ (n) = n, и s₁ – биекция множества {1, 2, 3, …, n -1 } из (п-1)- го элемента. По предположению индукции можно считать, что для s₁ утверждение верно, то есть s₁=t₁t₂…t_r - композиция транспозиций. Но s = t_qn^-1s₁ = t_qns₁ = t_qnt₁t₂…t_r - композиция транспозиций.



Очевидно, разложение подстановки в композицию транспозиций неоднозначно.

На практике очень легко раскладывать подстановку в произведение транспозиций, если она задана в циклической записи. Так, например, легко проверить, что

(1, 3, 7, 2, 4)(5, 6)(8) = t₁₃t₃₇t₇₂t₂₄t₅₆.

Будем говорить, что в последовательности чисел i₁, i₂ ,..,i_n два числа i_k и i_l образуют инверсию, если i_k > i_l, но i_k расположено левее i_l. Подстановка s = называется четной, если количество инверсий в её нижней строке

че­тно, и s называется нечетной, если количество инверсий в

её нижней строке нечетно.

Утверждение. Если количество инверсий в нижней строке подстановки s равно m, то s можно разложить в произведение m транспозиций.

Доказательство. Пусть два соседних элемента i_k и i_k+1 в нижней строке подстановки s образуют инверсию. Тогда

s₁=s =, и число инверсий в нижней строке у s₁ равно m – 1. Продолжая эту процедуру далее, получим, что существуют транспозиции t₁ ,t₂ , …,t_m такие, что подстановка t_mt_m-1…t₁s не имеет инверсий в нижней строке, то есть t_mt_m-1…t₁s = id. Умножая последнее равенство слева на t_m, затем на t_m-1 и так далее до t₁, и учитывая, что все t_i²= id, получим, что s = t₁t₂…t_m.



Лекция 4.

Дата добавления: 2014-01-04