Отправляет email-рассылки с помощью сервиса Sendsay

Система компьютерной алгебры GAP

Подписаться Бесплатная «Серебряная» новостная рассылка . Временно не выходит ,возобновит выход - нет информации Подписчиков 783 RSS
←   Декабрь 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://www.gap-system.org/ukrgap/
Открыта: 05-02-2002

Автор
Александр Борисович Коновалов

Статистика

783 подписчиков
0 за неделю
←   Все выпуски   →

Система компьютерной алгебры GAP - #44, 06-12-04 (Подстановки в GAP)


Информационный Канал Subscribe.Ru
Рассылка "Система компьютерной алгебры GAP"
(http://subscribe.ru/catalog/science.exact.gap/)
ведущий рассылки А.Б.Коновалов, a_konovalov@hotmail.com
выпуск 44 от 06 декабря 2004 г.
Подстановки в системе GAP
На сайте Украинской группы пользователей GAP (http://ukrgap.exponenta.ru/) в разделе "Изучаем алгебру с GAP" помещен новый материал по теме "Подстановки". Предлагаем Вам ознакомиться с ним в данном выпуске рассылки.
Перед тем, как приступить к рассказу о подстановках в системе GAP, приведем необходимые теоретические сведения. Итак, пусть M={1,2,3,...,n}. Взаимно однозначное отображение множества M первых n натуральных чисел на себя называется подстановкой n-й степени. Подстановку n-й степени s можно записать в виде матрицы из двух строк и n столбцов, в которой соответствующий элемент первой строки отображается в находящийся под ним элемент второй строки (очевидно, что каждая строка такой матрицы является перестановкой из n элементов). Если x - элемент множества M, и s - подстановка, то образ элемента x под действием подстановки s обозначается s(x). Тогда умножение подстановок определяется как композиция отображений:
(s1*s2)(x) = s1(s2(x)).

Далее, подстановка s называется циклом длины k, если s(a1)=a2, s(a2)=a3, ... s(ai)=ai+1 и s(ak)=a1 (разумеется, все элементы, входящие в один цикл, должны быть попарно различны). Для записи циклов используется более компактное обозначение: (a1 a2 a3 ... ak). Циклы называются независимыми, если они не содержат общих элементов. Известно, что каждую подстановку можно разложить в произведение независимых циклов. Например, подстановка (1,2,3)(4,5) переводит 1 в 2, 2 в 3, 3 в 1, 4 в 5 и 5 - в 4. Цикл длины два называется транспозицией. Каждая подстановка разлагается в произведение конечного числа транспозиций, количество которых определяет четность подстановки.

Подстановки являются стандартными объектами в системе GAP. При этом ввод и вывод подстановок производится в виде произведения независимых циклов. Максимальным числом, которое может входить в запись подстановки, является 228-1. При попытке ввести подстановку, циклы которой не являются независимыми или не являются циклами вообще, выдается сообщение об ошибке.

Примеры правильных и неправильных вариантов задания подстановок:

gap> a:=(1,2,3)(4,5); # правильное задание подстановки
(1,2,3)(4,5)
gap> a:=(1,2,3,1)(3,4,5); # первый множитель - не цикл
Permutation: cycles must be disjoint and duplicate-free
gap> a:=(1,2,3)(3,4,5); # циклы не являются независимыми
Permutation: cycles must be disjoint and duplicate-free
gap> b:=(1,2,3)*(3,4,5); # так нужно поступать, если циклы не независимы
(1,2,4,5,3) # (в этом случае выполняется их умножение)
gap> e:=(); # так задается тождественная подстановка
()

Следует обратить внимание на то, что в GAP умножение подстановок выполняется слева направо, а не справа налево, как было указано в приведенных выше кратких теоретических сведениях. Это связано с тем, что для образа точки i под действием подстановки p можно использовать как обозначение p(i), так и обозначение ip. В GAP принят за основу второй вариант записи (поскольку запись p(i) интерпретировалась бы как обращение к функции p с аргументом i), и ip записывается как i^p. Тогда выполняется соотношение i^(p1*p2)=(i^p1)^p2, соответствующее правилу (p1*p2)(i) = p1(p2(i)).

Если i^p не совпадает с i, то мы говорим, что i перемещается подстановкой p. В противном случае точка i называется неподвижной (или фиксированной) точкой относительно подстановки p. Прообраз точки i относительно подстановки p записывается как i/p, что позволяет быстро определить его без непосредственного вычисления подстановки, обратной к p:

gap> 1^a;
2
gap> 3^a;
1
gap> 3/a;
2
gap> 3/a=3^(a^-1); # проверим, что оба способа дают одинаковый результат
true

Приведем еще несколько примеров действий над подстановками:

gap> c:=(1,2,4)(7,3,6)(8,9); # зададим подстановку, состоящую из трех циклов
(1,2,4)(3,6,7)(8,9)
gap> b*c; # и умножим ее на b
(1,4,5,6,7,3,2)(8,9)
gap> (1,2,3)^-1; # так находят обратную подстановку
(1,3,2)
gap> (1,2,3)^(1,2); # а так - подстановку, сопряженную с данной
(1,3,2)
gap> (1,2,3)^(1,2)=(1,2)^1 * (1,2,3) * (1,2); # проверим это, вычислив сопряженную подстановку
true
gap> b/c; # так можно быстро вычислить b*c^-1
(3,4,5,7,6)(8,9)
gap> b*c^-1; # проверим это, сравнив два последних результата
(3,4,5,7,6)(8,9)

Полезными также являются функция LeftQuotient(elm1,elm2), возвращающая произведение elm1^(-1)*elm2 (для подстановок она возвращает результат быстрее, чем непосредственное нахождение подстановки, обратной к первой подстановки и последующее умножение результата на вторую подстановку), а также функция Comm(elm1,elm2), возвращающая коммутатор elm1 и elm2, который по определению равен произведению elm1^(-1) * elm2^(-1) * elm1 * elm2 :

gap> a:= (1,3)(4,6);; b:= (1,6,5,4,3,2);;
 gap> LeftQuotient( a, b );
(1,2)(3,6)(4,5)
gap> Comm( a, b );
(1,5,3)(2,6,4)

Как правило, для удобства в наименованиях функций GAP, предназначенных для работы с подстановками, слово Permutation сокращается до Perm. Например, функция IsPerm проверяет, является ли объект подстановкой:

gap> IsPerm( (1,3,4,6) );
true
gap> IsPerm( [1,3,4,6] );
false

Подстановки в GAP не принадлежат к какой-либо специфической группе подстановок. Это означает, что Вы можете работать с ними, не определяя группу подстановок, которой они принадлежат. Подстановки считаются равными, если они перемещают одно и то же множество точек, и образы соответствующих точек совпадают:

gap> (1,2,3)=(2,3,1);
true
gap> (1,2,3)(10)=(2,3,1)(11);
true
gap> (1,2,3)=(1,3,2);
false

Для перестановки элементов списка в соответствии с некоторой подстановкой используется функция Permuted:

gap> Permuted( ["a","b","c","d"], (1,4)(2,3) );
[ "d", "c", "b", "a" ]

Для изучения свойств множества точек, перемещаемых подстановкой или набором подстановок, используются функции SmallestMovedPoint, LargestMovedPoint, MovedPoints и NrMovedPoints. Аргументом этих функций может быть одна подстановка, список подстановок, или, например, группа подстановок или ее класс сопряженных элементов. Действие этих функций описывается в следующей таблице.


 Аргумент - подстановка
 Аргумент - набор подстановок
SmallestMovedPoint
 Возвращает наименьшее положительное число, которое перемещается данной подстановкой, если такое число существует, и infinity, если подстановка является тождественной
 Возвращает наименьшее значение из всех SmallestMovedPoint для элементов из данного набора подстановок, и infinity, если набор является пустым
LargestMovedPoint
 Возвращает наибольшее положительное число, которое перемещается данной подстановкой, если такое число существует, и 0, если подстановка является тождественной
 Возвращает наибольшее значение из всех LargestMovedPoint для элементов из данного набора подстановок, и 0, если набор является пустым
MovedPoints
 Возвращает множество положительных чисел, которые перемещаются данной подстановкой.
 Возвращает множество положительных чисел, которые перемещаются хотя бы одной подстановкой из данного набора
NrMovedPoints
 Возвращает количество положительных чисел, которые перемещаются данной подстановкой
 Возвращает количество положительных чисел, которые перемещаются хотя бы одной подстановкой из данного набора

Пример:

gap> SmallestMovedPointPerm((4,5,6)(7,2,8));
2
gap> LargestMovedPointPerm((4,5,6)(7,2,8));
8
gap> NrMovedPointsPerm((4,5,6)(7,2,8));
6
gap> MovedPoints([(2,3,4),(7,6,3),(5,47)]);
[ 2, 3, 4, 5, 6, 7, 47 ]
gap> NrMovedPoints([(2,3,4),(7,6,3),(5,47)]);
7
gap> SmallestMovedPoint([(2,3,4),(7,6,3),(5,47)]);
2
gap> LargestMovedPoint([(2,3,4),(7,6,3),(5,47)]);
47
gap> LargestMovedPoint([()]);
0
gap> SmallestMovedPoint(());
infinity

Функция SignPerm возвращает знак подстановки, который равен (-1)k, где k - количество циклов четной длины в разложении подстановки в произведение независимых циклов (цикл четной длины представляется в виде произведения нечетного числа транспозиций, а нечетной длины - в виде четного числа транспозиций). Таким образом, знак подстановки равен 1, если она четная, и -1, если она нечетная. Знак подстановки является гомоморфизмом из симметрической группы подстановой в мультипликативную группу { +1, -1 }, ядром которого является знакопеременная группа.

gap> SignPerm((1,2,3)(4,5));
-1
Количество циклов каждой длины в разложении подстановки возвращает функция CycleStructurePerm. Ее результатом является список, i-й элемент которого содержит количество циклов длины i+1. Если подстановка не содержит циклов длины i+1, то i-й элемент списка не определен. Циклы длины 1 игнорируются. Например:

gap> CycleStructurePerm( (1,8)(2,4)(3,5,6));
[ 2, 1 ]
gap> CycleStructurePerm((1,2,3)(4,5,9,7,8));
[ , 1,, 1 ]

Кроме задания подстановок в виде произведения независимых циклов, существуют различные способы конвертации подстановок в списки и наоборот. Функция ListPerm(perm) возвращает список, который содержит образы положительных чисел под действием подстановки perm, т.е. list[i] = i^perm, где i изменяется от 1 до LargestMovedPoint(perm). Иными словами, для подстановки, заданной в виде произведения циклов, она возвращает нижнюю строку из ее представления в виде двустрочной матрицы.

Обратной к этой функции является PermList(list), которая возвращает подстановку, которая действует в соответствии со списком list. Иными словами, i^perm = list[i], если i находится в границах от 1 до длины списка list, и i^perm = i, если i больше его длины. Эта функция возвращает fail, если заданный список не определяет подстановку (например, не является плотным, содержит одинаковые числа, содежит целое число не из интервала [ 1 .. Length( list ) ] или содержит элемент, который не является целым числом.

Если src и dst - два списка положительных чисел одинаковой длины, и каждый из них не содержит одинаковых элементов, то функция MappingPermListList ( src, dst ) возвращает подстановку perm, такую что src[i]^perm = dst[i]. При этом perm оставляет на месте все числа, превышающие максимальное из чисел, входящих в списки src и dst.

Функция RestrictedPerm( perm, list ) возвращает новую подстановку, которая является ограничением подстановки perm на список list, т.е. действует на элементы списка list таким же образом, как и исходная подстановка perm, и фиксирует все точки, не входящие в список list. Список list должен быть замкнут относительно действия подстановки perm, т.е. вместе с каждым элементом i содержать его образ i^perm.

Пример:

gap> ListPerm((3,4,5));
[ 1, 2, 4, 5, 3 ]
gap> PermList([1,2,4,5,3]);
(3,4,5)
gap> MappingPermListList([2,5,1,6],[7,12,8,2]);
(1,8,5,12,11,10,9,6,2,7,4,3)
gap> RestrictedPerm((1,2)(3,4),[3..5]);
(3,4)

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

gap> s8 := Group( (1,2), (1,2,3,4,5,6,7,8) );
Group( [ (1,2), (1,2,3,4,5,6,7,8) ] )

Как известно, это - симметрическая группа подстановок 8-й степени. Теперь вычислим ее коммутант (который является знакопеременной группой подстановок 8-й степени), найдем его порядок и установим, будет ли он коммутативным:

gap> a8 := DerivedSubgroup( s8 );
Group([(1,2,3),(2,3,4),(2,4)(3,5),(2,6,4),(2,4)(5,7),
(2,8,6,4)(3,5)])
gap> Size( a8 ); IsAbelian( a8 );
20160
false

Кроме этого, в системе имеются стандартные функции для задания симметрической и знакопеременной групп:

gap> S3:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> AsList(S3);
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
gap> A4:=AlternatingGroup(4);
Alt( [ 1 .. 4 ] )
gap> AsList(A4);
[ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2), (1,3,4),
(1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]

С уважением,
Александр Борисович Коновалов
председатель Украинской группы пользователей GAP (http://ukrgap.exponenta.ru/)
доцент кафедры алгебры и геометрии Запорожского государственного университета
E-mail: a_konovalov (at) hotmail.com
http://subscribe.ru/
http://subscribe.ru/feedback/		 Подписан адрес:
Код этой рассылки: science.exact.gap		 Отписаться
В избранное