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

Posted by admin on 23 Июль 2010 | Subscribe
in Лекции по алгебре
as , , , ,

Теорема 5.0.4. Множество S(U) всех биекций

f: U\to U

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

  1. операция произведения ассоциативна (h(gf)=(hg)f для всех f,g,h\in S(U)),
  2. нейтральным элементом для этой операции является тождественное отображение 1U (1Uf=f=f1U для всех f\in S(U)),
  3. для всякой биекции f: U\to U существует обратный элемент — биекция g=f-1 (fg=1U=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}, в этом случае группу Sn = 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, при этом только по одному разу. Такие строчки элементов (i1,…,in), 1 \leq i_j \leq n, где каждый элемент i_j, 1 \leq i_j \leq n, встречается один и только один раз, называются перестановками элементов 1,2,…,n.

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

Доказательство. Для i1 имеем n возможностей. При выбранном i1 для i2 имеем (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, располагая в верхней строчке произвольную перестановку (i1,i2,…,in):

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

  1. Для тождественной подстановки в S2 имеем
    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}.
  2. Если
    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}.
  3. Так как (\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}.
  4. Обозначим через (i1 i2… ir) цикл длины r в группе подстановок Sn: подстановку, переводящую ik в ik+1 для 1 \leq k \leq r-1, ir в i1, и оставляющую все элементы из {1,2,…,n}, отличные от i1,…,ir, на месте. Тогда в S3 имеем шесть подстановок:
    \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*}

    При этом в Sn для 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),

    следовательно, группа S3 и любая группа Sn при n \geq 3 некоммутативны. Так как S1={e} и S2={e, (1 2)} — коммутативные группы, то получаем, что группа Sn коммутативна тогда и только тогда, когда n=1 или n=2.