Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Все сказанное о матрицах с действительными элементами в равной мере относится к матрицам с элементами из произвольного поля F, Так, в теории кодирования приходится рассматривать матрицы, составленные из элементов конечного поля. Естественно, что при оперировании с такими матрицами их элементы складываются и умножаются в соответствии с «арифметикой» поля F. Вот, к примеру, как перемножаются две матрицы с элементами из
11 1 о) ' (j Jy Со Oy
6. Задачи и дополнения
1. Покажите, что преобразование, обратное параллельному переносу в направлении вектора а, есть параллельный перенос а противоположном направлении (на вектор —а).
2. Пусть / — симметрия плоскости относительно оси Ox, g—пово. рот плоскости на л/2 против часовой стрелки. Проверьте, что преобразование jg есть симметрия относительно биссектрисы 1-го и 3-го координатных углов. Найдите также преобразование gj и убедитесь, что [g ^ g[.
3. Операция произведения преобразований обладает свойством ассоциативности, это значит, что для любой тройки преобразований fly /2, Із выполняется равенство
(filtl h = fi(fJt).
Справедливость соотношения вытекгет из того, что обе его части есть результат последовательного выполнения трех преобразований сначала затем /2, затем f3.
4. Какие из следующих множеств образуют группу преобразований плоскости:
а) множество всех параллельных переносов;
б) множество всех вращений относительно фиксированного центра;
в) множество всех вращений плоскости;
г) множество всевозможных осевых симметрий.
5. Напомним, что совокупность всех подстановок «-элементного множества образует группу. Она называется симметрической группой степени п и обозначается Sn. Найдите все подстановки из S3, не меняющие значения функций
а) ф1 = X1X2-jTX2Xs^-X1X3-,
б) (P2=(X1-X2)(X1-X3)(X2-X3).
,136Проверьте прямым вычислением, что найденные в каждом из случаев подстановки образуют группы.
6. Транспозицией называется подстановка, переставляющая какие-либо два символа, а все прочие оставляющая на месте. Например, из двух подстановок
/1 2 3 А\ /1 2 3 А\ 3 2 AJ' \2 3 4 Iy
первая является транспозицией, вторая — нет, но она может быть представлена в виде произведения транспозиций следующим образом1
/1 2 3 4^/1 2 3 4W 1 2 3 4\ /1 2 3 4\ \2 3 4 \) \2 1 3 4/ ІЗ 2 1 4/\4 2 3 Iy1 ( '
Справедлив общий факт: всякая подстановка разлагается в произведение транспозиций.
Это разложение неоднозначно, например, вместо (1) мы могли бы написать
/1 2 3 4N /1 2 3 4W1 2 3 4W1 2 3 4\ V2 3 4 3 2 4Ді 4 3 2J\2 1 3 Aj'
і
Однако можно доказать, что при всех представлениях подстановки в виде произведения транспозиций число сомножителей имеет одинаковую четность.
Подстановка называется четной, если число транспозиций и в разложении четно, в противном случае подстановка называется нечетной.
7. Покажите, что множество всех четных подстановок образует группу, она сбозначается An и называется знакопеременной группой.
8. Убедитесь, что множество подстановок из задачи 5 (б) совпадает со знакопеременной группой A3.
Вообще рассмотрим функцию
F (хи хг.....*„)= Д (*,— *,¦). і, /,= 1, 2, ..., п. (2)
< < /
Тогда множество всех подстановок переменных, не меняющих значения этой функции, совпадает со знакопеременной группой An. Это вытекает из того, что при любой транспозиции значение функции (2) меняется на противоположное, например,
F (х2, X1,..., Xrl)=-F (хи х2, ..., хп).
Сказанное объясняет и происхождение термина «знакопеременная группа».
,1379. Для числовых групп типичной является такая ситуация, когда все степени одного элемента g Ф 1 различны *). Если же обратиться к группам преобразований, то в них зачастую бывает так, что две различные степени одного элемента (преобразования) совпадают, В качестве примера таких элементов рассмотрите преобразования; а) симметрию относительно оси; б) поворот плоскости на угол л/3 (вообще на угол 2n/k).
Что касается конечных групп, то здесь для любого элемента g существуют такие натуральные kam (k ф т), что
g* = g«. (3)
Если бы это было не так, то группа содержала бы бесконечно много элементов.
Пусть в равенстве (3) k > т. Умножим сбе его части на элемент g~m, это даст следующее равенство gfl~m=e, или gn = e, где n = k—m > 0.
В описанной ситуации обязательно найдется наименьшее натуральное п со свойством gn = e, которое называется порядком элемента g.
Если же все степени элемента g
g° = e, g, g2, ..., g"
различны, то g называется элементом бесконечного порядка.
10. Найдите порядки следующих подстановок:
(1 2 3 4 5\ /1 2 3 4 5\ /1 2 3 4 5\
V2 3 4 5 \), І2 3 1 5 4 J1 U 4 5 2 3J.
11. Пусть G = (g)— конечная циклическая группа, и ее образующий g имеет порядок п. Рассмотрим произвольную степень gm.
Если показатель кратен n(m = sn), то gm =gns = (gt)s = es = е. Если же показатель т произволен, то его всегда можно записать в виде: m = sn-{-r, O^rsgji— 1, где г — остаток от деления т на п. Но тогда gn=gS" + r = gsn-gr=:e-gr = gr. Это значит, что все элементы группы G = (g) исчерпываются следующими п элементами: