ЗАКЛЮЧЕНИЕ

Наши рассказы о кодировании подошли к концу. Мы познакомились, конечно, далеко не со всеми задачами этой теории, но в той или иной мере затронули три ее основных направления — кодирование с целью засекречивания сообщений, кодирование с целью сжатия информации, наконец, кодирование с целью исправления и обнаружения ошибок. Нам хотелось дать представление читателю, сколь широки и многообразны связи этой тео­рии с разными разделами математики, и как порой самые абстрактные математические теории могут с успехом при­меняться для решения практических задач.

Дальнейшее проникновение в проблематику теории ко­дирования (подробное изучение циклических кодов и их обобщении, знакомство с кодами, исправляющими пакеты ошибок, и специфическими алгоритмами их декодирования и т. д.) требует уже значительно более серьезной математи­ческой подготовки. Впрочем, интересующийся читатель мо­жет при желании обратиться к литературе, список которой приводится в конце книги.ПРИЛОЖЕНИЕ

В школьной математике рассматриваются различнее операции над числами. Простейшие из них — сложение и обратная к нему операция вычитания, и умножение, для которого обратной опера­цией является деление. Подобные действия приходится производить не только над числами, но и над другими, более сложными объектами. Это можно обнаружить уже и в школьном курсе: на уроках геометрии и физики учат складывать и вычитать векторы, а на уроках алгебры рассматривают операции сложения и умножении многочленов. Однако список таких объектов гораздо обширнее. Мы познакомимся с неко­торыми из них, наиболее важными для наших целей.

1. Сравнения и классы вычетов

Исходным материалом для нас остаются пока все же числа. Два целых числа а и Ь называют сравнимыми по модулю п (п — натуральное), еелн их разность а — Ь делится на п без остатка >„ Это выражают следующей записью:

 

 

Число п называют модулем сравнения (1). Например, 35=2 (тос! II), так как разность 35—2=33 делится на II; аналогично, 25 ——11 (гпо.1 9), так как 25— {—11)=36 делится на 9.

Запись о=О (той п) означает тогда, что само число а делится на га, т. е. а=к-п.

Если зафиксировать некоторый модуль сравнения п, то всякое натуральное число с можно единственным образом представить в виде

 

 

где к — частное от деления на п, а г — остаток, совпадающий с одним

 

 

Остаток г называют также вычетом числа с по модулю п. Заметим, ч то запись вида (2), где 0</<п—1, допускают не только натуральные, нон любые целые числа. Очевидно, из равенства (2) следует, что с= === /-(той п), т. е. всякое число сравнимо со своим остатком (вычетом) по модулю п. Пусть теперь а и Ь — два произвольных числа, записанные в виде (2):

 

 

 

 

Каждый из остатков т1 и г2 — это одно чз чисел (3), поэтому их разность может делиться на п лишь в одном случае, когда тх—гг. Но тогда и разность а — Ь= (к± — к^)п-\-г1—г2 может делитьси нл п тогда и только тогда, когда г,=л2. Отсюда следует, что (той п) тогда и только тогда, когда числа а и Ь имеют одинаковые остатки при делении на п.

В теории чисел (см., например, [5]) доказывается ряд свойств сравнений, во многом аналогичных свойствам обычных равенств. По­добно тому, как мы это делаем с равенствами, сравнения по одинако­вому модулю можно складывать, перемножать и т. д. (так, перемножив сравнения 17=5 (той 4) и 7=3 (той 4), получим, как нетрудно убедить­ся, верное сравнение 119=15 (той 4). Вообще, если   а2^Ь2, то

Значение этих свойств заключается в том, что при рассмотрении вопросов делимости чисел и различных числовых арифметических выражений мы можем входящие в эти выражения числа заменять на другие, сравнимые с ними по данному модулю п; в частности, каждое число может быть заменено своим вычетом. Проиллюстрируем сказан­ное следующей задачей.

из ч исел

Доказать, что число (1981)А+ (1982)* при любом нечетном нату­ральном к делится на 3.

 

т. е. если к нечетно, то исходное выражение делится на 3.

Замечаем, что 1981=1 (той 3), 1982=2 (той 3). Заменяя в исход- пом выражении числа 1981, 1982 их Еычетами по модулю 3, получаем

 

 

Следовательно, левая часть сравнения делится на 3 тогда и только тогда, когда на 3 делится сумма 1+2й. Для степеней двойки имеем: 22=1, 23~2, 2*=!, 2®=2 и т. д. Вообще, применяя индукцию по к, убеждаемся, что 2Й=1 при к четном и 2А=2 при к нечетном. Таким серазом, при нечетном кВ разобранной задаче числа 1981 и 1982 могли быть заменены любыми числами а и Ь, дающими при делении на 3 остатки соответст­венно 1 и 2. Ни утверждение задачи, ни способ его доказательства от этого не изменились бы. Таким образом, в некоторых вопросах все числа, имеющие один и тот же вычет г по модулю п, и, следовательно, сравнимые между собой по этому модулю, оказываются взаимозаме­няемыми. Объединим все их в один класс, обозначаемый г:

 

 

Иными словами, класс г состоит из всех тех целых чисел, которые записываются в виде (2). Класс, определяемый равенством (4), нг бы­вают классом вычетов. Каждому вычету 0, 1, 2, . . ., п—1 отвечает июй класс вычетов, так что имеется ровно п различных класа з

 

 

Ясно, что эти классы попарно не пересекаются и каждое Целое -то попадает ровно в один класс.

Мы обнаруживаем, далее, что используя операции сложения и умножения чисел, можно производить аналогичные операции и над классами вычетов.

В самом деле, пусть т± и г2 — два класса вычетов. Выберем любые два числа из этих классов: сц&Ь а2^г2. Пусть оказалось, что сумма аЛ+а, имеет вычет г, а произведение а,а2 — вычет $:

 

 

Тогда будем считать, что «сумма» классов г^ и г2 равна г, а их «произ­ведение» равно х:

 

 

 

 

Законность этого определения обосновывается тем, что класс, которому принадлежит сумма й1-|-о2 (соответственно произведение о^) не за­висит от выбора элементов сц и а2 в «.пассах гг и г2.

Поясним данное определение на примере, взяв за модуль срав­нения число п—2 В этом случае имеем два класса вычетов - 0 и а операции над ними выглядят так:

 

 

Часто, когда это не вызывает путаницы, в обозначениях классоь вычетов опускают черту, записывая их как обычные натуральные '.исла. В основном тексте книги это делается без специальных оговорок. Выпишем, например, таблицы сложения и умножения классов по

модулю 4 с этих упрощенных обозначениях:

 

 

Эти таблицы можно понимать н буквально, считая, что оии опре» дсляют две операции на множестве {0, 1, 2, 3} — сложение и умножение но модулю 4.

2. Группы

Прежде чем дать определение группы, рассмотрим однн

важный пример.

 

Будем исходить из понятия взаимно однозначного отображения множества на себя. В случае конечного множества такое отображение называют обычно подстановкой. Пусть множество М состоит из чисел 1, 2, 3: М={1, 2, 3}. Чтобы задать какую-либо подстановку множе­ства М, достаточно указать для каждого из чисел 1, 2, 3 то число, в которое оно отображается этой подстановкой. Удобнее всего сделать это, исгользовав таблицу из двух строк,— в первой строке выписы­ваются (в любом порядке) числа 1, 2, 3, а во второй под каждым из них гишется соответствующее ему при дайной подстановке число. Скажем, обе таблицы задают одну и ту же подстановку, число 1 переходит в число 2, 2— в 3, 3 — в 1. Нетрудно указать все различные подстановки множества А", нх будет шесть:

 

 

 

 

 

 

 

Определим теперь на множестве 5= {с(, о2, . . ., а6} всех подстановок операцию умножения (или композицию) подстановок. Именно, произ­ведением подстановок а,- и о,- будем называть подстановку получаю­щуюся в результате последовательного выполнения сначала подста­новки с,-, а затем О/ (записывается: а,ау=аЛ). Например, (первая подстановка переводит число 1 в число 3, после ^его вторая подстановка переводит число 2 в число 3, так что в результате после­довательного выполнения подстановок число 1 перейдет в число 2 и т, д.). Читатель может проверить, что и тем самым убедиться, что произведение двух подстановок зависит, вообще говоря, от порядка сомножителей.

Множество 5 с определенной выше операцией умножения называют группой подстановок множества М.

Во-вторых, тождественная подстановка

 

переводящая каждый элемент в себя, играет роль единицы в обычном умножении, а именно, для любой подстановки а,-

 

Операция умножения на 5 обладает следующими свойствами. Во-первых, эта операция ассоциативна: для любых о,-, О/, сй

 

 

Наконец, вместе с каждой подстановкой с,- множество 5 содержит образую ей подстановку Су, которая переводит число о в число Ь тогда и только тогда, когда а,- переводит число Ь в число а. При этом, понятно, каждое из произведений и суо; будет тождественной подстановкой-'

 

 

Эти три свойства сохранятся, если распространить определение умножения подстановок множества {1, 2, 3} на случай подстановок любого конечного множества.

Более того, выяснилось, что имеются самые разнообразные си­стемы объектов с операцией, обладающей указанными свойствами.

Это привело к следующему (общему) определению группы ). Множество О, на котором определено умножение элементов, назы­вается группой, если выполняются три аксиомы:

 

2. В множестве С существует такой единичный элемент е, что

 

3. Для каждого элемента а множества С существует в О такой обратные элемент а-1, что

 

 

2. Существует такой нулевой элемент 0, что для любого элемента а из С,

 

3. Для каждого элемента а существует такой противоположный элемент (—а), что

 

1. Умножение ассоциативно: для любых элементов а, Ь, с из О

Обращаем внимание читателя на то, что в приведенном опреде­лении говорится об умножении элементов и используется связанная с обычным умножением терминология и символика. Этой «мультипли­кативной» терминологии мы и будем в дальнейшем придерживаться. Однако термин «умножение» нельзя понимать буквально; речь идет о любой операции, удовлетворяющей данным аксиомам. В частности, в ряде случаев естественнее называть операцию сложением и соот­ветственно переформулировать аксиомы группы, пользуясь термино­логией, связанной со сложением («аддитивной» терминологией): 1, Сложение ассоциативно: для любых элементов а, Ь, с из О

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

Читатель обнаружит далее, что многие примеры групп ему уже известны. Перечислим некоторые из них:

Множество всех ненулевых действительных чисел относительно операции умножения — «мультипликативная группа действительных чисел» К*.

Множество всех целых чисел относительно операции сложе­ния — «аддитивная группа целых] чисел» ч,.

