Группы преобразований

Множества и отображения

Пусть X и Y --- произвольные множества. Если каждому элементу x множества X поставлен в соответствие определенный элемент y=f(x) множества Y, то говорят, что определено отображение f из X в Y (пишут f: X Y).

Рис. 4

Если имеются три множества X, Y, Z и два отображения f: X Y и g: Y Z, то определено "сквозное" отображение g f: X Z, которое переводит элемент x множества X в элемент z=g(f(x)) множества Z (рис. 4). Отображение g f называется композицией или произведением отображений f и g.

Рассмотрим тождественное отображение e_X: XX, которое "оставляет на месте" любой элемент xX, т. е. e_X(x)=x для любого xX, и аналогичное отображение e_Y: YY. Отображение f: XY называется обратимым (взаимно однозначным соответствием), если существует такое отображение g Y X, что

g f=e_X, f g=e_Y,

x X

y Y

Рис. 5

Такое отображение g называется обратным отображению f и обозначается f ^-1 (рис. 5).

Преобразования и их свойства

Преобразованием некоторого множества X называется обратимое отображение множества X на себя --- f: XX.

Если f и g --- два преобразования множества X, то их произведение g f также является преобразованием множества X. (Действительно, отображение g f переводит множество X в множество X, а обратным ему является отображение f^{- -1} g^-1.) Таким образом, на совокупности всех преобразований множества X определена операция умножения .

Конечно, умножение преобразований устроено не так просто, как умножение действительных чисел. Например, для любых чисел a и b выполнено равенство a*b=b*a. Однако далеко не всегда f g=g f.

Рис. 6

Рассмотрим такой пример. Пусть множество X --- это плоскость, преобразование f --- поворот с центром в точке O на некоторый угол, g --- симметрия относительно прямой l (рис. 6). Преобразование f g переводит точку A в точку A'=f(g(A)), а преобразование g f --- в точку A''=g(f(A)) (в первом случае мы сначала отразили, потом повернули, во втором --- сначала повернули, потом отразили). А раз точки (f g)(A) и (g f)(A) не совпадают, то f g и g f --- разные преобразования.

Но умножение преобразований обладает и многими хорошими свойствами, которые сближают его с умножением чисел. Мы знаем, например, что (a*b)*c=a*(b*c) для любых чисел a, b и c, т. е. что произведение трех чисел не зависит от того, в каком порядке выполнять операции умножения. Такое же свойство выполняется и для преобразований: (f g) h=f (g h). Докажем это. По определению умножения преобразований, для любого элемента x X

((f g) h)(x)=(f g)(h(x))=f(g(h(x)),
(f(g h))(x)=f((g h)(x))=f(g(h(x))).

(f g) h

f (g h)

x X

Среди всех чисел выделяется число 1, обладающее следующим свойством: a*1=a для любого числа a. В множестве преобразований роль единицы выполняет тождественное преобразование e=e_X: очевидно, что f e=f=e f для любого преобразования f. Каждому числу a0 соответствует число a^-1=1/a, a*a^-1=1; говорят, что числа a и a^-1 взаимно обратны. Каждому преобразованию f также соответствует обратное преобразование, т. е. такое f ^-1, что f f ^-1=f ^-1 f=e.

Группы преобразований и их инварианты

Обозначим через некоторую совокупность интересующих нас свойств множества X, а через G --- совокупность всех преобразований множества X, сохраняющих эти свойства .

Пример 1. Если X --- это плоскость, --- расстояния между точками плоскости, то G состоит из движений плоскости: поворотов, параллельных переносов, симметрий, а также их всевозможных произведений (композиций).

Пример 2. (К задаче 3.) Пусть X --- плоскость, а в качестве возьмем расстояния между точками и данный правильный n-угольник A₁A₂... A_n. Тогда G --- совокупность движений плоскости, оставляющих на месте этот n-угольник, --- состоит из n поворотов (включая поворот на нулевой угол, т. е. тождественное преобразование) и n осевых симметрий. (G называется группой самосовмещений правильного n-угольника.)

Пример 3. (К задаче 4.) Пусть X={x,y,z} --- множество из трех элементов --- формальных символов, --- вид системы уравнений в условии задачи. Тогда, как мы уже выяснили, G --- совокупность преобразований, сохраняющих вид системы, --- состоит из перестановок элементов множества X.

Пример 4. Заменим систему уравнений в задаче 4 на такую:

xy

Отметим некоторые общие свойства совокупности G.

1^o. Если g₁ G и g₂ G, то g₁ g₂ G.

2^o. e G.

3^o. Если g G, то g ^-1 G.

Дадим теперь важное определение.

Группой преобразований называется совокупность G преобразований множества X, удовлетворяющая условиям 1^o--3^o.

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

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

Задача. На 44 деревьях, посаженных по окружности, сидят 44 веселых чижа, по одному на каждом дереве. Время от времени один из чижей перелетает на соседнее дерево и одновременно с ним какой-нибудь другой чиж перелетает на соседнее дерево в противоположном направлении. Могут ли все чижи собраться на одном дереве?

Решение. Занумеруем деревья по порядку числами от 0 до 43. В дальнейшем нам будет удобно считать, что это не целые числа, а остатки от деления на 44 или вычеты по модулю 44 (так, например, 440(mod 44), 43+54(mod 44), 1-342(mod 44)). . Каждому вычету i (i=0, ..., 43) сопоставим число n_i, равное количеству чижей на i-м дереве (числа n_i тоже суть вычеты по модулю 44). В результате мы получаем функцию f(i)=n_i на множестве вычетов со значениями в множестве вычетов. Множество всех таких функций обозначим через X.

Например, когда все чижи сидят на одном дереве (с номером i), получается функция

f₀(k)=

_i(k)=

: XX

(g_ijf)(k)=f(k)+_i+1(k)-_i(k)-_j(k)+_j-1(k).

Преобразования g_ij --- это элементарные преобразования. Всевозможные композиции элементарных преобразований образуют некоторую группу G преобразований множества X.

Контрольные вопросы: Что такое g_ij^-1? Что такое (g_ijg_kl)^-1? Как действует преобразование g_i,j-1 g_i-1,j?

А теперь вычислим для каждой функции f X число (а точнее вычет) S(f):
S(f)=0*f(0)+1*f(1)+2*f(2)+...+43*f(43).
Легко видеть, что S(f) --- инвариант группы G. Действительно, любое элементарное преобразование функции f не меняет S(f):

g G

Осталось заметить, что

S(f_нач)=0+1+2+...+43=(43*44)/2=94622 (mod 44),
S(f₀)0 (mod 44).

Как правило, задача типа: " Можно ли сделать <что-нибудь>?" --- либо задача на построение примера, если это сделать можно, либо задача на нахождение инвариантов, которые показывают, что это сделать нельзя.

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

Следующий раздел