У. Питерсон - Коды, исправляющие ошибки (1267328), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

д. Число элементов группы называется порядком группы. ь)исло различных смежных классов в разложении группы 6 по подгруппе Н называется индексом Н в 6. Очевидно, что (порядок Н) (индекс Н в 6)= порядок 6. Подгруппа Н группы 6 называется нормальной' ), если для любого элемента Ь из Н и любого элемента д из 6 произведение аг-1Ьп принадлежит Н. Вообще говоря, левые смежные классы могут не быть правыми смежными классами, и наоборот.

Однако любой левый смежный класс по нормальной подгруппе является также правым смежным классом, и наоборот. В абелевой группе, очевидно, каждый левый смежный класс является правым смежным классом, так же как всякая подгруппа, очевидно, нормальная. В данной книге используются только нормальные подгруппы, являющиеся абелевыми, поэтому мы не будем доказывать сформулированный выше результат в общем случае. Если подгруппа Н группы 6 нормальная, то можно ввести операцию над смежными классами, так что получится новая группа, элементами которой будут смежные классы. Эта группа называется факторгруппой и обозначается как 6)Н. Смежный класс, содержащий элемент а, обозначим через (д).

Операция умножения смежных классов определяется правилом (п1) (й2) (К!02)' Законность этого определения остается неустановленной до тех пор, пока не будет показано, что независимо от того. какие элементы выбраны в качестве представителей в каждом из перемножаемых смежных классов, результирующий смежный класс получится один и тот же. Другими словами, необходимо показать, что если гг! и гг,' принадлежат одному и тому же смежному классу и а; и да' входят в один и тот же смежный класс, то и произведения I г К!да и ~к!д также принадлежат одному и тому же смежному классу. Предположим, что д! 1дг', = Ьп д-!д' = Ь . Поскольку подгруппа является нормальной, элемент лт-1Ь!д' должен принадлежать подгруппе Н.

Обозначим его через Ь,. Тогда (й д) 'д'й'= ! 2) ! 2 =й; 'к! 'к1д'=д 'Ь!д'=лт 'дтйа=йтЬа, так что это произведение принадлежит подгруппе Н. Таким образом, элементы д!дт и д'й' входят в 1 2 ! 2 дя в один и тот же смежный класс, и определение умножения ') Но мал ') р альпую подгруппу часто иеаывают иормальиым делителем.-!!ром Проверим теперь, что факторгруппа 6/Н действительно является группой. Операция над смежными классами, очевидно, определена для всех пар смежных классов, и поэтому аксиома 6.1 удовлетворяется. Чтобы проверить справедливость ассоциативного закона, заметим, что (йз ) ((Иг) (йз)) = (з1) (йзйз) = (Фаз) = (йЮг) (йз) = ((з1) (М) (йз).

Единичным элементом является сама подгруппа Н = (Ц, поскольку (Ц Ы = (1И) = (ь') и (а) (Ц = (дЦ = (й). Аналогично обратным к смежному классу (й) оказывается смежный класс, содержащий элемент й-', так как (д) (8-з) = (дд — ') = (Ц и (д-') (д)= = (д — 'й) = (Ц. Кроме того, если первоначальная группа абелева, то, как нетрудно проверить, факторгруппа также является абелевой.

Примеры. Предположим, что в качестве группы 6 рассматривается группа нз восьми преобразований квадрата, а подгруппа Н состоит из элементов 1, а, Ь, с. Тогда стандартная таблица левых смежных классов прн условии, что элемент з! выбран образующим, имеет вид 1 а Ь с с! з!а=д с!Ь=) з!с=е Существует только один смежный класс, содержащий все элементы группы 6, не вошедшие в Н, и поэтому он должен быть также правым смежным классом, а подгруппа Н должна быть нормальной.

Если единичный смежный класс обозначить через 1, а второй смежный класс — через О, то таблица умножения имеет вид П = 7, т=(Ц(!) =(!) =В, 'Ш=П, 66=(а)(!)=(Ы) (Ц 7'. Структура этой таблицы умножения, конечно, такая же, как у таблицы умножения для единственной группы из двух элементов. В качестве более важного примера рассмотрим аддитнвную группу 6, состоящую из положительных и отрицательных целых чисел и нуля, и подгруппу Н, состоящую из чисел, кратных целому а. Все числа от нули по а — 1 принадлежат различным смежным классам, потому что для того, чтобы два элемента а и Ь принадлежали одному и тому же смежному классу, необходимо, чтобы элемент ( — а) + Ь принадлежал подгруппе и, таким образом„был кратен п.

Эти числа могут быть выбраны образующими смежных классов, и легко видеть, что смежных классов с другими образующими не существует. Поскольку группа 6 абелева, то может быть определена операция сложения смежных классов, и смежные классы образуют группу. Например, пусть и = 3. Тогда смежные классы оказываются строками таблицы: О, 3, — 3, 6, — 6, 9, — 9, ... 1, 4, — 2, 7, — 5, 1О, — 8, 2, 8, — 1, 8, — 4, τ— 7, Е ли ик обозначить соответственно как (О), (!) и (2), то таблица сложения имеет вид + (о) РЦ (2) (о) (о) (ц (2) (Ц (Ц (2) (0) (з) (2) (о1 (Ц В этой таблице можно узнать таблицу сложения чисел по модулю 3.

2.З. Векторные пространства и линейные алгебры Множество Г называется векторным пространством над полем р, если для него выполняются следующие аксиомы: Аксиома ч'. 1. Множество Р является абелевой аддитивной группой. Аксиома 7.2. Для любого вектора ч и любого элемента поля с определено произведение сч, являющееся вектором (элементы поля называются скалярами, а элементы ч' — векторами), Аксиома Ч.З (дистрибутивный закон). Если и и ч — векторы из множества Г, а с — скаляр, то с(и+ ч) = си+ сч, Аксиома (Г.4 (дистрибутивный закон). Если ч — вектор, а с и й — скаляры, то (с+ й)ч = сч+йч. Аксиома ч'.5.

(ассоциативный закон), Если ч-вектор, а с и г(— скаляры, то (сй)ч = с(дч) и 1ч = ч. Множество А называется линейной ассоциативной алгеброй над полем Р, если выполняются следующие аксиомы: Аксиома А.1. Множество А является векторным пространством над г. Аксиома А.2. Для любых двух элементов и и ч из А суицествует произведение ич, определяемое как некоторый( элемент из А.

Аксиома А.З (ассоциативный закон). Для любых трех элементов и, ч и тч из А справедливо равенство (ич)тч = и(чэг). Аксиома А.4 (билинейный закон). Если с и й — скаляры из г, и, ч и тч — векторы из А, то ~(сч+йтч)= сцч+йив и (сч+ йтч)и = счи+ бтгц. Набором длины и элементов поля называется упорядоченное множество из п элементов поля, обозначаемое как (аь ам ам а,), где каждый из а; является элементом поля.

Сложение наборов длины и определяется следующим образом: аъ, а„)-)-(Ьо Ь,..., Ь„)=(а, + Ьь а,+Ь„..., а„+ Ь„). умножение наборов длины и на элемент поля определяется правилом с(а„а„..., о„) =(сп„саг, ..., са„). Если определены эти две операции, то, как легко проверить, совокупность всех наборов длины и над полем образует векторное пространство. Такие векторные пространства занимают центральное место в теории кодирования.

Онн и являются основным предметом изучения остальной части данной главы. Умножение наборов длины п может быть определено следующим образом: (а,, ам ..., а„)(Ь,, Ьм ..., Ь„)=(а,Ьн агЬм ..., а„Ь„). Введение этой операции превращает совокупность наборов в линейную алгебру. Определенная таким образом операция умножения нспользуется довольно редко. Другой способ умножения наборов, приводящий к линейной алгебре, описывается в гл. 6.

Он играет более важную роль в теории кодирования. Единичный элемент векторного пространства будет обозначаться символом О. Таким образом, 0=(0,..., 0). Для совокупности наборов очевидно, а в случае произвольного векторного пространства легко проверить, что для любого вектора ч произведение Оч = 0 н для любого скаляра с произведение сО =- О.

Кроме того, ( — ч)=( — 1)ч, так как ч+( — 1)ч=1ч+( — 1)ч (1+ ( — 1))ч — Оч = 0 Подмножество векторного пространства называется подпространством, если оно удовлетворяет аксиомам векторного пространства. Для того чтобы проверить, является ли некоторое подмножество векторного пространства подпространством, необходимо проверить только замкнутость этого подмножества относительно операций сложения и умножения на скаляр. Заметим, что так как — ч = ( — !)ч, то замкнутость относительно умножения на скаляр показывает, в частности, что элемент, обратный каждому из элементов подмножества, принадлежит подмножеству.

Поэтому замкнутости подмножества относительно операции сложения достаточно для того, чтобы подмножество было подгруппой; ассоциативный и дистрибутивный законы должны быть справедливы в подпространстве, если они справедливы в исходном векторном пространстве. Линейной комбинацией й векторов чь чь ..., чь называется сумма вида ц=а,ч, +агу,+ ...

+аьчм Здесь а; — скаляры, т. е. элементы поля. Теорема 2.5. Совокупность всех линейных комбинаций некоторого набора векторов чь ..., чь из векторного пространства У является подпространством пространства У. доказательство. Очевидно, что любая линейная комбинация кторов из г' является вектором иэ Р. Если совокупность всех линейных комбинаций векторов т), ..., т)ь обозначить через 5, а щ — Ь,ч)+ ...

+ЬИЪ и и = с)т)+ ... + сьчь — любые два элемента из 5, то элемент тг+ и также принадлежит 5, поскольку „, +ц =(Ь, +с))т)+ ... +(Ьь+сд)т)ь Кроме того, любое прои)- ведение я) на скаляр, ая) = аЬ)т)) + ... + абьт)ь принадлежит 5. Поскольку множество 5 замкнуто относительно операций сложения и умножения на скаляр, то оно является подпространством векторного пространства К Ч. т. д. Совокупность векторов т„ть ..., ть называется линейно зависимой тогда и только тогда, когда существуют скаляры сь сь ... ..., см не все равные нулю, такие, что с)ч) + с1т)2 + ° ° + сьуь = О. Совокупность векторов называется линейно независимой, если она не является линейно зависимой.