Множество всех векторов в пространстве относительно опера­ции сложения векторов.

Множество всех многочленов с действительными коэффициен­тами относительно операции сложения многочленов.

Группы в примерах 1—4 имеют бесконечно много элементов, а группа 5 — конечная (6 элементов). Число элементов конечной группы называется ее порядком.

Из аксиом группы можно вывести, что в группе существует только один единичный элемент. Можно доказать также и единственность обратного элемента для всякого элемента группы.

Пример группы подстановок показывает, что умножение в группе может быть некоммутативным. Те группы, для которых опера­ция коммутативна, так и называются коммутативными (примеры 1-4).

Если некоторое подмножество Н группы С само образует группу относительно операции, определенной в С, то подмножество Н назы­вают подгруппой группы О.

Например, подмножества {о^ с2} и Н2= {а*, а4, а6} группы 5 явля.этся подгруппами этой группы. Подмножество четных целых чисел есть подгруппа аддитивной группы Е всех целых чисел, а под­множество нечетных чисел не будет подгруппой этой группы (сложение на 2 не задает операцию на этом подмножестве, так как сумма двух нечетных чисел есть число четное).

Имеет место следующая теорема.

Для того чтобы подмножество Н являлось подгруппой группы О, необходимо и достаточно, чтобы выполнялись два условия-.

произведение любых элементов Н1, Н2 из подмножества Н также является элементом из Н (Н^^Н);

если Н^Н, то и обратный к нему элемент принадлежит

II (И-1 ею-

 

Пои таком определении степени выполняются хорошо знакомые

Наиболее просты так называемые циклические подгруппы, кото­рыми обладает любая группа О. Со всяким элементом можно свг- зать «порожденную» им циклическую подгруппу, которая, по существу ( представляет собой наименьшую из подгрупп, содержащую данный элемент. Чтобы определить ее, введем понятие степени элемента полагая е"=е и для любого натурального кнам правила действий со степенями: для любых целых чисел тик

 

 

 

 

Ясно, что всякая подгруппа, содержащая элемент должна со­держать любые его степени. С другой стороны, уже само множество степеней образует, как нетрудно убедиться, группу.

Указанную группу называют циклической подгруппой, порож­денной элементом ее обозначают символом (§), а сам элемент § назы­вается образующим элементом этой группы.

Может случиться, что для некоторого элемента § циклическая подгруппа (я) совпадает со всей группой С, и тогда группа С также называется циклической. Например, аддитивная группа целых чисел есть циклическая группа с образующим элементом 1 (или —1), а ее подгруппа четных чисел — циклическая с образующим элементом 2. Являясь наиболее простыми, циклические группы служат важным инструментом для изучения групп, имеющих более сложное строение.

Между группой и любой ее подгруппой существует определенная связь, которую можно охарактеризовать с помощью понятия смеж­ного класса по подгруппе.

Пусть Н — подгруппа группы С и //^С— произвольный элемент группы О (мы не требуем, чтобы он обязательно принадлежал под­группе). Множество всевозможных произведений ф, где Н — любой элемент подгруппы Н, называется смежным классом (точнее, левым смежным классом) по подгруппе Н, а элемент # — его представителем. Обозначая левый смежный класс чесез рН, имеем, следовательно,

 

 

Аналогично определяются правые смежные классы Н§. Если группа О — коммутативная, то Нц—цН.

Для смежных классов, безразлично, левых или правых, справед­ливы два основных факта.

В случае конечной подгруппы И число элементов в любом смеж­ном классе одно и то же и совпадает с порядком подгруппы.

Любые два смежных класса и ^Н либо совпадают, либо вовсе не имеют общих элементов.

Для иллюстрации понятия смежного класса рассмотрим следующий пример. Пусть 2 — аддитивная группа целых чисел, а Н — ее под­группа, состоящая из чисел, кратных пяти. Тогда можно «выписать» следующие смежные классы:

 

 

Читатель сразу же заметит, что это классы вычетов О, Т, 3, ?., 4 по мо­дулю 5. Легко видеть, что всякий смежный класс Н+п о падает с. одним из этих пяти, и что классы эти не йересекаются. Непосредственно видно также, что

В случае, когда О и И — конечные группы порядков т п п, из последнего равенства вытекает, что т=п-г. Мы пришли к следующей теореме Лагранжа ):

Порядок любой подгруппы конечной группы является делителем порядка группы.

Мы привели здесь простейшие определения и факты теории групп. За дальнейшими сведениями читатель может обратиться, например, к книгам [8], [9].

3. Кольца и поля

Часто приходится рассматривать множества, на кото­рых определены две операции, например, различные числовые множе­ства, множества многочленов, множества классов вычетов с опреде­ленными иа них операциями сложения и умножения. Выделяя не­которые свойства этих операций, общие для всех указанных множеств, мы приходим к еще одному важному алгебраическому понятию — по­нятию кольца.

Кольцом называется (непустое) множество К, на котором опре­делены две операции (сложение и умножение), обладающие следующими свойствами:

 

Оказывается, то же самое верно для любой группы: если Нщ, 2, . . .-, Н§г— все различные (правые) смежные классы группы О по подгруппе Н, то

 

множество К относительно сложения образует коммутативную группу;

умножение ассоциативно: для любых а, Ь, с ^ К

 

 

3) сложение и умножение подчиняются дистрибутивному закону:

 

 

 

 

