Алгебра

куба; e) ребер куба. Пiсля нумерацiї елементiв вiдповiдної множини натуральними числами одержуємо гомоморфiзм групи O в групу: a) S3; b) S4; c) S6; d) S8; e) S12. Усi цi дiї групи O, крiм першої, є точними. Ядром першої дiї є пiдгрупа порядку 4, що складається з тотожного перетворення i поворотiв на 180◦ навколо осей, що проходять через центри протилежних граней.

2. Можна кiлькома природними способами визначити дiю довiльної групи G на множинi G˙ своїх же елементiв. Найважливiшими з них є:

a)дiя правими зсувами: xg = xg (т. зв. регулярне зображення групи, воно вже зустрiчалося при доведеннi теореми Келi); i

b)дiя спряженнями: xg = g−1xg.

Перша дiя є точною, а ядром другої дiї є центр Z(G) групи G.

3.Узагальненням регулярного зображення є дiя групи правими зсувами на правих класах сумiжностi за довiльною пiдгрупою H: (Hx)g =

Hxg.

4.Iз кожною дiєю групи G на множинi M природно пов’язується

цiлий ряд т. зв. iндукованих дiй цiєї групи, зокрема, на множинi M(k) =

{A M |A| = k} k–елементних пiдмножин множини M за правилом

Ag = {ag | a A} i на множинi Mk = {(m1, . . . , mk) | m1, . . . , mk M}

наборiв довжини k за правилом (m1, . . . , mk)g = (mg1, . . . , mgk).

Кожна дiя групи G на множинi M визначає певне вiдношення еквiвалентностi на множинi M:

a b iснує такий елемент g G, що ag = b.

Вправа 18.1. Перевiрте, що це справдi вiдношення еквiвалентностi.

Класи еквiвалентностi O цього вiдношення називаються орбiтами групи G. Легко бачити, що довiльнi двi орбiти або збiгаються, або не перетинаються, а тому множина M розбивається в диз’юнктне об’єднання орбiт M = ti I Oi. Також позначимо символом O(a) або aG множину {ag | g G}, яку природно назвати орбiтою точки a M.

Твердження 18.3. Нехай задана дiя (G, M) групи G на множинi M. Тодi для довiльного елемента a орбiти O матимемо O = O(a).

Доведення. Нехай b O, b 6= a. Тодi iснує g G такий, що ag = b. Звiдки включення O O(a) легко випливає. I навпаки, якщо b O(a), то знайдеться такий елемент g G, що b = ag, а тому a b i b O.

81

Наслiдок 18.1. Якщо група G дiє на множинi M, то для довiльних a, b M a b O(a) = O(b).

Таким чином, орбiта точки a M це клас еквiвалентностi, що мiстить точку a.

Приклади. 1. Для природної дiї групи G всiх поворотiв площини навколо фiксованої точки O на множинi точок площини орбiтами будуть кола з центром у точцi O.

2.При природнiй дiї групи ортогональних перетворень на множинi векторiв арифметичного векторного простору орбiтами будуть множини векторiв однакової довжини.

3.Для дiї групи G на собi спряженнями орбiтами будуть класи спряжених елементiв групи G. Зокрема, у випадку групи GLn(C) це будуть класи невироджених матриць з однiєю i тiєю ж нормальною жордановою формою.

4.Група може дiяти по–рiзному навiть на однiй i тiй же множинi. Наприклад, дiю нециклiчної групи G = {e, a, b, c} порядку 4 на множинi M = {1, 2, 3, 4} можна визначити так, щоб її елементам вiдповiдали пiдстановки ϕ(e) = ε, ϕ(a) = (12)(34), ϕ(b) = (13)(24), ϕ(c) = (14)(23), а

можна елементам групи G зiставити пiдстановки ϕ(e) = ε, ϕ(a) = (12), ϕ(b) = (34), ϕ(c) = (12)(34). Тодi у першому випадку матимемо лише

