Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 7
Текст из файла (страница 7)
Например, 7, х 7, задается миожесгвач 2 х 2«.— - КО, 0), (О, !), (О. 2), (1, 0), (1, !), П, 2)). Типнчнмм элеиеитаи таблицы сложений в 2, х 3, является (1, 2) 4. (О, 2) = (1, 1). Отметим, что группа 7, х 2, сама является цинлической с об. разующим элементом (1, 1). Следователь«га, 7, х 7, нзаморфнв группе 2,. Причина этого роется етом, чта числа 2 и 3 не имеют общих целочисленных делителей. Пусть 6 группа и Н вЂ” подмножество в 6 Тогда Н называется подгруппой группы С, если Н само является группой относительна ограничения групповой операции на Н В качестве примера, выножеств целык чисел (ооложнтельиых, отрицательных и нуля) с операцией сложения множество четных чисел, так же как и множество чисел, кратных 3, образует подгруппу.
Один нз способов построения подгруппы Н конечной группы 6 состоит в том, чтобы, выбрав некоторый элемент й из 6, форми. ровать злементы множества Н в ваде последовательимх степеней й, = 1 й, й „ й, й, й, . й, " й, й. й, « Л, = йз й Ь, " й« « ° «й„ й„л„ называется «ид«рам свеж называется леням смежным й.«й, =й„й„й, Первый элемент в каждой строке ного класса. Каждаа строка таблицы зюга элемента; й, й', й', й', Тан как группа 6 конечна, то элемент последовательности обязателдио начнет павторятьс».
Пе вым должен повториться сзм элемент й, а непосредственно ервым до предшествующий ему элемент является единичны и алене«ыом гру уппы, так нак рассматриваема» конструкция дает цвнличесную г пп Множества Н назыьается цикаичасгшй ладгрр апай, порожденной элементом й Число д элементов д ру в по г ппе Н удовлетворяет равенс у ет авенству й« = 1 и называется порядкам злеиента й Множества элементов й, АА й',, й« == 1 называетси цик.юм в группе 6. Н явДля Д того чтобы показать, что непустое подмножество группой в С, достаточно толька пронерить, что змее те ляется поагру ит элемент с злеиентами а и Ь из Н множеству Н принадлежит а Ь, и что обратный к произвольноиу злементу а из П также принадлежит Й.
Осталыгые требуемые групповые свойства наследуютсв иэ группы 6 Если группа конечна, то, как мы увндим паза«е при рассмотрении циклических подгрупп, д аже свойство обратимости выполняется автоматически. Дли заданных конечной труним С и одгруппы Н и ее с ' важная конструкция, иллюстрирующая определенную взаимосвязь между С и Н н известная под названием разложении группы С ла смежяьм классы по подгруппе Н. Обозначим через йо йа й, элементы аз Н, причем через й, обозначим ециничный зле. мент.
ос р Пост оим следующую таблицу: первая строка состоит из элементов подгруппы Н, причем цервыи слева выписан д злемент и каждый элемент нз Н выписан в строке один и только один раз. Выберем произвольный элемент группы 6, не содержащийся в первой строке. Назовем его й, и используем в начестве первогозлемеита второй строки Остальныезлементы второй строки теперь получаются умножением слева злементов подгруппы на згог первый элемент. Аналогична, строя стретью, четвертую и пнт ю строки, каждый раз выбираем не использованный иа препнтую р аз душих шагах элемент группы 6 в качестве элемент , р ме«тов пе ного столбца Конел наступает, нагда после некоторого шага ока ыз что все элементы группы записаны в некотара» месте вается, что с 6.
Таблица таблицы. Процесс оканчиваетси в силу конечности 6. и аеет следующий вид Эв Г». 2. В в *г в* т тю гг аэу 22 К т В классом, а в случае абелевой группы просто смежным кгтьпг, .т л, слн прн построении разложен«я группм на смежные «лаосы использовать вместо лесото правое умножение на элементы группы Н, , то строка называются ирагыми смежными классами. В силу указанных правнл построения разложенне группы на смежные классы всегда является прямоугольной таблицей. все строки которой поляостью заполнены.
Докажем теперь, что в этой таблнце наждый элемент группы встречаетса точно аЛин раз Теорема 2.1.3. В разгожгнгги руопа ни сметные класси каж. дый элемент групои т пргчагтся один и только один раз. Докиэитглзспмо. Каждый элемент появится по крайней мере один раз, так как в противном случае пропесс не остановится. Покажем теперь, что каждый элемент не может ноявнться дважды в одной и той же строке, а затем докажем, что одпн н тот же элемент не может появиться в двух разаых строках таблицы. Прелноложнм, что два элемента в одной н тай же строке, снажем д,*й, н д<чй„ равны Тогда умножение') «аждого нз них на дд дает равенства и! =- д, это противоречат таму, что каждый элемент подгруппы выписан в первой строке ~олька одни рав.
Предположим. чта два элемента иа раздячных строк, скажем Ьг и дгчйк равны, я что Ь < г Умножение справа на Ь ' 1 Ь. приводит к равенству д, = дагйг Ьг' Тогда д порождает .й смежный класс, так как элемент 2~ ей,' принадлежит подгруппе. Это протнворечнт выбранному выше правилу выбор» лидеров смежных классов Слсдствме 2.1.4. Если Н вЂ” лодгруяла гропли П, то чист элемгнтт з Н дглтгт число гггмгнтт г П Таким образом, (Порядок Н) (Чис. о смежны* кгт ог 6 по Н) — (Порядок 6).
Доказатггьснмо. Следует непосредственно нз прямоугольностн таблнпы рззложевня на смежные классы О Теорема 2.1.3. Порядок гонечнод группы дггится ио лорлдок любого из ге эхе чентоа Гикам обр зом, сг = 1 дгя любого элемента а группы П с д элементами Докаитгльстао. Группа содержит циклическую подгруппу, порожденную любым из ее элементов, н, тким образом, доказательство теоремы вытекает нз следствия 2.1 4.О 2.2. Кольца Следующей необходяной нам алгебраической структурой является кольца.
Кольцо представляет собой абстрактное множество, которос является абелевой группой н «аделено дополнительной онерацией. ')Слт.— Пр . р Определенме 2,2.1, Калы(ом П называется множество с двумя опр еделеннымн на нем операциями: первая называется сложением (обозначается плюсом); воюрая называется умножением (обозна- чается запнсью сомножителей ридом), причем вываляв«пся сле- дьющие аксиомы 1.
Относнтсльво сложения (-1-) П является абелевой группой. 2 (Зимкнуттть.) Г!ронзведенне аЬ принадлежит П длн любых а и Ь нз Я. 3. (Закон тсониатигности ) а (Ь ) = (аь) с, 4. (Зтлн днгтрибутигн сти ) а (Ь -1- с) = аЬ 1- щ, (Ь 4. с) а =. Ьа -!-са. Сложение в «ольие всегда коммутативно, з умножение не обязательно должно быть комнутатввным. Коммутатозиое кель- нов — что кольцо с коммутатнвным умножением: аб = Ьа для всех а и Ь нз д Дистрибутивный закан в опрехеленни к тина сья ы- вает опсрацвн сложения и умножения Важней~пима примерзни колец являются кольцо 2 целых чисел н кольна дд(д) целых чисел по молулю д Мы уже видели, что о ан являются группами по сложению. Так как аа этих множест- вах амеется также умножение с необходнммчи свойствамн, т , то онн являются кольнами Несколько хороша известных чвтателю по знакомым «ельцам свойств могут быть выведены из аксиом следующим образом Теорема 2.2.2. Длл ироиыогьнмх элементов а и Ь из кожно П змиогняютсв раггист а (!) иб — Оа —.
О. (П) и ( — Ь) = ( — а) Ь вЂ” — аЬ. Доказатг п,стао. П) аб — а (О -1- О) = аб 4- аб Прнбавлпя к обеим частям равенссва — иб, получим О = аб. Аналогично доказывается вто. рая отлов«на п (!). (21) О = об = а (Ь вЂ” Ь) — аЬ 1 а( — Ь).
Следовательно, а ( — Ь) = — (аЬ) Аналогично доказывается вторая яоловинз п. (и). (3 Относительно операцнн сложения кольна содержат единицу, называемую «нулем Относительно опера«ни умноження кольцо не обязательно имеет единицу, но если еднняца есть, то она елин. огненна Колыю, обладающее еднняцей относительно умножения, называется кольцо но едииичгй. эта еднница называетсв геднннцей» 4! га Г«.2. В з *з эг р У эюЕРУ Х2 Клэ и обозначается символам 1. Тогда для всех а нз Р нмеет мес(о 1а = а! = а. Относительно операвнн сложения каждый элемент кольца имеет обратный. Относительно операинн умножения обратные н данному элементу не обязательно существуют, на в кольце с едн.
навей обратные могут существовать. Это означает, что для за. даннога элемента а может существовать элемент Ь, такой что об = 1. Если эта так, то Ь наэываетсн лраеым обратлым к а Аналогично, еслн существует элемент с, такой, что са = 1, то с назынается пегим обрат«ым н о. Теорема 2.2.3. В кольце с едииицеб: (1) Един цо еди«стев«па (В) Если элемент о имеет и легай обрат«ыл Ь, и лр еий обрат«ий с, то Ь = с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