для любых а, Ь, с^Л.

При этом множество К, рассматриваемое лишь относительно опе рации сложения, называется аддитивной группой кольца.

Приведем некоторые примеры колец.

Множество целых чисел с операциями сложения н умножения — кольцо целых чисел 2.

Множество многочленов от одного неизвестного с действитель­ными коэффициентами с операциями сложения и умножения много­членов — кольцо многочленов К [Л].

Множество классов вычетов по модулю п с операциями сложе­ния п умножения классов — кольцо классов вычетов

Читателю предлагается проверить выполнимость аксиом кольца в каждом из примеров. Остановимся подробнее на примере 3.

Как показывают примеры 1 и 2, необратимыми могут быть и ненулевые

Поскольку операции над классами вычетов сводятся к операциям над числами из этих классов, то свойства ассоциативности и комму­тативности этих операций вытекают из аналогичных свойств числового сложения и умножения. То же замечание относится к свойству дистри­бутивности. Роль нулевого элемента при сложении играет класс 0. Противоположным элементом для класса вычетов гф0 является класс п — г. Из определения сложения классов следует, что В общем определении кольца не содержится требование комму­тативности умножения. В том случае, если умножение обладает этим дополнительным свойством, кольцо называется коммутативным. В при­мерах 1—3 мы имеем как раз коммутативные кольца, а позднее (в при­ложении 5) познакомимся с важным примером некоммутативного кольца.

Умножение в кольце, как и в группе, является ассоциативной операцией, по другие свойства группового умножения в кольце могут не выполняться. Правда, большинство важных колец содержат еди­ничный элемент относительно умножения (скажем, кольца из примеров 1—3), но и такие кольца заведомо содержат элементы, для которых не существует обратного (необратимые элементы). В любом кольце необратим элемент 0 — нулевой элемент относительно сложения, так как доказывается, что он отличен от единичного и что для любого а^ /\ имеет место:

 

элементы. Так, в кольце целых чисел обратимы лишь 1 и —1, всякое другое пфО в кольце 2 не имеет обратного, так как 1/я^Е.

Рассмотрим таблицы умножения ненулевых элементов в кольцах вычетов 24 и ■

 

 

Таблица 19 показывает, что в кольце могут существовать ненуле­вые элементы, произведение которых равно нулю: в 2»2=б. Из этой же таблицы видно, что класс 2 необратим. Вообще, можно дока­зать, что ненулевые элементы, произведение которых равно нулю (на­зываемые делителями нуля), всегда необратимы. С другой стороны, таблица 20 показывает, что в кольце Ъ 6 всякий ненулевой элемент обратим. Кольца с этим свойством имеют особое значение. Примем такое определение.

Коммутативное кольцо с единицей, в котором всякий ненулевой элемент обратим, называется полем.

Множество ненулевых элементов поля относительно умножения образует в силу определения поля коммутативную группу, которая называется мультипликативной группой поля.

Простейшими примерами числовых полей являются поле рацио­нальных чисел О и поле действительных чисел К (разумеется, отно­сительно операций сложения и умножения чисел). Полем, как ясно из предыдущего, является и кольцо Вообще, можно доказать, что при любом простом р (и только в этом случае) кольцо вычетов Ър является полем. Оно называется полем вычетов по модулю р. В таблице 21 указаны элементы, обратные к ненулевым элементам поля вычетов %Поля вычетов %р являются простейшими примерами конечных полей. В алгебре доказывается, что в произвольном конечном поле число элементов ц всегда есть степень простого числа: <?=р". Справед­ливо и обратное утверждение: для любого д, являющегося степенью простого числа, существует поле с д элементами.

 

 

Конечные поля часто называют полями Галуа (их обозначают С Г (д)); важное их свойство, используемое, в частности, и в теории кодирования, состоит в следующем:

Мультипликативная группа поля Галуа является циклической группой порядка I.

Образующий элемент мультипликативной группы поля Галуа называют примитивным элементом. Так, в поле 2? примитивным элементом является класс вычетов 3. Действительно, его степени исчерпывают все ненулевые элементы поля.

Заметим, что класс 2 не является примитивным элементом в 2?» так как среди его степеней нет, например, класса 3. В то же время имеется очень много простых чисел р, для которых элемент 2 прими­тивен в %р. Так обстоит дело в полях 2з> 1ц и т. д. В теории чисел известна следующая до сих пор не решенная задача:

Бесконечно ли множество тех простых чисел р, для которых 3 является примитивным элементом в

Интересно, что с ответом на этот вопрос связано решение неко­торых проблем теории кодирования.

В заключение определим еще одно важное понятие, связанное с. кольцом,— понятие идеала.

Подмножество / кольца К называется его (двусторонним) идеалом, если оно само является кольцом относительно операций на К и если для любых элементов а^К и Ь^/ оба произведения аЬ и Ьа принад­лежат 1.

Так, множество четных чисел есть идеал кольца 2. Читатель легко проверит, что и вообще всякое множество чис^л крагных ка­кому-нибудь числу к, являете? идеалом кольцч

