Подстановки, перестановки

Разбить на страницы

Показывать лекцию целиком

Подстановки, перестановки

Теорема 5.0.4. Множество S(U) всех биекций$$f: U\to U$$ с операцией произведения (композиции) отображений gf для $$U\xrightarrow{f} U \xrightarrow{g} U$$, $$f,g\in S(U)$$, обладает следующими свойствами:

операция произведения ассоциативна ( h(gf)=(hg)f для всех $$f,g,h\in S(U)$$ ),

нейтральным элементом для этой операции является тождественное отображение 1_U ( 1_Uf=f=f1_U для всех $$f\in S(U)$$ ),

для всякой биекции $$f: U\to U$$ существует обратный элемент - биекция g=f^-1 ( fg=1_U=gf ).

(Другими словами, S(U) - группа относительно операции произведения отображений; S(U) - подгруппа моноида T(U): $$S(U)\subseteq \mT(U)$$.)

Доказательство. следует из теоремы 1.6.4 и леммы 1.8.4.

Биекции $$f: U\to U$$ множества U часто называются подстановками . Наиболее важный для нас случай U={1,2,...,n}, в этом случае группу S_n = S({1,2,...,n}) называют группой подстановок множества {1,2,...,n} из n элементов (иногда называемой симметрической группой).

Запись подстановок. Перестановки

Если $$f\in S_n$$ - подстановка, то рассмотрим ее каноническую запись$$\begin{pmatrix} 1 2 ... n\\ f(1) f(2) ... f(n) \end{pmatrix}.$$ В нижней строчке (f(1), f(2),..., f(n)), поскольку f - биекция, встречаются все элементы i, $$1 \leq i \leq n$$, при этом только по одному разу. Такие строчки элементов (i₁,...,i_n), $$1 \leq i_j \leq n$$, где каждый элемент i_j, $$1 \leq i_j \leq n$$, встречается один и только один раз, называются перестановками элементов 1,2,...,n .

Лемма 5.1.1. Число всех перестановок (i₁,...,i_n) из n элементов равно $$n!=1\cdot 2\cdot ...\cdot n$$.

Доказательство. Для i₁ имеем n возможностей. При выбранном i₁ для i₂ имеем (n-1) возможность. Таким образом, число различных перестановок равно $$n\cdot (n-1)\cdot ...\cdot 2\cdot 1 = n$$!.

Лемма 5.1.2. Число различных подстановок множества {1,2,...,n} равно n! (т. е. | S_n|=n!).

Доказательство. Для $$f\in S_n$$ рассмотрим каноническую запись$$f=\begin{pmatrix} 1 2 ... n\\ f(1) f(2) ... f(n) \end{pmatrix}.$$ Таким образом, различных подстановок столько же, сколько различных перестановок n элементов, т. е. n!.

Во многих случаях удобно рассматривать записи подстановки $$f\in S_n$$, располагая в верхней строчке произвольную перестановку (i₁,i₂,...,i_n):$$f = \begin{pmatrix} i_1 i_2 ... i_n\\ f(i_1) f(i_2) ... f(i_n) \end{pmatrix}.$$ Каждый столбец этой таблицы имеет вид$$\begin{pmatrix} i\\ f(i) \end{pmatrix}.$$

Пример 5.1.3

Для тождественной подстановки в S₂ имеем$$f = \begin{pmatrix} 1 2\\ 1 2 \end{pmatrix} = \begin{pmatrix} 2 1\\ 2 1 \end{pmatrix}.$$ Для биекции $$f: \{1,2\}\to \{1,2\}$$, f(1)=2, f(2)=1, имеем$$f = \begin{pmatrix} 1 2\\ 2 1 \end{pmatrix} = \begin{pmatrix} 2 1\\ 1 2 \end{pmatrix}.$$

Если$$f=\begin{pmatrix} i_1 ... i_n\\ j_1 ... j_n \end{pmatrix} \in S_n,$$ то$$f^{-1}=\begin{pmatrix} j_1 ... j_n\\ i_1 ... i_n \end{pmatrix}.$$