одну орбiту M, а в другому двi орбiти O1 = {1, 2} i O2 = {3, 4}.

Вправа 18.2. Нехай H пiдгрупа групи G. Доведiть, що кожне з правил gh = gh i gh = h−1g визначає дiю пiдгрупи H на множинi G˙ елементiв групи G. Знайдiть орбiти цих дiй.

Група пiдстановок (G, M) називається транзитивною, якщо вона має лише одну орбiту (тобто для довiльних x, y M знайдеться такий елемент g G, що xg = y), та iнтранзитивною, якщо орбiт бiльше однiєї.

Зауваження. 1. Ранiше (див. приклад 3 на стор. 81) з кожною пiдгрупою H < G ми зв’язали зображення групи G взаємно однозначними перетвореннями множини правих класiв сумiжностi G за пiдгрупою H. Таке зображення є транзитивним, бо якщо Hg1, Hg2 два правi класи сумiжностi, то (Hg1)g1−1g2 = Hg2. Насправдi, має мiсце i зворотне: кожне транзитивне зображення даної групи взаємно однозначними пе-

82

ретвореннями подiбне зображенню цiєї групи правими зсувами на множинi правих класiв сумiжностi за деякою пiдгрупою.

2. Транзитивнi дiї у певному сенсi можна вважати найпростiшими дiями групи, а iнтранзитивнi як узгодження кiлькох транзитивних дiй групи на рiзних орбiтах.

Дiя (G, M) називається k–транзитивною, якщо iндукована дiя групи G на множинi M[k] усiх тих наборiв (m1, . . . , mk) довжини k, компоненти m1, . . . , mk яких є попарно рiзними, є транзитивною. Iншими словами, дiя (G, M) є k–транзитивною, якщо для довiльних двох наборiв m1, . . . , mk та m˜ 1, . . . , m˜ k iз множини M, елементи кожного з яких є попарно рiзними, iснує такий g G, що mg1 = m˜ 1, . . . , mgk = m˜ k.

Задача 18.1. Нехай χ(g) кiлькiсть нерухомих точок елемента g G при дiї групи G на множинi M. Доведiть, що: a) для 2–транзитивної групи G

X

χ2(g) = 2 · |G|;

g G

b) для 3–транзитивної групи G

X

χ3(g) = 5 · |G|.

g G

Вказiвка. a) Якщо χ(g) i χ0(g) кiлькiсть нерухомих точок елемента g при дiї G на M i M[2] вiдповiдно, то Pg G χ(g) = |G| i Pg G χ0(g) = |G|. Додайте цi рiвностi i врахуйте, що χ0(g) = χ(g)(χ(g) − 1).

Задача 18.2. Доведiть, що: a) група Sn є n−транзитивною; b) група An є (n − 2)−транзитивною i не є (n − 1)−транзитивною.

Пiдмножина N M називається iнварiантною вiдносно дiї групи

G, якщо mg N для всiх m N i g G. Очевидно, що пiдмножина є iнварiантною тодi й лише тодi, коли вона є об’єднанням орбiт групи G. Тому для кожної iнварiантної пiдмножини N можна розглядати обмеження (G, N) дiї групи G на цю пiдмножину.

Точка m M називається нерухомою вiдносно елемента g G, якщо mg = m. Точки, нерухомi вiдносно усiх елементiв групи G це просто 1–елементнi орбiти групи G. Множина {g G | mg = m} називається стабiлiзатором точки m i позначається StG(m) або коротко St(m). Очевидно, що для кожної точки m M її стабiлiзатор StG(m) є пiдгрупою групи G.

83

Теорема 18.1. Нехай група G дiє на множинi M. Тодi iснує природна взаємно однозначна вiдповiднiсть мiж елементами орбiти O(m) i правими класами сумiжностi групи G за пiдгрупою StG(m). Зокрема, |O(m)| = |G : StG(m)|, тобто довжина орбiти точки дорiвнює iндексовi її стабiлiзатора.

Доведення. Нехай a O(m). Виберемо такий елемент g G, що a = mg. Тодi

mh = a (mh)g−1 = m hg−1 StG(m) h StG(m) · g.

Таким чином, кожнiй точцi a O(m) природно зiставляється правий клас сумiжностi StG(m) · g тих елементiв групи G, якi точку m переводять в a.

Наслiдок 18.2. a) Потужнiсть |O(m)| орбiти точки m дiлить порядок |G| групи G.

b) Стабiлiзатори точок, що належать однiй орбiтi, мають однаковий порядок.

Приклад. Знайдемо nk кiлькiсть k–елементних пiдмножин множини M, яка складається з n елементiв. Для цього розглянемо природну дiю симетричної групи Sn на множинi M{k} k–елементних пiдмножин множини M = {1, . . . , n}. Така дiя є транзитивною. Нехай A = {i1, . . . , ik} довiльна пiдмножина iз M{k}. Тодi стабiлiзатор StSn (A) складається iз усiх тих пiдстановок множини M, якi переставляють тiльки точки всерединi кожної з множин A та M\A. А таких пiдстановок, як легко бачити, буде |A|! · |M\A|! = k! · (n − k)!. Крiм того,

|M{k}| = |O(A)| = |Sn : StSn (A)| = |StSn!(A)|.

n

Наслiдок 18.2 b) можна трохи посилити:

Твердження 18.4. Стабiлiзатори точок, що належать до однiєї орбiти, є спряженими пiдгрупами.

Доведення. Оскiльки згiдно твердження 18.3 орбiта O збiгається з орбiтою довiльного елемента m, що їй належить, то досить показати, що для довiльнних m M та g G St(mg) = g−1St(m)g. Нехай

84

g˜ St(m). Тодi (mg)g−1gg˜ = mgg−1gg˜ = (mg˜)g = mg i g−1gg˜ St(mg).

Тому St(mg) g−1St(m)g. З iншого боку, для h St(mg) матимемо:

(mg)h = mg, звiдки mghg−1 = m i ghg−1 St(m). Тобто h g−1St(m)g i St(mg) g−1St(m)g. Отже, St(mg) = g−1St(m)g.

Задача 18.3. Доведiть, що у скiнченнiй p–групi число тих пiдгруп, якi не є нормальними, дiлиться на p.

Вказiвка. Розгляньте дiю групи спряженнями на множинi своїх пiдгруп.

Дiя групи на рiзних множинах є дуже ефективним методом дослiдження груп. Фактично ми вже ним користувалися. Так, при доведеннi теореми Келi (теорема 7.1) використовувалося регулярне зображення групи, а при доведеннi леми Кошi (наслiдок 11.3) i неодиничностi центра скiнченної неодиничної p–групи (теорема 15.1) формула класiв (теорема 11.3), в якiй йдеться про потужностi класiв спряженостi, тобто про довжини орбiт при дiї групи на собi спряженнями. Використовуючи iншу дiю, можна дати значно коротше доведення леми Кошi.

Нове доведення леми Кошi. Нехай порядок |G| групи G дiлиться на просте число p. Розглянемо множину

M = {(g1, g2, . . . , gp) | g1, g2, . . . , gp G, g1g2 · · · gp = e}

i визначимо дiю на M групи Zp таким правилом:

¯

(g1, g2, . . . , gp)k = (gp−k+1, gp−k+2, . . . , gp, g1, g2, . . . , gp−k) .

Множина M мiстить |G|p−1 наборiв, тому її потужнiсть |M| дiлиться на p. За теоремою 18.1 орбiти групи Zp мають порядок 1 або p. Оскiльки одна 1–елементна орбiта напевно є це {(e, e, . . . , e)}, то мусять бути й iншi 1–елементнi орбiти. Кожна така орбiта має вигляд {(g, g, . . . , g)}. Але тодi g елемент порядку p.

