Преобразования и подстановки

Множество всех преобразований множества X обозначим П (Х). Из определения произведения функций следует, что для любых преобразований g, h е П (Х) определено произведение: gh (x) = h (g (x)) для любого ieIB частности, определено возведение в степень преобразований: g° = е, g¹ = ggⁱ~^l, t= 1, 2,… Следовательно, П (Х) образует моноид, где единица есть тождественная функция. Для и-множества X моноид (обозначаемый П") имеет порядок п^п и называется симметрической полугруппой преобразований степени п.

Пусть g (X) = {g (jtr): х е X} — образ множества X относительно преобразования g. Числа |g'(X)| и |х| - Ig (X) | называются соответственно рангом преобразования g и дефектом преобразования g, обозначаются rang (g) и def (g).

Биективное преобразование n-мпожества X называется подстановкой на X, п — степенью подстановки. Ранг подстановки степени п равен п, дефект равен 0.

Утверждение 4.3. Для любых g, h е П" верно: rang (g/z) < min{rang (g), rang (/?)}.

4 Пусть Y с N_n. Из однозначности преобразования g множества N_n следует, что lg (E)l<|E|. Тогда gh (N_n) | = | h (g (N")) | < lg (iV") |, т. е. rang (gA) <

< rang (g').

Пусть Y_tQY₂Q JV", тогда I /?(F,) I < I h (Y₂) I. Отсюда gh (N") I = h (g (N_n)) <

< I h (i_n) |, т. е. rang (g'/?) < rang(h). ?

Следствие. Произведение gj… g_f преобразований^{-множества} X есть подстановка g, — подстановка множества X, i = 1,…, t, где t > 1. О Теорема 4.2. Преобразование g е П" биективно инъективно (сюръективно).

М Пусть g инъективно; покажем, что g сюръективно, т. е. для любого х е X найдется х' из X такой, что g (x^/) = х. Обозначим {g*(x), k = 0, 1,…} - последовательность элементов множества X. В силу конечности множества X в этой последовательности неизбежны повторения, т. е. g^m(x) =gⁿ(x), где т > п> 0. Если п > 0, то отсюда в соответствии с инъективностью g имеем g^w_I(x) = g^I~¹(x). Повторив эти рассуждения еще п — 1 раз, получаем g^m~ⁿ(x) = g°(x) = х. Значит, равенство g (xf) = х выполнено при х? = gⁿ~ⁿ~^x{x).

Пусть преобразование g множества X сюръективно. Тогда для каждого образа найдется ровно один прообраз, так как мощности множеств образов и прообразов конечны и равны. Следовательно, преобразование g биективно. ?

Множество всех подстановок множества X, обозначаемое S (X), образует группу. Для я-множества X группа (обозначаемая S_n) имеет порядок п и называется симметрической группой подстановок степени п. Группа S_n есть максимальная подгруппа моноида П".

В параграфе 3.5 показано, что граф T (g) подстановки g состоит из независимых циклов без подходов. Значит, в соответствии с определением произведения преобразований для возведения в степень t подстановки g требуется возвести в степень t все циклы. При возведении в степень t цикла С = (х_и …, xj) длины / получаются d независимых циклов С₀'(?)> •••> C’d-(О длины / / d, где d = (t, l) и Cj'(t) = (gJ (x_{), &^+d(x_x),gJ^+,~^d(x_{))J = 0 d- 1,.

g°=e.

Группа S_n изоморфна группе всех подстановочных матриц порядка п, где квадратная матрица над полем {0, 1} называется подстановочной, если в каждой ее строке и каждом ее столбце имеется единственный элемент, равный 1, а остальные элементы равны 0.

Подстановки используются в криптографических приложениях для шифрования данных и как элементы при построении криптографических схем. Каноническое табличное задание подстановки g е S_n имеет вид.

где (i_t>…, i_n) — перестановка чисел (1, …, п). Каноническая таблица обратной подстановки g~^x получается после перестановки в таблице g верхней и нижней строк и переупорядочения вертикальных пар по элементам верхней строки.

Подгруппы группы S_n называют группами подстановок.

Укажем некоторые классы подстановок из S_n> возникающие в различных приложениях. Обозначим Г_л (Г_п) подстановку левого (правого) циклического сдвига:

Подстановка g называется инволюцией, если g~^{ = g. Отсюда g — инволюция g² = е. Инволюция g на X называется транспозицией элементов i, j при i ф], если g (i) = j, g (j) = i, а остальные элементы неподвижны относительно g.

Теорема 4.3 [2]. Каждая подстановка разлагается в произведение транспозиций, где четность длины (числа транспозиций) любого разложения одинакова. О.

Подстановка четная (нечетная), если длина разложения четная (нечетная). Множество А_п всех четных подстановок из S_n есть подгруппа группы S_n порядка п / 2, называемая знакопеременной группой подстановок степени п.