<< Предыдущая

стр. 71
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

3 н ^ 1 ь-> 2.

Значит, произведение этих перестановок равно
123
^'132
Как мы уже отмечали, по своей природе математики очень лени­
вы. Поэтому и матрица в качестве обозначения перестановки их не
устраивает. Действительно, в каждой перестановке мы должны вы­
писывать неизменную первую строку. Кроме того, отдельные столб­
цы матрицы излишни, например, первый столбец перестановки h.
Введем еще одно обозначение перестановок, лаконичное и ясное, что
вполне устраивает любого математика. Но сначала нам необходимо
понятие цикла.

Определение А. 16. Циклом или 77-циклом [xi^ • • • 7 '^п) называется
перестановка / , действующая по правилу: f{xi) = Х2-, /(^2) = ^з^
. . . , f{xn-i) = Хп, f{xn) = Ж и f{x) =^ X, если х ^ {xi, . . . , Хп}.
1
Например, перестановка
12 3
231
является циклом, который можно записать по-разному: (1,2,3) =
= (2,3,1) = (3,1,2). Заметим, что не любая перестановка является
циклом. Приведем пример, когда перестановка равна произведению
двух 2-циклов и 1-цикла. Причем 1-цикл математики, как правило,
выбрасывают из произведения, правомерно считая его тождествен­
ной перестановкой, т. е. перестановкой, которая реально ничего не
переставляет.
12 3 4 5
3 2 15 4 /-(1.3)(2)(4,5)-(1,3)(4,5)-(4,5)(1,3).

Два цикла (^i, Х2^ . . . , Хп) и (?/i, ?/2, . . . , Ут) называются независи-
462 Прилодюение А. Основная математическая терминология

мыми, если {ж1, } П {уь ^2, • • •, Ут} = ^- Легко показать,
что независимые циклы а и т перестановочны в произведениях:
а от — т о а,

С другой стороны, свойство перестановочности не выполнено ^\ля
зависимых циклов:
(1,2,3,4) о (3,5) = (1,2,3,5,4) ф (1,2,5,3,4) = (3,5) о (1,2,3,4).
Что делает циклы по настоящему интересными, так это следующее
утверждение.

Лемма А. 17, Любую перестановку можно представить в виде про­
изведения независимых циклов.
Доказательство. Пусть а Е Sn- Обозначим через ai цикл
(l,a(l),c7(a(l)),...,a(...a(l)...)),
В котором мы применяем а до тех пор, пока не получим снова 1.
Затем берем такое число :г G {1, . . . , п}, что cri{x) = ж, и определяем
второй цикл
С 2 = (ж, а{х), (т{а{х)),... , сг(...
Г а{х)...)).
После этого возьмем число, которое остается неподвижным как при
действии (71, так и сг2, и определяем цикл сгз. Будем продолжать про­
цесс до тех пор, пока не исчерпаем все натуральные числа от 1 до п.
Полученные в результате циклы cri, . . . , сг^, очевидно, независимы,
а их произведение равно исходной перестановке а. Ш
Очень приятно, что приведенное доказательство конструктивно,
в том смысле, что дает алгоритм разложения произвольной переста­
новки в произведение независимых циклов. Разберем пример, взяв
в качестве а перестановку
123456789
^ "237684159
Тогда сг(1) = 2, а{2) = 3, сг(3) = 7 и а(7) = 1. Получили первый
цикл:
ai = (1,2,3,7).
Следующий элемент, который мы должны рассмотреть — это 4,
поскольку это минимальный элемент множества { 1 , . . . , 9}, который
неподвижен при действии ai, сг(4) = 6, (7(6) = 4. Поэтому сг2 = (4,6).
Продолжая процесс, получаем аз = (5,8) и сг4 = (9), Следовательно,
а = (1,2,3,7)(4,6)(5,8)(9) = (1,2,3,7)(4,6)(5,8).
л.5. Операции


А.5. Операции
в математике встречается большое количество бинарных опера­
ций: сложение и умножение чисел, композиция функций, сложение и
умножение матриц, умножение перестановок, и т. д,, всего и не вспо­
мнишь сразу, поскольку имя таким операциям — легион. Бинарные
операции имеют много обш;его, но в чем-то и отличаются друг от
друга. Например, для веп];ественных чисел х иу справедливо тожде­
ство: х-у = у-х^но матрицы 2 х 2 с веш;ественными коэффициентами
этим свойством не обладают, т. е. для обш;их матриц А и В выпол­
нено обратное: АВ^ВА. Для изучения обш;их и индивидуальных
свойств бинарных операций вводятся определенные понятия, кото­
рые мы приведем после этого абзаца. Опираясь на эти понятия, мы
докажем некоторые полезные свойства операций. Таким образом,
абстрактные свойства помогут нам одним рассуждением доказать
большое число конкретных свойств.

Определение А. 18. Бинарной операцией называется любая функ­
ция f : Ах А • А.
Так, например, если Л = М, то такой функцией может служить
сумма: f{x^ у) — хЛ-у. Однако обозначать операцию f{x^ у) очень не­
удобно. Поэтому символ функции заменяется подходяш;им символом
операции, который ставится между аргументами:

х-\-у, ХУ,
Х'У,
хоу^ хоу,
xQy,
хУу, Xicy.
X Ау,

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

Определение А. 19. Говорят, что операция «о» ассоциативна^
если для любых элементов х^ у и z выполнено тождество:

(хоу) оZ = хо{уоz).

Все упомянутые выше конкретные операции ассоциативны. Су-
^Значок, стоящий в качестве операции в определениях, обозначает любую би­
нарную операцию. При этом не утверждается, что конкретная операция обязана
обладать соответствующим свойством. — Прим. перев.
Прилоэюение А. Основная математическая терминология

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

Определение А.20. Операция «V» называется коммутативной^
если для любой пары х и у
xW у = уУ X.

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

Определение А.21. Говорят, что операция «•» обладает единицей
(единичным или нейтральным элементом), если существует такой
элемент е, что для любого х справедливы равенства:
е - X = X ' в = X.


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

Лемма А.22. Если для операции «•» существует единица, то она
только одна.
Доказательство. Предположим, что существует два единичных
элемента: е и е\ Тогда е-е' = е^ (поскольку е — единичный элемент).
С другой стороны, е- е' — е^ ибо е' — тоже единица. Значит,
е' = е ' е' = е^

откуда е — е',
Как правило, используя знак «+» для обозначения операции, мы
называем единичный элемент нулем и обозначаем О, а говоря об
умножении, т.е. операции «•,», единичный элемент упоминается как
единица и обозначается 1 или е.
А,5. Операции

Определение А.23. Пусть «+» — бинарная операция на множе­
стве Л, обладающая нейтральным элементом О, а гг — элемент из А.
Обратным^ или противополоэюным^ элементом к х называется та­
кой у Е А^ что
х-{-у = у-\-х — 0.

При аддитивном обозначении операции, т. е. при использовании
знака «+», противоположный элемент к х обозначается —ж, а при
мультипликативном — х˜^.
Каждое вещественное число обладает противоположным по сло­
жению. Любое ненулевое вещественное число обладает мультипли­
кативным обратным. Каждой из перестановок можно сопоставить
обратную ей относительно умножения перестановок. Однако только
квадратные матрицы с ненулевым определителем имеют обратную
матрицу относительно умножения.
Следующий результат говорит о том, что у любого элемента
существует не более одного обратного относительно ассоциативной
операции.

Лемма А.24. Пусть на множестве А задана ассоциативная опера­
ция с единицей е. Если х Е А обладает обратным элементом отно­
сительно этой операции, то только одним.
Доказательство. Предположим, что найдется еще один обратный
к X элемент у\ Тогда
у=:уе = у{ху') = {ух)у' = еу' = у\ •
Обратите внимание на то, как в доказательстве использована
ассоциативность операции.
С этого момента будем считать, что все используемые нами опе­
рации ассоциативны. Введем обозначения для многократного по­
вторения операций. В случае аддитивной и мультипликативной опе­
раций приняты обозначения
х-\-х-\---- + х = п-х = пх. X • X • • • X = х^. где п G N.
-v^
п п
Следующее утверждение можно доказать методом математиче­
ской индукции.

Лемма А.25. (Правила действия со степенями) Для любой
ассоциативной операции выполнены свойства
Прилоэюение А. Основная математическая т,ерминология

Если операция обладает единицей, то эти правила можно про­
должить на любые целые показатели, определив (—п) = п • {—х) и

Следующая лемма очевидна, но применяя ее, неопытные «мате­
матики» часто совершают ошибки, поскольку она противоречит ин­
туиции. Чтобы лучше ее усвоить, представьте, что работаете с ма­
трицами.

Лемма А.26. Пусть на множестве G задана ассоциативная опера­
ция с единицей, а. х и у — элементы в G, обладающие обратными.
Тогда
(1) ( x - i ) - i - x ,
(2) (ху)-^ =у-^х-К
Доказательство. Для проверки первого равенства достаточно
осознать, что х и х˜^ взаимно обратны: х˜^ • х — е = х - х˜^, Вто­
рое равенство проверяется непосредственным вычислением с уче­
том единственности обратного:
{х -у) • {у˜^ • х˜^) = X ' {у • у˜^) • х˜^ — X • е - х˜^ = х • х˜^ — е. •

Приведем небольшой словарик соответствий понятий в аддитив­
ной и мультипликативной записи.
1 Сложение Умножение
ху
х^-у
1 или е
0
—X
ж"
п •X



А.6. Группы

Определение А.27. Группой называется множество G с бинарной
операцией, обладающей следуюп];ими свойствами:
- ассоциативность;
- суп1;ествование единицы;
- каждый элемент из G обладает обратным.

Обратите внимание на то, что в определении группы мы не го­
ворили о замкнутости операции, т. е. о том, что результат операции
над любыми элементами группы принадлежит группе. Это свойство
А.6. Группы

вытекает непосредственно из определения самой операции. В случае
коммутативной групповой операции говорят о коммутативных, или
абелевых, группах.
В следующем списке представлены группы. В качестве упраж­
нения мы предлагаем читателю в каждом случае выявить единицу,
обратный элемент к каждому элементу группы и выяснить, какие
из этих групп абелевы.
- Целые числа Z по сложению: Z"^.
- Рациональные числа Q по сложению: Q"^.
- Вещественные числа Ш по сложению: М"^.
- Комплексные числа С по сложению: С"^.
- Рациональные числа Q \ {0} без нуля по умножению: Q*.
- Вещественные числа Ш \ {0} без нуля по умножению: М*.
- Комплексные числа С \ {0} без нуля по умножению: С*.
- Множество векторов с п целыми, рациональными, веществен­
ными, комплексными координатами с операцией сложения век­
торов.
- Множество п X т матриц с целыми, рациональными, веще­
ственными, комплексными элементами с операцией сложения

<< Предыдущая

стр. 71
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>