У багатьох задачах належнiсть чи неналежнiсть елементiв множини M до однiєї орбiти дiї певної групи G на M є основою класифiкацiї цих елементiв. Наприклад, в геометрiї рiвнiсть двох плоских фiгур визначається саме як їх належнiсть до однiєї орбiти при природнiй дiї групи рухiв площини на множинi фiгур. У теорiї графiв можна розглянути природну дiю симетричної групи Sn на множинi всiх n–вершинних графiв iз множиною вершин V = {1, 2, . . . , n}: пiдстановка π Sn задає

85

перенумерацiю вершин графа, коли вершина зi старим номером i одержує новий номер π(i). Тодi належнiсть двох n–вершинних графiв до однiєї орбiти групи Sn означає їх iзоморфнiсть. У таких випадках дуже корисно вмiти знаходити кiлькiсть орбiт групи G.

Лема 18.1 (Кошi–Фробенiуса–Бернсайда). Нехай скiнченна група

G дiє на скiнченнiй множинi M. Тодi

де χ(g) кiлькiсть нерухомих точок елемента g.

Доведення. Пiдрахуємо двома способами кiлькiсть таких пар (g, m), в яких g G, m M i mg = m. З одного боку, вона дорiвнює Pg G χ(g).

P

З iншого боку, кiлькiсть таких пар дорiвнює m M |St(m)|. Щоб перетворити останню суму, розглянемо всi орбiти M1, M2, . . . , MN групи G i в кожнiй орбiтi Mi виберемо представника mi. Враховуючи теорему 18.1 i наслiдок 18.2 b), маємо:

XX

P

Таким чином, g G χ(g) = N · |G|, що й доводить твердження.

Зауваження. Функцiя χ : G → N0, g 7→χ(g), називається пiдстановочним характером групи G. Якщо група транзитивна, то з леми

P

Кошi–Фробенiуса–Бернсайда випливає, що g G χ(g) = |G|, тобто в цьому випадку кожен елемент групи G має в середньому рiвно 1 нерухому точку.

Задача 18.4. Доведiть, що кожна пiдстановка з симетричної групи Sn має в середньому рiвно 1/k циклiв довжини k (k = 1, 2, . . . , n).

Лема Кошi–Фробенiуса–Бернсайда має численнi застосування в комбiнаторному аналiзi, де вона використовується для пiдрахунку рiзних комбiнаторних об’єктiв.

86

Приклади. 1. Кожна грань куба фарбується в один iз даних k кольорiв. При фiксованому розмiщеннi куба в просторi маємо, очевидно, k6 рiзних розфарбувань. На множинi M цих розфарбувань природно дiє група O поворотiв куба. Назвемо два розфарбування геометрично рiзними, якщо одне з них не можна перевести в iнше жодним поворотом куба. Пiдрахуємо кiлькiсть геометрично рiзних розфарбувань.

Група O мiстить такi елементи: a) 1 тотожне перетворення; b) 6 поворотiв навколо осей, що проходять через центри протилежних граней, на кути ±90◦; c) 3 повороти навколо осей, що проходять через центри протилежних граней, на кут 180◦; d) 8 поворотiв навколо осей, що проходять через протилежнi вершини, на кути ±120◦; e) 6 поворотiв навколо осей, що проходять через середини протилежних ребер, на кут 180◦. Для кожного з таких поворотiв кiлькiсть нерухомих точок кiлькiсть тих розфарбувань куба, якi при цьому поворотi переходять у себе, дорiвнює: a) k6; b) k3; c) k4; d) k2; e) k3. Тому згiдно леми Кошi–Фробенiуса–Берн- сайда кiлькiсть геометрично рiзних розфарбувань дорiвнює

Зауважимо, що звiдси випливає не зовсiм очевидний факт, що для довiльного натурального k число k6 + 3 · k4 + 12 · k3 + 8 · k2 дiлиться на 24.