Так как $$(\sigma\tau)(i)=\sigma(\tau(i))$$, то$$\begin{pmatrix} 1 2 3\\ 2 1 3 \end{pmatrix} \begin{pmatrix} 1 2 3\\ 1 3 2 \end{pmatrix} = \begin{pmatrix} 1 2 3\\ 2 3 1 \end{pmatrix}.$$ В частности,$$\begin{pmatrix} i_1 i_2 ... i_n\\ j_1 j_2 ... j_n \end{pmatrix} \begin{pmatrix} 1 2 ... n\\ i_1 i_2 ... i_n \end{pmatrix} = \begin{pmatrix} 1 2 ... n\\ j_1 j_2 ... j_n \end{pmatrix}.$$

Обозначим через (i₁ i₂... i_r) цикл длины r в группе подстановок S_n: подстановку, переводящую i_k в i_k+1 для $$1 \leq k \leq r-1$$, i_r в i₁, и оставляющую все элементы из {1,2,...,n}, отличные от i₁,...,i_r, на месте. Тогда в S₃ имеем шесть подстановок:$$\begin{alignat*}{2} e= \begin{pmatrix} 1 2 3\\ 1 2 3 \end{pmatrix}; \qquad (1\quad 2) = \begin{pmatrix} 1 2 3\\ 2 1 3 \end{pmatrix}; \\ (1\quad 3) = \begin{pmatrix} 1 2 3\\ 3 2 1 \end{pmatrix}; (2\quad 3) = \begin{pmatrix} 1 2 3\\ 1 3 2 \end{pmatrix}; \\ (1\quad 2\quad 3)= \begin{pmatrix} 1 2 3\\ 2 3 1 \end{pmatrix}; (1\quad 3\quad 2)= \begin{pmatrix} 1 2 3\\ 3 1 2 \end{pmatrix}. \end{alignat*}$$ При этом в S_n для $$n \geq 3$$ имеем$$(1\quad 2)(1\quad 3) = (1\quad 3\quad 2) \neq (1\quad 2\quad 3) = (1\quad 3)(1\quad 2),$$ следовательно, группа S₃ и любая группа S_n при $$n \geq 3$$ некоммутативны. Так как S₁={e} и S₂={e, (1 2)} - коммутативные группы, то получаем, что группа S_n коммутативна тогда и только тогда, когда n=1 или n=2.

Перестановки и транспозиции

Рассмотрим перестановку двух элементов i и j, $$i\neq j$$, в перестановке (i₁,...,i_n) (все остальные элементы, отличные от i, j, остаются на своих местах). Эта процедура называется транспозицией перестановки (i₁,...,i_n).

Лемма 5.2.1.

Умножение слева (i j)f подстановки$$f = \begin{pmatrix} i_1 ... i_n\\ j_1 ... j_n \end{pmatrix}$$ на цикл (i j) длины 2 приводит к транспозиции элементов i и j в нижней строке (перестановке) (j₁,...,j_n).

Умножение справа f(i j) подстановки$$f = \begin{pmatrix} i_1 ... i_n\\ j_1 ... j_n \end{pmatrix}$$ на цикл (i j) длины 2 приводит к транспозиции элементов i и j в верхней строке (перестановке) (i₁,...,i_n).

Доказательство.

$$\begin{mult} \begin{pmatrix} ... i ... j ...\\ ... j ... i ... \end{pmatrix} \begin{pmatrix} i_1 ... i_k ... i_l ... i_n\\ j_1 ... j_k=i ... j_l=j ... j_n \end{pmatrix}={} \\ {}= \begin{pmatrix} i_1 ... i_k ... i_l ... i_n\\ j_1 ... j=j_l ... i=j_k ... j_n \end{pmatrix}. \end{mult}$$

$$\begin{mult} \begin{pmatrix} i_1 ... i_r=i ... i_s=j ... i_n\\ j_1 ... j_r ... j_s ... j_n \end{pmatrix} \begin{pmatrix} ... i ... j ...\\ ... j ... i ... \end{pmatrix}={} \\ {}= \begin{pmatrix} i_1 ... j=i_s ... i=i_r ... i_n\\ j_1 ... j_r ... j_s ... j_n \end{pmatrix}. \end{mult}$$

Лемма 5.2.2 (о списке перестановок). Все n! перестановок из n элементов {1,2,...,n} можно расположить в список, начиная с произвольной перестановки (i₁,i₂,...,i_n), так, что каждая следующая перестановка в этом списке получается из предыдущей с помощью некоторой транспозиции двух элементов.

Доказательство. Проведем индукцию по n. Начало индукции n=2, n!=2, наши списки:$$\begin{array}{@{}l@{}} (1, 2)\\ (2, 1) \end{array}\,;\quad \begin{array}{@{}l@{}} (2, 1)\\ (1, 2) \end{array}.$$

Пусть наше утверждение верно для всех k, k<n. Пользуясь этим, создадим первый блок из различных (n-1)! перестановок с i_1 на первом месте (т. е. перестановок из элементов {i₂,...,i_n} ), при этом каждая следующая перестановка получается из предыдущей с помощью транспозиции:$$\scriptstyle{(n-1)!} \left\{ \begin{array}{@{}l@{}} (i_1,i_2,...,i_n),\\ \quad \vdots\\ (i_1,...,i_2,...). \end{array} \right.$$

Совершая транспозицию i₁ и i₂ в последней перестановке первого блока и повторяя наше рассуждение, построим второй блок из различных (n-1)! перестановок с i₂ на первом месте (т. е. перестановок элементов {i₁,i₃,...,i_n} ), при этом каждая следующая перестановка получается из предыдущей применением транспозиции:$$\scriptstyle{(n-1)!} \left\{ \begin{array}{@{}l@{}} (i_2,...),\\ \quad \vdots\\ (i_2,...,i_3,...). \end{array} \right.$$

Продолжая этот процесс, получим n блоков из (n-1)! перестановок каждый, всего n! перестановок. Они все различны: в одном блоке по индуктивному предположению, в разных блоках перестановки различаются на первом месте. Таким образом, в этом списке присутствуют все n! перестановок из n элементов, при этом каждая следующая получается из предыдущей с помощью одной транспозиции.

Следствие 5.2.3. От любой перестановки (i₁,...,i_n) можно перейти к любой другой перестановке (j₁,...,j_n) с помощью конечного числа транспозиций.

Доказательство. В списке с началом (i₁,...,i_n) надо найти перестановку (j₁,...,j_n).

Следствие 5.2.4. Каждая подстановка$$\tau= \begin{pmatrix} 1 2 ... n\\ k_1 k_2 ... k_n \end{pmatrix} \in S_n$$ является произведением $$\tau = \tau_r...\tau_1$$ конечного числа циклов $$\tau_i$$ длины два (называемых также транспозициями). Таким образом, циклы длины два (транспозиции) дают одну из систем образующих группы S_n.

Доказательство. Составим список перестановок, начинающийся с перестановки (1,2,...,n), в котором каждая l -я перестановка получается из (l-1) -й транспозицией элементов i_l-1 и j_l-1, и найдем в нем нашу перестановку (k₁,...,k_n) из канонической записи подстановки $$\tau$$ (пусть она занимает (r+1) -е место). Тогда (по лемме об умножении слева на цикл длины два)$$(i_r\quad j_r)... (i_1\quad j_1) \begin{pmatrix} 1 2 ... n\\ 1 2 ... n \end{pmatrix} = \begin{pmatrix} 1 2 ... n\\ k_1 k_2 ... k_n \end{pmatrix} = \tau,$$ т. е. $$\tau=\tau_r...\tau_1$$, где $$\tau_r=(i_r\quad j_r),..., \tau_1=(i_1\quad j_1)$$.

Замечание 5.2.5. Ясно, что представление подстановки $$\tau\=\tau_1...\tau_r$$ в виде произведения транспозиций возможно разными способами (например, (1 2)=(1 2)³ ).

Разложение подстановок в произведение циклов с непересекающимися орбитами

Орбитой цикла (i₁ i₂ ... i_r) назовем множество {i₁,...,i_r} .

Если $$\sigma\in S_n$$ - подстановка символов {1,2,...,n} и $$a\in N$$, $$1 \leq a \leq n$$, то рассмотрим последовательность$$a,\sigma(a),\sigma^2(a)=\sigma(\sigma(a)),...,\sigma^r(a),...$$ (орбиту элемента a ). Из конечности множества {1,2,...,n} следует, что найдутся такие натуральные числа t и s, t<s, что $$\sigma^ta=\sigma^sa$$. В группе S_n рассмотрим $$\sigma^{-1}$$. Применяя $$(\sigma^{-1})^t$$ к этому равенству, получим $$a=\sigma^{s-t}(a)$$, r=s-t>0. Рассмотрим самое маленькое такое натуральное число r (со свойством $$a=\sigma^r(a)$$, при этом все r элементов $$\{a,\sigma(a),...,\sigma^{r-1}(a)\}$$ различны). Итак, получили цикл $$(a\quad \sigma(a)\quad...\quad \sigma^{r-1}(a))$$ длины r. Выбирая элемент b вне этого цикла (если r<n ), получаем цикл $$(b\quad \sigma(b)\quad...\quad \sigma^{r'-1}(b))$$ длины r', при этом орбиты этих циклов не пересекаются. Продолжим этот процесс. Заметим, что циклы с непересекающимися орбитами перестановочны. Единственность этого разложения следует из инвариантности определения орбиты. Итак, получаем следующее утверждение.

Теорема 5.3.1. Каждая подстановка $$\tau\in S_n$$ разлагается (и притом единственным образом) в произведение циклов с непересекающимися орбитами (поэтому эти циклы перестановочны друг с другом).

Замечание 5.3.2.

В практических задачах удобно начинать с a=1, затем число b выбирать как наименьшее число, не вошедшее в $$\{a,\sigma(a),...,\sigma^{r-1}(a)\}$$,и т. д.

Как правило, циклы длины 1 (т. е. неподвижные элементы) опускают в записи циклового разложения подстановки.

Упражнение 5.3.3.

Пусть $$\sigma,\tau\in S_n$$. Подстановка $$\tau\sigma\tau^{-1}$$ называется подстановкой, сопряженной с подстановкой $$\sigma$$ (с помощью подстановки $$\tau$$ ). Проверьте, что отношение сопряженности является отношением эквивалентности. Соответствующее разбиение множества S_n на классы эквивалентных подстановок называется разбиением на классы сопряженных элементов .

Доказать, что подстановки $$\gamma,\sigma\in S_n$$ сопряжены тогда и только тогда, когда $$\gamma$$ и $$\sigma$$ имеют одинаковое цикловое разложение (т. е. одинаковое число циклов каждой длины в своих разложениях в произведение циклов с непересекающимися орбитами).

Указания

$$\tau(\sigma_1\sigma_2)\tau^{-1}= (\tau\sigma_1\tau^{-1})(\tau\sigma_2\tau^{-1})$$.

Если $$\sigma=(i_1,...,i_r)$$ - цикл длины r, то $$\tau\sigma\tau^{-1}=(\tau(i_1),...,\tau(i_r))$$.

Пример 5.3.4. Пусть$$\begin{align*} \delta = \begin{pmatrix} 1 2 3 4 5 6 7 8 9 10\\ 9 8 1 2 4 7 5 3 6 10 \end{pmatrix},\\ \sigma = \begin{pmatrix} 1 2 3 4 5 6 7 8 9 10\\ 5 1 6 10 2 4 9 7 3 8 \end{pmatrix}. \end{align*}$$ Требуется найти $$(\delta\sigma)^{100}$$.

Сначала находим$$\delta\sigma= \begin{pmatrix} 1 2 3 4 5 6 7 8 9 10\\ 4 9 7 10 8 2 6 5 1 3 \end{pmatrix}= (5\quad 8)(1\quad 4\quad 10\quad 3\quad 7\quad 6\quad 2\quad 9)$$ (разложение в произведение циклов с непересекающимися орбитами). Поэтому$$(\delta\sigma)^{100}=(5\quad 8)^{100} (1\quad 4\quad 10\quad 3\quad 7\quad 6\quad 2\quad 9)^{100}.$$ Так как (5 8)² и (1 4 10 3 7 6 2 9)⁸ - тождественные подстановки, $$100=12\cdot 8 \+ 4$$, то$$\begin{mult} (\delta\sigma)^{100} = (1\quad 4\quad 10\quad 3\quad 7\quad 6\quad 2\quad 9)^4 ={} \\ {}= \begin{pmatrix} 1 2 3 4 5 6 7 8 9 10\\ 7 10 9 6 5 4 1 8 3 2 \end{pmatrix}= (4\quad 6)(3\quad 9)(2\quad 10)(1\quad 7). \end{mult}$$

Задача 5.3.5. Найти разбиение на классы сопряженных элементов для групп S₃, S₄, S₅.

Задача 5.3.6.

Группа S_n порождается транспозициями (1 2),(1 3),...,(1 n) (т. е. любой элемент группы S_n является произведением этих транспозиций).

Указание Если $$i,j\neq 1$$, то (i j)=(1 i)(1 j)(1 i).

Группа S_n, $$n \geq 3$$, порождается транспозицией (1 2) и циклом (1 2... n).

Четность перестановок и подстановок

Будем говорить, что числа i и j в перестановке (...,i,...,j,...) образуют инверсию, если число i расположено левее, чем j, но i>j (в противном случае будем говорить, что числа i и j расположены в правильном порядке). Ясно, что сумма числа всех инверсией и числа всех порядков в любой перестановке из n чисел 1,2,...,n равна $$C_n^2=\frac{n(n-1)}{2}$$.

Пример 5.4.1. Число инверсий в перестановке (1,2,...,n) равно нулю, в перестановке (n,n-1,...,2,1) равно $$\frac{n(n-1)}{2}$$.

Удобный алгоритм подсчета числа инверсий: считаем, сколько инверсий образует 1 (все числа, находящиеся левее), после чего вычеркиваем 1 и переходим к 2 и т. д.

Теорема 5.4.2. Транспозиция в перестановке меняет четность числа инверсий.

Доказательство. Рассмотрим транспозицию элементов i и j:$$(...,i,...,j,...)\mapsto (...,j,...,i,...).$$ Сначала рассмотрим случай "соседей":$$(...,i,j,...)\mapsto (...,j,i,...).$$ Так как при перестановке чисел i и j их отношение с числами, расположенными левее (как и правее) не изменяется, то число инверсий изменяется на единицу (т. е. $$\pm 1$$ ), следовательно, четность числа инверсий изменяется.

Если же между числами i и j находится k элементов, то последовательно переставляя i с правыми соседними элементами k раз, потом с j, затем переставляя k раз элемент j с левыми соседними элементами, мы, проведя k+1+k=2k+1 транспозиций соседних элементов, осуществим транспозицию чисел i и j. Таким образом, четность изменилась.

Следствие 5.4.3. Число четных перестановок при $$n \geq 2$$ равно числу нечетных перестановок и равно $$\frac{n!}{2}$$.

Доказательство. Расположив все n! перестановок, начиная, например, с (1,2,...,n), в список, в котором каждая следующая перестановка получается из предыдущей одной транспозицией, мы видим, что четные перестановки чередуются с нечетными, поэтому число четных перестановок равно числу нечетных и равно $$\smash[b]{\frac{n!}{2}}$$.

Четность подстановки$$\begin{pmatrix} i_1 ... i_n\\ j_1 ... j_n \end{pmatrix}$$ определяется как четность суммы числа инверсий в верхней строчке и числа инверсий в нижней строчке.

Предложение 5.4.4. Четность подстановки $$\sigma\in S_n$$ не зависит от ее записи.

Доказательство. Если$$\sigma= \begin{pmatrix} i_1 ... i_n\\ \sigma(i_1) ... \sigma(i_n) \end{pmatrix} = \begin{pmatrix} i'_1 ... i'_n\\ \sigma(i'_1) ... \sigma(i'_n) \end{pmatrix}\text{ -}$$ две записи подстановки $$\sigma\in S_n$$, то, переходя конечным числом транспозиций от перестановки (i_1,...,i_n) к перестановке (i'₁,...,i'_n), переставляя при этом соответствующие "столбики"$$\begin{pmatrix} i\\ \sigma(i) \end{pmatrix},$$ приходим от нижней строчки $$(\sigma(i_1),...,\sigma(i_n))$$ к строчке $$(\sigma(i'_1),...,\sigma(i'_n))$$. Перестановка двух "столбиков" является транспозицией в верхней и в нижней строчках, следовательно, меняется четность в верхней и в нижней строчках, в итоге четность суммы числа транспозиций в верхней и в нижней строчке при перестановке двух "столбиков" не изменится.

Замечание 5.4.5. Подстановка, обратная к четной подстановке, четная. Действительно, если$$\sigma = \begin{pmatrix} i_1 i_2 ... i_n\\ j_1 j_2 ... j_n \end{pmatrix}$$ четная, то$$\sigma^{-1} = \begin{pmatrix} j_1 ... j_n\\ i_1 ... i_n \end{pmatrix}$$ четная.

Четность произведения подстановок

Возможность использовать произвольную запись подстановки удобна для рассмотрения произведения:$$\begin{pmatrix} i_1 ... i_n\\ j_1 ... j_n \end{pmatrix} \begin{pmatrix} 1 2 ... n\\ i_1 i_2 ... i_n \end{pmatrix} = \begin{pmatrix} 1 2 ... n\\ j_1 j_2 ... j_n \end{pmatrix},$$ откуда следует

Лемма 5.5.1 (о четности произведения).$$\begin{array}[b]{|c|c|c|} \sigma \tau \sigma\tau\\ \hline \textup{ч} \textup{ч} \textup{ч}\\ \hline \textup{н} \textup{ч} \textup{н}\\ \hline \textup{ч} \textup{н} \textup{н}\\ \hline \textup{н} \textup{н} \textup{ч}\\ \end{array}\;.$$

Рассмотрим отображение$$\begin{align*} \varepsilon\colon \mS_n \to \{1,-1\},\\ \varepsilon(\sigma) = \begin{cases} 1, \text{если $\sigma$"--- чётная подстановка},\\ -1, \text{если $\sigma$"--- нечётная подстановка}. \end{cases} \end{align*}$$

Замечание 5.5.2. Напомним, что {1,-1} - коммутативная группа относительно операции произведения. Действительно, произведение является операцией на {1,-1} ; эта операция ассоциативна и коммутативна; 1 - нейтральный элемент; (1)^-1=1, (-1)^-1=-1.

Следствие 5.5.3. Если $$\sigma,\tau\in S_n$$, то:$$\varepsilon(\sigma\tau)=\varepsilon(\sigma)\varepsilon(\tau)$$ (т. е. $$\sigma: S_n\to \{1,-1\}$$ - гомоморфизм групп);$$\varepsilon(\sigma)=\varepsilon(\sigma^{-1}).$$

Следствие 5.5.4. Если $$\sigma=\tau_1...\tau_k$$ - разложение подстановки $$\sigma\in S_n$$ в произведение транспозиций $$\tau_1,...,\tau_k$$, то $$\varepsilon(\sigma)=(-1)^k$$.

Доказательство. Отметим только, что если $$\tau=(i\quad j)$$ - транспозиция, то $$\varepsilon((i\quad j))=-1$$.

Упражнение 5.5.5. $$\varepsilon((i_1\quad...\quad i_r))=(-1)^{r-1}$$ для цикла (i_1... i_r) длины r, $$r \geq 2$$.

Теорема 5.5.6. Четные подстановки A_n являются группой (подгруппой в группе подстановок S_n ) $$|A_n|=\frac{n!}{2}$$ при $$n \geq 2$$.

Доказательство. Так как произведение $$\sigma\tau$$ четных подстановок $$\sigma,\tau\in A_n$$ является четной подстановкой, то имеем операцию произведения на множестве A_n, которая ассоциативна. Тождественная подстановка четная и является нейтральным элементом в A_n. Если $$\sigma\in A_n$$, то мы уже отметили, что $$\sigma^{-1}\in A_n$$.

Задача 5.5.7.Найти разбиение в классы сопряженных элементов групп A₄, A₅.

Задача 5.5.8. Группа A_n, $$n \geq 3$$, порождается тройными циклами (любой элемент группы A_n является произведением тройных циклов и обратных к ним; обратный элемент к тройному циклу сам является тройным циклом).

Указание Четная подстановка может быть представлена в виде произведения четного числа транспозиций, при различных i, j, k (i k)(i j)=(i j k), при различных i, j, k, l (i j)(k l)=(j k l)(i l j).

Страницы: