ЗАКЛЮЧЕНИЕ
Наши рассказы о кодировании подошли к концу. Мы познакомились, конечно, далеко не со всеми задачами этой теории, но в той или иной мере затронули три ее основных направления — кодирование с целью засекречивания сообщений, кодирование с целью сжатия информации, наконец, кодирование с целью исправления и обнаружения ошибок. Нам хотелось дать представление читателю, сколь широки и многообразны связи этой теории с разными разделами математики, и как порой самые абстрактные математические теории могут с успехом применяться для решения практических задач.
Дальнейшее проникновение в проблематику теории кодирования (подробное изучение циклических кодов и их обобщении, знакомство с кодами, исправляющими пакеты ошибок, и специфическими алгоритмами их декодирования и т. д.) требует уже значительно более серьезной математической подготовки. Впрочем, интересующийся читатель может при желании обратиться к литературе, список которой приводится в конце книги.ПРИЛОЖЕНИЕ
В школьной математике рассматриваются различнее операции над числами. Простейшие из них — сложение и обратная к нему операция вычитания, и умножение, для которого обратной операцией является деление. Подобные действия приходится производить не только над числами, но и над другими, более сложными объектами. Это можно обнаружить уже и в школьном курсе: на уроках геометрии и физики учат складывать и вычитать векторы, а на уроках алгебры рассматривают операции сложения и умножении многочленов. Однако список таких объектов гораздо обширнее. Мы познакомимся с некоторыми из них, наиболее важными для наших целей.
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. Какие из перечисленных ниже матриц обратимы или являются делителями нуля