2. Знайдемо кiлькiсть попарно неiзоморфних 5–вершинних простих графiв (тобто графiв без кратних ребер). Позначимо символом M множину усiх 5–вершинних простих графiв i пiдрахуємо, для початку, потужнiсть цiєї множини. Оскiльки двi вершини графа можуть або з’єднуватися ребром, або нi, то для визначення графа нам потрiбно знати, чи з’єднанi ребром наступнi вершини: перша та друга, перша та третя, перша та четверта, перша та п’ята, друга та третя, друга та четверта, друга та п’ята, третя та четверта, третя та п’ята i четверта та п’ята (10 пар). Тому всього 5–вершинних простих графiв буде 210. На множинi M природним чином дiє симетрична група S5: нехай = (V, E) довiльний 5–вершинний простий граф, де V = {1, 2, 3, 4, 5} множина його вершин, а E множина його ребер, π S5, тодi π = (V, Eπ) M, де вершини π(i) та π(j) з’єднанi ребром, тобто (π(i), π(j)) Eπ, якщо ребром з’єднанi вершини i та j, тобто (i, j) E. Два графи 1 i 2 будуть iзоморфними, якщо знайдеться така пiдстановка π S5, що π1 = 2. Таким чином, кiлькiсть попарно неiзоморфних 5–вершинних простих

87

графiв дорiвнює кiлькостi орбiт групи (S5, M).

Знайдемо тепер кiлькiсть нерухомих точок елементiв iз S5. Порядок групи S5 дорiвнює 5! = 120. Ця група мiстить один елемент циклового типу (a)(b)(c)(d)(f) (це тотожна пiдстановка ε). Кожен граф M при дiї на нього ε залишається на мiсцi, тому χ(ε) = |M| = 210.

Група S5 мiстить 10 елементiв циклового типу (ab). Нехай {a, b, c, d, f}множина вершин графа, який є нерухомою точкою для такого типу пiдстановки. Тодi якщо в такому графi вершини a та i (i одна iз вершин {c, d, f}) з’єднанi ребром, то ребром з’єднанi i вершини b та i. А тому для визначення цього графа нам потрiбно знати з’єднанi ребром, чи нi тiльки наступнi вершини: a та b, a та c, a та d, a та f, c та d, c та f, d та f. Отже, χ((ab)) = 27.

Аналогiчно, група S5 мiстить 15 елементiв циклового типу (ab)(cd). I для визначення графа, який є нерухомою точкою для такого типу пiдстановки, нам потрiбно знати з’єднанi ребром, чи нi тiльки наступнi вершини: a та b, a та c, a та d, a та f, c та d, c та f. Отже, χ((ab)(cd)) = 26.

Група S5 мiстить 20 елементiв циклового типу (abc). Для визначення нерухомої точки для такого типу пiдстановки, нам потрiбно знати з’єднанi ребром, чи нi тiльки вершини: a та b, a та c, a та d, a та f. Отже, χ((ab)(cd)) = 24.

Стiльки ж, а саме 20, мiстить S5 елементiв циклового типу (abc)(df). Для визначення графа, який є нерухомої точкою у цьому випадку, нам потрiбно знати з’єднанi ребром, чи нi тiльки вершини: a та b, a та c, a та d. Отже, χ((abc)(df)) = 23.

I, нарештi, S5 мiстить 24 елементи циклового типу (abcdf). Для визначення нерухомої точки нам досить знати з’єднанi ребром, чи нi вершини: a та b (тобто в такому графi або одночасно всi вершини попарно з’єднанi ребрами, або ж жоднi двi вершини не з’єднанi ребром). Тому,

χ((abcdf)) = 22.

I згiдно леми Кошi–Фробенiуса–Бернсайда кiлькiсть попарно неiзоморфних 5–вершинних простих графiв дорiвнює

210 + 10 · 27 + 15 · 26 + 20 · 24 + 20 · 23 + 30 · 23 + 24 · 22 = 34 . 120

Прикладом ще однiєї дiї є дiя симетричної групи Sn на множинi P [x1, . . . , xn] многочленiв вiд змiнних x1, . . . , xn з коефiцiєнтами з поля

