Алгебра билет 13

Подстановки n-ой степени, запись. Умножение подстановок, умножение подстановки на транспозицию.

Опр. Подстановкой n-степени называют всякое биективное отображение n-элементного мн-ва на себя, т. е. а: Аà (биекция)A.

Биективность а означает: 1) если i, j принадлежат А и I не равно j, то а (i) не равно а (j) – разные переводятся в разные. 2) для любого j из А найдется i из А: а (i)= j (если мы возьмем какой-нибудь j из А, то в него из А обязательно какой-нибудь переведем).

Мн-во всех подстановок n-степени обозначают через Sn.

Методом мат. индукции можно показать, что всего подстановок n-степени будет n!

Важна запись подстановки n-степени. Если эта запись удобна, то она помогает изучать сами подстановки. Поскольку А – это конечное мн-ва, то а из Sn можно записать, указав для каждого i из А его образ а (i). Сделать это можно, например, в виде 2-х строк, выписав в 1-ой строке в любом порядке все элементы из А, а во 2-ой под каждым из них записать его образ относительно а.

Расшифруем: и в верхней, и в нижней строках записи (1) выписаны все эл-ты из А (и в верхней, и в нижней строкахнет одинаковых).

Запись (1) полная запись подстановки а. Полная запись неоднозначна. Если в верхней строке записи(1) эл-ты из А (числа от 1 по n) записаны в натуральном порядке, то такая полная запись называется канонической.

(2)

Каноническая – обязательно полная, но полная не всегда каноническая.

Выделяется тождественная подстановка id.

Задается

Если а, b принадлежат Sn, произведением а*b – называют их композицию (последовательные применения подстановок а и b в упраздненном порядке.

По опр. (3) легко записать полную запись а*b

Св-ва умножения подстановок.

Умножение подстановок ассоциативно.

Опр. Подстановка b называется обратной для подстановки а, если

Правило: Чтобы получить запись а в -1, нужно в любой полной записи поменять местами 1-ю и 2-ю строки.

ОПР. Подстановка n-степени, меняющая местами 2 числа i и j из А, а все остальные оставляющая на месте, называется транспозицией. tij

Опр. Транспозиции tij можно формализовать так:

Выясним правило умножения подстановки на транспозицию.

Анализируя полные записи а и tij* а, мы получаем правило: Чтобы умножить подстановку а слева на tij слева, нужно в полной записи а по 2-ой строке поменять местами числа, стоящие под i и j.

Полная подстановка а в- 1 получается из полной записи подстановкой а сменой записи 1 и 2 строк. Предлоги под и над меняются местами.

Обратимся к формуле (13).

Умножить а в- 1 слева на tij это значит нужно в полной записи подстановки а в- 1 поменять местами в полной записи подстановки а числа i и j.

Если вернуться к началу записи (13), сказанное означает: Чтобы умножить подстановку а справа, нужно в ее полной записи поменять местами числа, чстоящие НАД i и j.

Следствие

Из правил умножения подстановки на транспозицию (справа и слева) следует вывод: Любую подстановку можно представить в виду произведения нескольких транспозиций.

Обоснование (схематично):

Формула (14) искомый ответ.