1610841784-4ddd8b6ff40e9cbd93e57c95925d7436 (824186), страница 13
Текст из файла (страница 13)
. . , ik ∈ {1, . . . , n}, чтоσ(i1) = i2, σ(i2) = i3, . . . , σ(ik−1) = ik , σ(ik ) = i1,и σ(j) = j для всех j 6= i1, . . . , ik .Обозначение: σ = (i1 i2 . . . ik )• (i1 i2 . . . ik ) = (i2 . . . ik i1);• (i1 i2 . . . ik )−1 = (ik . . . i2 i1);• (i1 i2 . . . ik ) = (i1 i2)(i2 . . . ik );• (−1)(i1 i2 ... ik ) = (−1)k−1Циклы длины 2 называются транспозициями,(i1 i2)−1 = (i2 i1) = (i1 i2).Разложение подстановки на независимые циклыТеорема.Любая подстановка σ ∈ Sn либо равна e, либо разлагается впроизведение независимых циклов.Это разложение единственно с точностью до перестановки циклов.Пример:σ=!1 2 3 4 5= (2 4)(1 5 3)5 4 1 2 3Доказательство.(?) Существование разложения: индукцией по числу элементов в D(σ)Если D(σ) = ∅, то σ = e.Допустим, теорема доказана для всех τ , для которых D(τ ) ⊂ D(σ) 6= ∅.Пусть i ∈ D(σ).
Рассмотримτ = (i σ(i))σТогда C(σ) ⊆ C(τ ), i ∈/ D(τ ) ⇒ D(τ ) ⊂ D(σ)По предположению индукцииτ = (i σ(i))σ = c1 . . . ck ,c1, . . . , ck — незав.циклыτ = (i σ(i))σ ⇒ σ = (i σ(i))τ = (i σ(i))c1 . . . ckПодстановка τ = c1 . . . ck не перемещает i.Если σ(i) ∈ C(τ ), то это — разложение на независимые циклы.Если σ(i) ∈ D(τ ), то выберем цикл cj , в который входит σ(i);Независимые циклы перестановочны, поэтому можно считать j = 1:c1 = (σ(i) j2 . . . jt) ⇒ (i σ(i))c1 = (i σ(i) j2 . . . jt)⇓σ = (i σ(i))c1 .
. . ck = (i σ(i) j2 . . . jt)c2 . . . ck— разложение на независимые циклы.(?) Единственность: Индукцией по числу элементов в D(σ)D(σ) = ∅ — очевидно (нет перемещаемых символов ⇒ нет циклов)Допустим, какая-то σ ∈ Sn имеет два различных разложения нанезависимые циклы:σ = c1 . . . ck = c′1 . . . c′l ,c1 = (i1 i2 . . . it).Элемент i1 входит в один из циклов второго разложения, допустим, в c′1(переставим множители при необходимости):c′1 = (i1 i′2 . . . i′p).Ноi2 = σ(i1) = i′2,i3 = σ(i2) = i′3,...,is = σ s−1(i1) = i′sдля всех s = 1, 2, . .
. . Поэтому, очевидно, p = t и c1 = c′1.Тогда′ . . . c′ ,τ = c−1σ=c...c=c2k2l1D(τ ) ⊂ D(σ).По предположению индукции k = l и cj = c′j с точностью доперестановки.Список задач к экзамену по материалам глав 1–7 (векторныепространства, матрицы, определители)http://math.nsc.ru/LBRT/a1/pavelsk/Algebra/zada4i.pdf8. Полугруппы и группы (продолжение)Разложение подстановки на независимые циклыТеорема.Любая подстановка σ ∈ Sn либо равна e, либо разлагается впроизведение независимых циклов.Это разложение единственно с точностью до перестановки циклов.Доказательство.(?) Существование разложения: индукцией по числу элементов в D(σ)Если D(σ) = ∅, то σ = e.Допустим, теорема доказана для всех τ , для которых D(τ ) ⊂ D(σ) 6= ∅.Пусть i ∈ D(σ).
Рассмотримτ = (i σ(i))σТогда C(σ) ⊆ C(τ ), i ∈/ D(τ ) ⇒ D(τ ) ⊂ D(σ)По предположению индукцииτ = (i σ(i))σ = c1 . . . ck ,c1, . . . , ck — незав.циклыτ = (i σ(i))σ ⇒ σ = (i σ(i))τ = (i σ(i))c1 . . . ckПодстановка τ = c1 . . . ck не перемещает i.Если σ(i) ∈ C(τ ), то это — разложение на независимые циклы.Если σ(i) ∈ D(τ ), то выберем цикл cj , в который входит σ(i);Независимые циклы перестановочны, поэтому можно считать j = 1:c1 = (σ(i) j2 . .
. jt) ⇒ (i σ(i))c1 = (i σ(i) j2 . . . jt)⇓σ = (i σ(i))c1 . . . ck = (i σ(i) j2 . . . jt)c2 . . . ck— разложение на независимые циклы.(?) Единственность: Индукцией по числу элементов в D(σ)D(σ) = ∅ — очевидно (нет перемещаемых символов ⇒ нет циклов)Допустим, какая-то σ ∈ Sn имеет два различных разложения нанезависимые циклы:σ = c1 . . . ck = c′1 . . . c′l ,c1 = (i1 i2 . . . it).Элемент i1 входит в один из циклов второго разложения, допустим, в c′1(переставим множители при необходимости):c′1 = (i1 i′2 . . .
i′p).Ноi2 = σ(i1) = i′2,i3 = σ(i2) = i′3,...,is = σ s−1(i1) = i′sдля всех s = 1, 2, . . . . Поэтому, очевидно, p = t и c1 = c′1.Тогда′ . . . c′ ,τ = c−1σ=c...c=c2k2l1D(τ ) ⊂ D(σ).По предположению индукции k = l и cj = c′j с точностью доперестановки.Декремент подстановкиПусть σ = c1 . . . ck — разложение на независимые циклы,длина цикла ci равна ti ≥ 2, i = 1, . . . , k.Декрементом подстановки называется числоd(σ) =kXti − ki=1(число перемещаемых элементов − число независимых циклов)Декремент единичной подстановки считается равным нулю.Предложение. Для любой σ ∈ Sn(−1)σ = (−1)d(σ)(четность декремента определяет четность подстановки).Доказательство.Для σ = e — утверждение верно по определению.Для σ 6= e рассмотрим разложение на независимые циклы:σ = c1 .
. . ck ,длина цикла ci равна tiТогда(−1)σ = (−1)c1 . . . (−1)ck = (−1)t1−1 . . . (−1)tk −1 = (−1)t1+···+tk −k ,что и требовалось.Упражнение. Можно ли в игре “15” перевести исходную раскладкукостей в приведенную ниже?Подсказка:Смоделируйте раскладку костей подстановкой из S16.Что происходит при перемещении кости?Теорема КэлиЛюбая конечная группа изоморфна подгруппе в некоторой группеподстановок.Доказательство.Пусть G = (G; ·) — некоторая группа, где G содержит n элементов,G = {g1, g2, . .
. , gn}; все они различны (gi 6= gj при i 6= j)В частности, для любого g ∈ G{gg1, gg2, . . . , ggn} = Gтак как ggi = ggj ⇒ gi = gj .Следовательноgg1 = gi1 , gg2 = gi2 , . . . , ggn = gin ,индексы i1, . . . , in попарно различны. Обозначимσg =1 2 ... ni1 i2 . . . in!Тогдаggi = gσg (i),i = 1, . . . , n.(?) Отображение ϕ : G → Sn, заданное правилом g 7→ σg , являетсяинъективным гомоморфизмом групп.Пустьϕ :g 7→ σg ,h 7→ σhдля некоторых g, h ∈ G.Тогда(gh)gi = g(hgi) = ggσh(i) = gσg (σh(i)) = g(σg σh)(i)для всех i = 1, .
. . , n. Поэтомуσgh = σg σh.Инъективность:σg = σh ⇒ ge = he ⇒ g = h.Сопряженные элементы в группеG = (G; ·) — группа, a, b ∈ G.Элементы a и b называются сопряженными в группе G,если существует x ∈ G такой, чтоx−1ax = bОбозначения:ax = x−1ax — сопряжение элемента a при помощи элемента x.a ∼G b — элементы a, b ∈ G сопряжены.Простейшие свойства сопряжения (a, b, x, y ∈ G):• a ∼G b — рефлексивность;• a ∼G b ⇒ b ∼G a — симметричность;• a ∼G b, b ∼G x ⇒ a ∼G x — транзитивность;• ax = xa ⇐⇒ ax = a;• (ab)x = axbx;• |ax| = |a|;• (a−1)x = (ax)−1;• (ax)y = axy ;Задача сопряженности подстановокПусть Sn — группа подстановок на n элементах, σ, τ ∈ Sn(?) Как определить, сопряжены ли σ, τНапример,(12) и (13) — сопряжены;(12) и (123) — не сопряжены (разные порядки);(12)(34) и (24) — тоже не сопряжены, хотя имеют одинаковый порядок(разная четность).Разбиением натурального числа n называется такой набор натуральныхчиселλ = (k1, k2, .
. . , km),что:• n ≥ k1 ≥ k2 ≥ · · · ≥ km ≥ 1;• k1 + k2 + · · · + km = n.Обозначение: λ ⊢ n(!) Всякая подстановка σ ∈ Sn однозначно определяет разбиениеλ = λ(σ) ⊢ n,которое строится следующим образом.Беремσ = c1 . . . cp— разложение на независимые циклы, длина каждого ci равна ki.Можно считать, что порядок множителей — по невозрастанию длиныциклов:k1 ≥ k2 ≥ · · · ≥ kp .Если |D(σ)| = k1 + · · · + kp < n, то допишем еще |C(σ)| = n − |D(σ)|единиц: положимλ(σ) = (k1, k2, . . . , kp, 1, . . .
, 1) ⊢ n.Пример.σ=1 2 3 4 5 6 7 8 9 105 10 1 2 3 6 4 9 8 7!Разложение на независимые циклы:σ = (1 5 3)(2 10 7 4)(8 9) = (2 10 7 4)(1 5 3)(8 9),есть один неподвижный элемент, т.е.λ(σ) = (4, 3, 2, 1) ⊢ 10Теорема. Подстановки σ и τ сопряжены в группе Sn тогда и толькотогда, когда λ(σ) = λ(τ ).Доказательство.Пусть σ и τ сопряжены:σ = τ x = x−1τ x,x ∈ Sn .Тогдаτ = xσx−1.Пусть σ = c1 . . . cp — разложение на независимые циклы. Тогдаτ = xc1 . . . cpx−1 = xc1x−1 · xc2x−1 · · · · · xcpx−1.Пусть c = ci — любой из этих циклов, допустим, длины k. Рассмотримxcx−1 = x(i1 . . .
ik )x−1Как действует эта подстановка на {1, . . . , n} = {x(1), . . . , x(n)}?При j 6= i1, . . . , ik :x−1cxx(j) 7→ j 7→ j 7→ x(j)При j = it, t = 1, . . . , k − 1:x−1xcx(j) = x(it) 7→ it 7→ it+1 7→ x(it+1)При j = ik :x−1cxx(ik ) 7→ ik 7→ i1 7→ x(i1)Таким образом,xcx−1 = x(i1 . . . ik )x−1 = (x(i1) . . . x(ik ))— снова цикл длины k.Следовательно,−1τ = cx1−1· cx2−1· · · · · cxp— разложение τ на независимые циклы, каждый цикл имеет в точноститу же длину, что в разложении подстановки σ.Поэтому λ(σ) = λ(τ ).Обратно: пусть λ(σ) = λ(τ ).Тогдаσ = c1 . . . cp ,τ = d1 .
. . dp— разложение на независимые циклы, причем длина ci равна длине diдля всех i = 1, . . . , p.Как показано выше,−1(i1 . . . ik )x= (x(i1) . . . x(ik ))Поэтому можно легко построить подстановку x ∈ Sn такую, что cxi = diдля всех i = 1, . . . , p.Тогда σ x = τ .Упражнение. Решить уравнение в группе S5:x!!1 2 3 4 51 2 3 4 5=x.4 3 2 5 13 5 4 1 2Упражнение. Доказать, что группа Sn порождается множеством всехтранспозиций вида (1i), i = 2, . . .
, n.Упражнение. Доказать, что группа всех четных подстановок An ≤ Sn(при n ≥ 3) порождается множеством всех тройных циклов вида (12i),i = 3, . . . , n.Теорема о полном раскрытии определителяSn — группа подстановок на n элементах; F — поле;a11 . . . a1nA = . . . . .
. . . . . . . . ∈ Mn(F )an1 . . . ann— матрица размера n × n с компонентами aij ∈ F .Теорема.det A =Xσ∈Sn(−1)σ a1 σ(1) . . . an σ(n)(?)det A =X(−1)σ a1 σ(1) . . . an σ(n)σ∈SnПримеры.n = 1:S1 = {e}, det(a11) = a11n = 2:S2 = {e, σ = (12)},!aadet 11 12 = (−1)ea1 e(1)a2 e(2) + (−1)σ a1σ(1)a2 σ(2) = a11a22 − a12a21.a21 a22(?)det A =X(−1)σ a1 σ(1) . . . an σ(n)σ∈SnДоказательство.Покажем, что правая часть доказываемой формулы являетсяполилинейной кососимметричной нормированной функцией строкматрицы.D(A) =Xσ∈Sn(−1)σ a1 σ(1) . .
. an σ(n)(?) Полилинейность (по строкам):AA ..1 ..1 . . A = A i , B = Bi , ... ... AnAnC=αAiA1...+ βBi,...AnТогдаD(C) ==X(−1)σ aσ∈SnX=α1 σ(1) . . . ai−1 σ(i−1) αai σ(i) + βbiσ(i) ai+1 σ(i+1) . . . an σ(n)(−1)σ a1 σ(1) . . . ai−1 σ(i−1)ai σ(i)ai+1 σ(i+1) . .
. an σ(n)σ∈Sn+βX(−1)σ a1 σ(1) . . . ai−1 σ(i−1)bi σ(i)ai+1 σ(i+1) . . . an σ(n)σ∈Sn= αD(A) + βD(B).(?) Кососимметричность (по строкам)Пусть в матрице A две строки совпадают: при некоторых i < jaik = ajk для всех k = 1, . . . , n.Поделим все подстановки из Sn на два класса:M1 = {σ ∈ Sn | σ(i) < σ(j)},M2 = {σ ∈ Sn | σ(i) > σ(j)}.Заметим, чтоσ ∈ M1 ⇐⇒ σ(ij) ∈ M2Таким образом, имеется взаимно-однозначное соответствиемежду множествами M1 и M2:M2 = {σ(ij) | σ ∈ M1}.ТогдаD(A) ==Xσ∈SnX(−1)σ a1 σ(1) . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