P .

88

Нехай

...,i

деякий многочлен вiд змiнних x1, . . . , xn.

Степенем одночлена ai1,...,in xi11 . . . xinn називається число i1 +· · ·+in.

Найбiльший iз степенiв одночленiв ai1,...,in xi11 . . . xinn у зображеннi (11) називається степенем многочлена f.

Вправа 18.3. Покажiть, що кiлькiсть рiзних одночленiв n змiнних

степеня m дорiвнює m+n−1 .

m

Для однозначного впорядкування членiв многочлена багатьох змiнних використовується так званий лексикографiчний порядок (аналогiчний впорядкуванню слiв у словнику): спочатку порiвнюють показники при x1, якщо вони рiвнi, то при x2 i т.д. Наприклад, у многочленi f його члени розмiщеннi у лексикографiчному порядку вiд вищого до нижчого: f(x1, x2, x3) = x51x3 + 2x41x23 + x52.

Старшим членом многочлена називатимемо найвищий член у лексикографiчному порядку.

Розглянемо дiю симетричної групи Sn на P [x1, . . . , xn]: елемент π симетричної групи Sn дiє на многочлен f(x1, . . . , xn) за правилом:

fπ(x1, . . . , xn) = f(xπ(1), . . . , xπ(n)).

Така дiя є точною. Якщо орбiта многочлена f при такiй дiї одноелементна, то кажуть, що f є симетричним многочленом. Iншими словами

Означення 18.2. Многочлен f P [x1, . . . , xn] називається симетричним,

якщо fπ(x1, . . . , xn) = f(x1, . . . , xn) для всiх π Sn.

Позначимо символом SP [x1, . . . , xn] множину симетричних многочленiв.

Вправа 18.4. Доведiть, що множина всiх симетричних многочленiв SP [x1, . . . , xn] утворює кiльце, яке є пiдкiльцем кiльця P [x1, . . . , xn].

Вказiвка. Скористайтеся тим, що вiдображення ϕπ : f 7→fπ є автоморфiзмом кiльця P [x1, . . . , xn].

89

Прикладом симетричних многочленiв є, так званi, елементарнi симетричнi многочлени σk :

σ1(x1, . . . , xn) = x1 + . . . + xn, . . . ,

Елементи кiльця SP [x1, . . . , xn] симетричних многочленiв влаштованi досить прозоро, про що говорить наступна

Теорема 18.2 (основна теорема про симетричнi многочлени).

Для кожного симетричного многочлена f SP [x1, . . . , xn] змiнних x1,

. . . , xn над полем P iснує, причому тiльки один, такий многочлен F P [x1, . . . , xn], що

Для доведення основної теореми про симетричнi многочлени нам знадобляться наступнi двi леми.

Лема 18.2. Нехай u = axk11 . . . xknn старший член симетричного многочлена f(x1, . . . , xn). Тодi k1 ≥ . . . ≥ kn.

Доведення. Припустимо, вiд супротивного, що ki < ki+1. Тодi f крiм члена u має мiстити також u,ˇ який одержаний iз u перестановкою змiнних xi та xi+1. А, отже, u не є старшим членом. Одержали протирiччя.

Лема 18.3. Для довiльного одночлена u = axk11 . . . xknn такого, що k1 ≥

. . . ≥ kn, iснують єдиним чином визначенi невiд’ємнi цiлi числа l1, . . . , ln, такi що старший член могочлена σ1l1 . . . σnln збiгається з u.

Доведення. Старший член многочлена σk дорiвнює x1 . . . xk. Тодi старшим членом многочлена σ1l1 . . . σnln буде

xl11 (x1x2)l2 . . . (x1 . . . xn)ln = xl11+...+ln xl22+...+ln . . . xlnn .

Порiвнюючи цей старший член iз одночленом u одержимо систему

l1 + . . . + ln = k1 ,

l2 + . . . + ln = k2 ,

. . . ,

ln = kn ,

90