Говорят, что некоторая совокупность порождает векторное пространство, если каждый вектор векторного пространства может быть представлен в виде линейной комбинации векторов этой совокупности. Теорема 2.6. Если совокупность А векгороа т), ..., ть порождает векторное пространство, которое содержит некоторую совокупность из т линейно независимых векторов ць ..., и , то й= и). Доказательство. Поскольку векторы ть ..., кь порождают пространство, вектор и, может быть представлен как линейная комбинация векторов ть Такое соотношение можно разрешить относительно какого-нибудь одного нз ))), скажем ть выразив его через и) и остальные ть Если для исключения т)) использовать его выражение через и, и другие мь то любая линейная комбинация элементов т, будет представлена как линейная комбинация и, н всех векторов т), кроме ть и, следовательно, совокупность, содержащая ц) и все векторы ть кроме ть порождает векторное пространство.

Поэтому пз можно представить как линейную комбинацию ц, и всех т)), за исключением ть Так как векторы линейно независимы, то по крайней мере один из векторов т) должен войти в линейную комбинацию с нулевым коэффициентом, и поэтому этот элемент может быть представлен как линейная комбинация пь из и оставшихся й — 2 векторов мь Следовательно, эти й векторов порождают пространство.

Этот процесс может быть продолжен до тех пор, пока не будут использованы все т векторов иь и так как на каждом шагу замещается один из векторов ть то число векторов т) должно быть по крайней мере не меньше числа векторов и). '). т, д. Теорема 2.7. Если два множества линейно независимгях векторов порождают одно и то же пространство, то в каждом из множеств содержится одно и то же число векторов. Доказательство. Если в одном множестве и векторов, а в другом А векторов, то по теореме 2.6 и ) А и А ~ и', так что т = й. Ч. т.

Характеристики

Список файлов книги