Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 77
Текст из файла (страница 77)
п 7(1) 7'(2) ... 7'(и) Рассмотрим следуюшую подгруппу симметрической группы Яг, основанную на квадрате, изображенном на рис. 9.12. 4 3 Рис. 9,12 Перестановка 3 2 1 4 аЬН = а(ЬН) = = а(Ь(НН) = = а(ЬН)Н = = а(НЬ)Н = = (аН)(ЬН). по теореме 9.75 по теореме 9.80 по теореме 9.75 по теореме 9.79 по теореме 9.75 РЯЗдЕЛ 9.5.
Группы и аомоморфизмы 419 меняет местами 1 и 3. Геометрически — это отражение квадрата относительно диагонали между вершинами 2 и 4. Аналогично, перестановка бг= 1 4 3 меняет местами 2 и 4. Геометрически — это отражение квадрата относительно диагонали между вершинами 1 и 3. Перестановка 4 3 2 1 геометрически отражает квадрат относительно горизонтальной оси, проходящей через центр квадрата. Перестановка 2 1 4 3 геометрически отражает квадрат относительно вертикальной оси, проходящей чеРез центР квадРата. ПУсть Ры Рг, и Рз — вРащениЯ квадРата по часовой стРел- /1 2 3 41 ке на 90', 180' и 270' соответственно. Следовательно, рг = ~ 2 3 4 /1 2 3 41 /1 2 3 41 Рг1 3 4 1 2)ирз1 4 2 3(Пусть 1 тождественная пере [ 4 1 2 3(' становка. Все результаты умножения этих элементов содержит приведенная ниже таблица.
о 1 Рг Рг Рз б~ бг фг фг Эта группа называется октической группой, или группой симметрий квадрата. Множество Н = 11, рг,рг,рз) — подгруппа октической группы. Поскольку Н содержит четыре элемента, и число элементов в смежном классе должно делить порядок группы, то существует только один смежный левый класс, аН для любого а ф Н. Этот класс состоит из всех элементов октической группы, которые не попали в Н. Но он должен совпадать с На для любого а гр Н, поскольку существует только один другой правый смежный класс.
Следовательно, Н вЂ” нормальная подгруппа октической группы. Читателю остается показать, что 11,рг) — нормальная подгруппа октической группы. ьг 1 Рг Рг Рз бг бг Фг Фг 1 Рг Рг Рг Рг Рз Рг Рз Рз 1 Рг бг фг бг бг Фг ф~ бг фг фг бг ф~ Рз б, 1 фг рг бг Рг Фг фг 1 Фг бг Рг бг Рз б. Ф~ Фг Фг бг бг Фг Фг фг бг бг Рг Рз Рг 1 Рг Рз Рз 1 Рг Рг Рг 420 ГЛЯВА 9. Алгебраические структуры Пусть А — конечное множество из и элементов и пусть ߄— группа перестановок на А. Поскольку имеется и! перестановок элементов множества А, то Я„содержит пй элементов. Пусть, для удобства, 1, 2, ..., и — элементы из А. Для фиксированной перестановки о определим отношение В на А таким образом; аВЬ, если Ь = о" (а) для некоторого неотрицательного целого числа к.
ТЕОРЕМА 9.87. Отношение В есть отношение эквивалентности на А. ДОКАЗАТЕЛЬСТВО. Поскольку группа Я„конечна, то о = 1, единице группы Я„для некоторого неотрицательного целого числа га. Следовательно, о™(а) = а и аВа. Пусть аВЬ, тогда Ь = аь(а) для некоторого неотрицательного целого числа к. Поскольку о"о ~ = о = 1, то о " — обратный элемент для о", так что о ь(Ь) = а и ЬВа. Следовательно, В симметрично. Пусть аВЬ и ЬВс. Тогда Ь = об(а) для некоторого неотрицательного целого числа 1 и с = оь(Ь) для некоторого неотрицательного целого числа Ь.
Следовательно, с = об+"(а), и В транзитивно. Поэтому  — отношение эквивалентности. Поскольку В является отношением эквивалентности, оно делит множество (1,2,3,...,п) на классы эквивалентности. Например, пусть А=(1,2,3,...,8) и г'1 2 3 4 5 6 7 81 \ 4 3 2 7 8 6 1 5)' Легко видеть, что множество классов эквивалентности имеет вид Ц1,4,7), (2,3), (5,8),(6Ц. Множество классов эквивалентности, созданное таким образом, называется орбитой перестановки о.
Теперь определим специальный вид перестановки, называемый циклом. Если обозначить ос = (ам аз, аз,...,аь) как цикл, тогда о,(а,) = а,ьг для 4 ( к, и ос(аь) = аы Например, если о, = (1,3,5,7) — цикл в Яа, то /1 2 3 4 5 6 7 81 (,3 2 5 4 7 6 1 8)' Данную перестановку о. можно записать как произведение циклов, которые не имеют общих элементов. Для этого сначала необходимо разделить множество А на классы эквивалентности. Выбираем элемент а и образуем цикл (а,о(а),оз(а), оз(а),...,о" (а)), где о"+г(а) = а. Эти циклы не содержат общих компонент, поскольку классы эквивалентности не пересекаются. Назовем эти циклы непересекающимися. Например, в перестановке г'1 2 3 4 5 6 7 8~ 4 3 2 7 8 6 1 5) с множеством классов эквивалентности ((1,4,7),(2,31,(5,8),(6Ц циклами являются (1,4,7), (2,3), (5,8) и (6). Поскольку каждый цикл двигает только числа из цикла, а циклы непересекающиеся, то о = (1,4,7)(2,3)(5,8)(6).
Поскольку циклы не пересекаются, то порядок циклов не меняет перестановку. По желанию, одноэлементные циклы можно опускать, поскольку они реально ничего не меняют. Поэтому можно записать а = (1,4,7)(2,3)(5,8). Если использовать одноэлементные циклы, то тождественную перестановку в Яа можно записать как (1)(2)(3)(4)(5)(6)(7)(8). рлзделд.д Группы и гомоморфогмы 421 ° УПРАЖНЕНИЯ 1. Докажите теорему 9.70. Пусть 7': С вЂ” Н вЂ” гомоморфизм из группы С в группу Н и 1 — единица группы С. Тогда 7'(1) — единица группы Н. 2.
Докажите теорему 9.71. Пусть 7: С вЂ” Н вЂ” гомоморфизм из группы С в группу Н и д' — элемент, обратный элементу д из С. Тогда 7"(д') есть элемент, обратный элементу 7'(д) из Н. 3. Следуя доказательству теоремы 9.64, пусть а о Н вЂ” левый смежный класс подгруппы Н группы С. Определим 7: Н вЂ” аоН соотношением г(п) = аой. Покажите, что функция 7" — биекция. 4. Докажите теорему 9.78. Ядро гомоморфизма 7": С вЂ” Н есть нормальная подгруппа группы С.
5. Пусть гз~ = ([Ц, [2], [3], [4]) — множество элементов Ез без элемента [О]. Эти элементы соответствуют целым числам, которые дают при делении на 5, соответственно, остатки 1, 2, 34. Вместе с операцией умножения,, введенной для Ез, получаем группу (Яз~,.). Покажите, что (Яз~, ) изоморфна (о4,+), непосредственно указав изоморфизм 7: Ез~ — 24. 6. Покажите, что (1, рз) — нормальная подгруппа октической группы. 7. Найдите двухэлементную подгруппу октической группы, которая не является нормальной подгруппой. 8. Докажите теорему 9.72. Если 7": С вЂ” Н вЂ” гомоморфизм из группы С в группу Н и К вЂ” подгруппа группы Н, то 7' '(К) — подгруппа группы С. 9.
Докажите теорему 9.73. Если 7": С вЂ” Н вЂ” гомоморфизм из группы С в группу Н и К вЂ” подгруппа С, то 7'(К) — подгруппа группы Н. 1О. Запишите приведенные ниже перестановки как произведение непересекаюшихся циклов: ( 1 2 3 4 5 6 7 8 9 3 9 4 7 8 6 1 5 2у'' 71 2 3 4 5 6 7 8 91 )[,2 4 7 8 3 6 9 1 5)' 7 1 2 3 4 5 6 7 1 2 4 1 7 3 6 5!' 3 4 5 6 1 2 1!.
Найдите а от, где а) а = (1, 3, 4)(2, 5) и т = (1, 2)(3, 4)(5); 6) а = (1, 2)(3, 4)(5, 6) и т = (1, 2)(3, 4)(5, 6); в) а = (1, 2, 3)(4, 5, 6) и т = (1, 2)(3, 4)(5, 6); г) а = (1, 2, 3, 8)(4, 5, 6)(7) и т = (1, 2)(3, 8)(4, 5)(6, 7). 12.
Докажите теорему 9.75. Если Н, д и К вЂ” подмножества группы (С, о), то (Н о 7) о К = (Н о (7 о К) 13. Докажите теорему, обратную теореме 9.79. Если для заданной подгруппы Н группы (С,о) имеет место дН = Нд для всех д 6 С, то Н вЂ” нормальная подгруппа. РАЗДЕЛ 10.1. Целочисленные решения линейных уравнений 423 Иной способ построения решения состоит в непосредственном использовании уравнения аи+ Ьо = НОД(а,6). Поскольку аи + Ьо = НОД(а, 6) или а (1)+Ь ( — 2) =17, то, умножая на 3, получаем а (3) +Ь ( — 6) = 51. Замечая, что при х = 5 и у = -11 85 5+ 34 ( — 11) = 425+ ( — 374) = 51, приходим к выводу, что может существовать более одного решения.
С) ПРИМЕР 10.3. Решить уравнение 252х+ 580у = 20.В примере 7.6 показано, что НОД(252,580) = 4 и (252)( — 23) + (580)(10) =. 4. Умножая каждое слагаемое на 5, получаем (252)( — 115) + (580)(50) = 20. Следовательно, х = — 115 и у = 50 являются решением. П Теперь у нас есть возможность определять, существует ли решение, и находить частное решение для уравнения ах+ Ьу = с, если решение существует. Теорема, приведенная ниже, дает возможность находить все решения уравнения. ТЕОРЕМА 10.4.
Если а и 6 — ненулевые целые числа и (хо,уо) — решение уравнения ах+ Ьу = с, тогда любое другое решение (х,у) имеет вид Ь х=хо+-„с; а У = Уо — — г, где г — произвольное целое число, а а' = НОД(а, 6). ДОКАЗАТЕЛЬСТВО. Если (х, у) и (хо,уо) являются решениями уравнения ах+ Ьу = с, то ах + Ьу = ахо+ Ьуо. Поэтому ах — ахо = Ьуо — Ьу и а(х — хо) = Ь(уо — у). Разделив обе части соотношения на а = НОД(а,Ь), имеем Цх — хо) = 3(уо — У). Поскольку по теореме 7.8 НОД (д, ь) = 1, получаем, что а(уо — у) и 3(х — хо), скажем, х — хо = и Я) и (уо — у) = и (-„'). Тогда (-') и Д) = (3а) и (-„'), и отсюда после сокрашения и = и.
Положив а = и = и, получаем х = хо + Д) т и у = Уо — (а) Г. Необходимо еще показать, что паРа (хо+ (ь) ~, Уо — (а) с) ЯвлЯетсЯ решением уравнения ах + Ьу = с. Но = ахо + Ьуо = 424 ГЛАВА 10. Некоторые специальные вопросы теории чисел Возвращаясь к примеру )0.2, мы видим, что общее решение уравнения 85х+ 34у = 51 имеет вид х = 3 + 2г и у = -6 — 5Ь. В примере 10.3 общим решением уравнения 252х + 580у = 20 является х = — 115+ 1451 и у = 50 — бзт. ° УПРАЖНЕНИЯ !. Найдите решение каждого из приведенных ниже уравнений: а) 24х + 81у = 6; б) 803х + 154у = 33; в) 73х + 151у = 3; г) 165х + 418у = 121; д) 27х + 78у = 12.
2. Найдите общее решение каждого из уравнений упражнения 1. 3. Найдите (если оно существует) решение каждого из приведенных ниже уравнений: а) 23х + 18у = 4; б) 299х + 533у = 52; в) 39х + 299у = 27; г) 272х + 102у = 68; д) 27х + 180у = 33. 4. Найдите общее решение каждого из уравнений упражнения 3, если оно существует. 5. Напишите в псевдокодах процедуру для нахождения целочисленных решений линейных уравнений. 10.2. РЕШЕНИЯ СРАВНЕНИЙ [а) О [Ь] [О! [1! [2! [3! [4] [0] [1! [2] [з! [4] [О! [О! [О! [О! [О! [0] [1] [2] [3] [4! [О] [2) [4! [1] [3] [о] [з] [1! [4) [г] [о] [4! [з! [2! [1! можно найти решение сравнения Зх = 1 (щи 5), рассматривая (по модулю 5) [3] О [х) = [1]. В предыдущем разделе рассматривались уравнения вида ах+ Ьу = с, имеющие в качестве решений целые числа х и у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