Рекомендуем читателю найти идеалы колец вычетоь 2,. 1ц, 2з и кольца многочлене» КIX],4. Арифметическое я-мериое секторное пространство

 

 

Всякая точка на плоскости при выбранной системе координат задается парой (а, Р) своих координат; числа а и Р можно понимать также как координаты радиуса-вектора с концом в этой точке. Аналогично, в пространстве тройка (а, Р, V) определяет точку или вектор с координатами а, р, у. Именно на этом основывается хорошо известная читателю геометрическая интерпретация систем линейных уравнений с двумя или тремя неизвестными. Так, в случае системы двух линейных уравнений с двумя неизвестными как вектор с координатами а и Р (рисунок соответствует случаю, когда система имеет единственное решение).

Аналогично можно поступить с системой линейных уравнений с тремя неизвестными, интерпретируя каждое уравнение как уравнение плоскости в пространстве.

В математике и различных ее приложениях (в частности, в теории кодирования) приходится иметь дело с системами линейных уравнений, содержащих более трех неизвестных. Системой линейных уравнений с п неизвестными хх-г          хп называется совокупность уравнений вида

 

 

где о,-у и 6,- — произвольные действительные числа. Число уравнений в системе может быть любым и никак не связано с числом неизвестных. Коэффициенты при неизвестных ац имеют двойную нумерацию: первый индекс I указывает номер уравнения, второй индекс /—номер неиз­вестного, при котором стоит данный коэффициент. Всякое решение системы понимается как набор (действительных) значений неизвестных (а!, а2,..а„), обращающих каждое уравнение в верное равенство.

Хотя непосредственное геометрическое истолкование системы (1) при п>3 уже невозможно, однако вполне возможно и во многих от­ношениях удобно распространить на случай произвольного п геомет­рический язык пространства двух или трех измерений. Этой цели и служат дальнейшие определения.

Всякий упорядоченный набор из п действительных чисел (а*, а2, . . . . . ., а„) называется п-мерным арифметическим вектором, а сами числа «1, а2,      — координатами этого вектора.

Для обозначения векторов используется, как правило, жирный шрифт и для вектора а с координатами аь а2, . , ., ап сохраняется обычная сЬопма записи:

 

 

По аналогии с обычной плоскостью множество всех п-мерных век­торов, удовлетворяющих линейному уравнению с п неизвестными, называют гиперплоскостью в «-мерном пространстве. При таком оп­ределении множество всех решений системы (1) есть не что иное, как пересечение нескольких гиперплоскостей.

 

— два п-мерных вектора, то их суммой называется вектор

 

Произведением вектора а на число Я называется вектор

 

 

где — действительные числа. Например, линейная комбинация Еекторов (2) с коэффициентами и и — это вектор

 

Сложение и умножение п-мерных векторов определяются по тем же правилам, что и для обычных векторов. А именно, если

Множество всех п-мериых арифметических векторов с операциями сложения векторов и умножения вектора на число называется ариф­метическим п-мерным векторным пространством Ь„.

Используя введенные операции, можно рассматривать произволь­ные линейные комбинации нескольких векторов, т. е. выражения вида

В трехмерном пространстве векторов особую роль играет тройка векторов I, у, к (координатные орты), по которым разлагается любой вектор а:

 

 

где х, у, г — действительные числа (координаты вектора а).

 

Всякий вектор а есть, очевидно, линейная комбинация векторов ву,

 

В и-мер ном случае такую же роль играет следующая система век­торов:

причем коэффициенты аъ а2, . . ., ап совпадают с координатами век­тора а.

Обозначая через 0 вектор, все координаты которого равны нулю (кратко, нулевой вектор), введем следующее важное определение:

Система векторов аг, а2, . . ад. называется линейно зависимой, если существует равная нулевому вектору линейная комбинация в которой хотя бы один из коэффициентов >.2            отличен от нуля. В противном случае система называется линейно независимой. Так, векторы

 

 

Линейная зависимость, как видно из определения, равносильна (при 2) тому, что хотя бы один из векторов системы является ли­нейной комбинацией остальных.

Если система состоит из двух векторов сц, а2, то линейная зави­симость системы означает, что один из векторов пропорционален дру- тому, скажем, а1=Яа2; в трехмерном случае это равносильно коллине­арности векторов ах и а2. Точно так же линейная зависимость системы из трех векторов в обычном пространстве означает компланарность этих векторов. Понятие линейной зависимости является, таким обра зом, естественным обобщением понятий коллинеарности и компланар­ности,Нетрудно убедиться, что векторы е%, е«, , , еп из системы (5) линейно независимы. Следовательно, в «-мерном пространстве сущест­вуют системы из « линейно независимых векторов. Можно показать,- что всякая система из большего числа векторов линейно зависима,

Всякая система аг, а2                   из п линейно независимых векторов

«-мерного пространства Ьп называется его базисом.

При таком определении сохраняются все основные свойства скаляр­ного произведения трехмерных векторов. Векторы а и Ь называются ортогональными, если их скалярное произведение равно нулю:

 

Любой вектор а пространства Ьп раскладывается, и притом един­ственным образом, по векторам произвольного базиса Щ, оа, . ( ., ап 1

 

 

Этот факт легко устанавливается на основании определения базиса, Продолжая аналогию с трехмерным пространством, можно и в «-мерном случае определить скалярное произведение а-0 векторов, полагая

 

 

В теории линейных кодов используется еще одно важное понятие — понятие подпространства. Подмножество V пространства Ьп называ­ется подпространством этого пространства, если

для любых векторов а, Ь, принадлежащих V, их сумма а-\-Ь также принадлежит V;

для любого вектора а, принадлежащего V, и для любого дей­ствительного числа % вектор 7.а также принадлежит V.

Например, множество всех линейных комбинаций векторов е2 из системы (5) будет подпространством пространства Ь„.

В линейкой алгебре доказывается, что во есяком подпространстве V существует такая линейно независимая система векторов аг, а2, ... , . ., ачто всякий вектор а подпространства является линейной ком­бинацией этих векторов.

 

 

Указанная система векторов называется базисом подпространства V, Из определения пространства и подпространства непосредственно следует, что пространство Ьп есть коммутативная группа относительно операции сложения векторов, а любое его подпространство V является подгруппой этой группы. В этом смысле можно, например, рассмат­ривать смежные классы пространства Ъп по подпространству V.

В заключение подчеркнем, то если в теории «-мерного арифме­тического пространства вместо действительных чисел (т. е. элементов

поля действительных чисел) рассматривать элементы произвольного поля Р, то все определения и факты, приведенные выше, сохранили бы силу.

В теории кодирования важную роль играет случай, когда поле Р есть поле вычетов которое, как мы знаем, конечно. В этом случае соответствующее п-мерное пространство также конечно и содержит, как нетрудно видеть, рп элементов.

Понятие пространства, как и понятия группы и кольца, допускает также и аксиоматическое определение. За подробностями мы отсылаем читателя к любому курсу линейной алгебры.

5. Алгебра матриц

Большую роль в линейной алгебре и многих других областях математики играют так называемые матрицы.

Под матрицей понимают прямоугольную таблицу вида

 

(I)

 где буквы а,•/ обозначают некоторые элементы. Эти обозначения содер­жат два индекса, первый из которых указывает номер строки, а вто­рой — номер столбца, на пересечении которых находится соответст­вующий элемент. Про матрицу, у которой т строк и п столбцов, го­ворят, что она имеет порядок тХп. В случае, когда число строк и столбцов одинаково (т=п), матрица называется квадратней порядка п.

Если т= 1, то матрицу можно понимать как вектор, координаты которого записаны в строку; ее тогда так и называют вектор-строка. Точно так же в случае одностолбцовой матрицы пользуются термином вектор-столбеи. Иногда матрицу обозначают одной буквой (А, В и т. д.), а вместо (1) часто используется сокращенное обозначение (а;у).

Если в исходной матрице А строки и столбцы поменять ролями, то получим матрицу, называемую транспонированной к А (обознача­ется Лт). Матрица, транспонированная к матрице (1), имеет вид:

 

Для матриц с действительными элементами определяются опе­рации сложения матриц и умножения матрицы на число, аналогичные операциям над Еекторами.. а именно, для любых двух матриц порядка иХй

 

н для любой матрицы и любого числа а

 

 

— две таких матрицы, то их произведением

 

Вместе с тем, нетрудно доказать, что умножение матриц ассоциативно:

 

 

Действительно, из формулы (2) следует, что

 

для любой квадратной матрицы А.

Определение этих операций выглядит вполне естественно. Иначе обстоит дело с довольно своеобразной операцией умножения матриц. Рассмотрим сначала умножение квадратных матриц одного порядка п, Ргпи

называется квадратная матрица порядка п, произвольный элемент которой вычисляется по правилу:

 

 

Иначе говоря, чтобы получить элемент 1-й строки и /-го столбца мат­рицы С—А -В, нужно взять сумму произведений элементов 1-й строки матрицы А на соответствующие элементы /-го столбца матрицы В. Например,

 

 

Умножение матриц некоммутативно, т. е., вообще говоря, А-ВФВ-А. Так, перемножив две предыдущие матрицы в обратном порядке, полу­чим иную матрицу:

 

 

Особую роль (подобную числовой единице) играет так называемая единичная матрица

Можно убедиться, что множество всех квадратных матриц задан­ного порядка образует относительно введенных операций сложения и умножения (некоммутативное) кольцо.

Правило умножения матриц можно распространить и на прямо­угольные матрицы, не являющиеся квадратными. Формула (2) по­зволяет это сделать, если число столбцов первой матрицы А совпадает с числом строк матрицы В. Например,

 

 

При этом получающаяся матрица имеет столько же строк, сколько первый сомножитель, и столько же столбцов, сколько второй. Поль­зуясь операциями над матрицами, мы получаем возможность записы­вать произвольные системы уравнений в краткой матричной форме. Действительно, пусть матрица

 

 

составлена из коэффициентов при неизвестных системы (1) приложения 4 (в этом случае она называется матрицей системы)- Рассмотрим векторы- столбцы неизвестных и свободных членов, обозначая их соответственно через х н Ь:

 

 

Тогда произведение Ах есть матрица с т строками и одним столбцом, т. е. вектор-столбец, элементы которого вычисляются согласно фор­муле (2). Таким образом,

 

 

Каждое из уравнений системы (1) означает равенство соответствующих координат вектора Ах и вектора Ь, и вся система в целом означает тогда равенство

 

Полученная краткая запись н есть матричная форма системы линей­ных уравнений. Подобная матричная запись встречается во множестве других ситуаций, и она широко используется в математической, физи­ческой и технической литературе.

Все сказанное о матрицах с действительными элементами в равной мере относится к матрицам с элементами из произвольного поля Р. Так, в теории кодирования приходится рассматривать матрицы, со­ставленные из элементов конечного поля. Естественно, что при опери­ровании с такими матрицами их элементы складываются и умножаются в соответствии с «арифметикой» поля Р. Вот, к примеру, как перемно­жаются две матрицы с элементами из

 

 

6. Задачи и дополнения

1. Покажите, что преобразование, обратное параллель­ному переносу в направлении вектора а, есть параллельный перенос в противоположном направлении (на вектор —а).

Пусть /—симметрия плоскости относительно оси Ох, д—пово. рот плоскости на л/2 против часовой стрелки. Проверьте, что преоб­разование есть симметрия относительно биссектрисы 1-го и 3-го координатных углов. Найдите также преобразование и убедитесь, что /в Ф е/.

 

 

Операция произведения преобразований обладает свойством ассоциативности, это значит, что для любой тройки преобразова­ний Л, /г, /з выполняется равенство

 

 

Справедливость соотношения вытекает из того, что обе его части есть результат последовательного выполнения трех преобразований сначала затем /г, затем /3.

Какие из следующих множеств образуют группу преобразова­ний плоскости:

а)         множество всех параллельных переносов;

б)         множество всех вращений относительно фиксированного центра;

в)         множество всех вращений плоскости;

г)         множество всевозможных осевых симметрий.

Напомним, что совокупность всех подстановок п-злементного множества гбразует группу. Она называется симметрической группой степени п и обозначается 8п. Найдите все подстановки из 53, не меняющие значения функций

Проверьте прямым вычислением, что найденные в каждом из случаев подстановки образуют группы.

 

6. Транспозицией называется подстановка, переставляющая ка­кие-либо два символа, а все прочие оставляющая на месте. Например, нз двух подстановок

 

 

первая является транспозицией, вторая — нет, но она может быть пред­ставлена в Енде произведения транспозиций следующим образом*

 

 

Справедлив общий факт: всякая подстановка разлагается в произведение транспозиций.

Зто разложение неоднозначно, например, вместо (1) мы могли бы написать

 

 

Однако можно доказать, что при всех представлениях подстановки в виде произведения транспозиций число сомножителей имеет одина­ковую четность.

Подстановка называется четной, если число траиспознций и в разложении четно, в противном случае подстановка называется нечетной.

Покажите, что множество всех четных подстановок образует группу, она обозначается Ап и называется знакопеременной группой,

Убедитесь, что множество подстановок из задачи 5 (б) совпа­дает со знакопеременной группой Л3.

 

Вообще рассмотрим функцию

 

 

Тогда множество всех подстановок переменных, не меняющих зна­чения этой функции, совпадает со знакопеременной группой Ап. Это вытекает из того, что при любой транспозиции значение функции (2) меняется на противоположное, напрмер,

 

 

Сказанное объясняет и происхождение термина «знакопеременная группа».

9. Для числовых групп типичной является такая ситуация, когда все степени одного элемента д Ф 1 различны ). Пели же обратиться к группам преобразований, то в них зачастую бывает так, что две различные степени одного элемента (преобразования) совпадают. В качестве примера таких элементов рассмотрите преобразования; а) симметрию относительно оси; б) поворот плоскости на угол л/3 (вообще на угол 2л/к).

Что касается конечных групп, то здесь для любого элемента д существуют такие натуральные кит (к Ф т), что

 

 

Если бы это было не так, то группа содержала бы бесконечно много элементов.

Пусть в равенстве (3) к > т. Умножим обе его части иа элемент д~т, это даст следующее равенство дк~т =е, или д" = е, где п—к—т > 0.

В описанной ситуации обязательно найдется наименьшее нату­ральное п со свойством д" — е, которое называется порядком элемен­та д.

Если же все степени элемента в различны, то д называется элементом бесконечного порядка. 10. Найдите порядки следующих подстановок:

 

 

 

 

 

 11. Пусть 0 = (д)—конечная циклическая группа, и ее образую­щий д имеет порядок п. Рассмотрим произвольную степень дт.

Если показатель кратен п(т = 5п), то дт = {>п8 = (д")8 = е8 = е. Если же показатель т произволен, то его всегда можно записать в виде: т=5П-\-г,   — 1, где г — остаток от деления т на п.

Но тогда цв1=д*п+г==дт.дг- е-дг—дг. Зто значит, что все элемен­ты группы 0 = (д) исчерпываются следующими п элементами:

 

 

Мы доказали, что порядок конечной циклической группы совпадает с порядком ее образующего. Как, используя сказанное, вывести из теоремы Лагранжа следующие утверждения:

а)         порядок любого элемента конечной группы является делителем порядка этой группы;

б)         всякая группа простого порядка является циклической?Найдите возможные порядки элементов в группах 03, 05, цик­лической группе порядка 12.

Проверьте, что всякая подгруппа Н циклической группы С = ((у) сама является циклической.

Указание: рассмотрите наименьшую положительную степень е Н, покажите, что Н — (<7к).

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

Рассмотрим произведение любых двух элементов а и 6 и преоб­разуем его следующим образом:

 

 

Второе слагаемое, как видно нз равенства, играет роль нейтраль­ного элемента при сложении. В силу его единственности 06 = 0 для всякого Ь ^ К.

Какие из следующих числовых множеств являются кольцами относительно обычных операций сложения и умножения:

а)         множество четных чисел;

б)         множество чисел, кратных данному п;

в)         -множество многочленов степени <п с действительными коэф­фициентами;

г)         множество всех многочленов с целыми коэффициентами;

д)         множество неотрицательных действительных чисел;

е)         множество всех чисел вида а-\-Ь гдеаи Ь—рациональные.

В каких случаях мы имеем дело с кольцом с единицей, в ка­ких—с полем?

Покажем, [что делитель нуля (левый или правый) не может быть обратим. В самом деле, пусть ха= 1 и аЬ = 0. Тогда

 

 

Следовательно, Ъ — 0 и а не является делителем нуля.

Из сказанного непосредственно вытекает, что никакое поле не содержит делителей нуля.

Показать, что если п = П1-/г2—число составное, то %п не является полем.

Показать, что ненулевой элемент к^Жп обратим тогда и толь­ко тогда, когда числа к и п взаимно просты, и что в противном случае ~к является делителем нуля.

Пользуясь предыдущим утверждением, найдите обратимые элементы и делители нуля в кольцах вычетов %е> 2ц> Для обратимых элементов найдите обратные. Для элементов к, явля-ющихся делителями нуля, найдите т Ф О такой, что к-т = б. Является ли такой класс т единственным?

29. Уже самые простые сведения о кольцах и группах могут быть применены в различных математических вопросах. Прекрасной иллю­страцией этого является теория чисел. Рассмотрим, например, хорошо известную теорему (малую теорему Ферма):

Если р—простое, то для любого натурального а число аР— а делится иа р.

Раггл'жлаем так:

 

 

Если а делится на р, то утверждение очевидно.

Пусть а не делится па р и а=тр-\-г (0 <г^р—1). Тогда в поле вычетов я^л и г Ф б. Делимость числа ар-1—1 на р рав­носильна тому, что в справедливо равенство гР-1 — ! = б или равносильное ему

 

 

Так как порядок мультипликативной группы поля _ р равен р—1, то из теоремы Лагранжа вытекает справедливость равенства (1), и это доказывает малую теорему Ферма.

Подумайте (это не простая задача), как с помощью указан­ных методов можно доказать утверждение: если р — простое, то (р—1)1 + 1 делится на р. Это теорема Вильсона, одна из наиболее изящных теорем элементарной теории чисел.

Функция Эйлера ф (п) определяется в теории чисел как ко­личество натуральных чисел, меньших п и взаимно простых с ним. Например, ф(4)=2, ф(8)=4 и т. д. Для всякого простого р очеви­дно ф(р) = р—1 ■ Обобщением малой теоремы Ферма является теоре­ма Эйлера, которая формулируется так:

Для любого натурального а, взаимно простого с п, а.ч> <">—1 де­лится на п. Например, при п = 8, а — 5 имеем 54—1=624 = 8 x 78. Можно предложить следующий план доказательства теоремы Эйлера (детали — на усмотрение читателя):

а)         показать, что множество обратимых элементов любого кольца образует группу относительно умножения;

б)         рассмотреть кольцо вычетов Ч,п и убедиться, что группа его обратимых элементов имеет порядок ф (п) (вспомните утверждение пункта 18);

в)         дальнейшие рассуждения таковы же, как и при доказатель­стве малой теоремы Ферма.

Найти все решения системы линейных уравнений в поле вычетов: а) по модулю 3; б) по модулю 5.

24. Многочлен р (X) ^ Г [X] называется неприводимым, если не существует разложения р (X) = / (X) % (X), в котором / (X), § (X) ^ [X] и степени сомножителей меньше, чем степень многочлена

Р(Х).

Выяснить, являются ли следующие многочлены: неприводимыми над полем: а) б) И3; в) О; г) К.

25. Разложить на неприводимые множители многочлен

йад полем: а) б) %3; в) С).

26. Найти наибольший общий делитель многочленов

 

 

 

 

над полем: а) б) О.

Доказать что в конечном кольце с единицей любой ненуле­вой элемент либо обратим, либо является делителем нуля. Верно ли это утверждение без предположения конечности (вспомните кольцо Ж)?

Используя предыдущее утверждение, докажите, что конечисе коммутативное кольцо без делителей нуля, содержащее более одно­го элемента, является полем.

В вопросах, связанных с решением систем линейных урав­нений, особую роль играет понятие определителя квадратней матрицы.

 

 

 

над полем: а) ж3; б) О?

В случае, если матрица обратима, найти обратную.

Введем здесь это понятие применительно к матрице 2-го порядка

 

 

с элементами из произвольного поля Р. Ее определителем называ­ется величина

 

 

Доказать, что в кольце всех матриц 2-го порядка матрица (5) обра­тима тогда и только тогда, когда ее определитель отличен от нуля (указать способ отыскания обратной матрицы). В противном случае матрица (5) является делителем нуля.

30. Какие из перечисленных ниже матриц обратимы или явля­ются делителями нуля