Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.4. Подгруппы и факторгруппы

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

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

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

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

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

Теорема 2.3. Два элемента группы О принадлеоюат одному а тому же левому смежному классу по подгруппе тогда и только тогда, когда произведение принадлежит Н.

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

Теорема 2.4. Каждый элемент группы О принадлежит одному и только одному смежному классу по подгруппе И.

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

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

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

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

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

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

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

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

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

Рассмотрим более важный пример. Пусть аддитивная группа, состоящая из всех положительных и отрицательных целых чисел и нуля, и пусть подгруппа, состоящая из всех чисел, кратных целому Все числа от нуля до принадлежат различным смежным классам, потому что для того, чтобы два элемента а и b принадлежали одному и тому же смежному классу, необходимо, чтобы элемент принадлежал подгруппе и, таким образом, был кратен Эти числа могут быть выбраны образующими смежных классов, и легко видеть, что смежных классов с другими образующими не существует. Поскольку группа О — абелева, то может быть определена операция сложения смежных классов, и смежные классы образуют группу. Например, пусть Тогда смежные классы оказываются строками таблицы:

ели их обозначить соответственно то таблица сложения меет вид

В этой таблице можно узнать таблицу сложения чисел по модулю 3.

<< Предыдущий параграф Следующий параграф >>
Оглавление