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

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

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

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

Лемма 5.2.1.

  1. Умножение слева (i j)fподстановки
    f = \begin{pmatrix} i_1 & ... & i_n\\ j_1 & ... & j_n \end{pmatrix}

    на цикл (i j) длины 2 приводит к транспозиции элементов i и j в нижней строке (перестановке) (j1,…,jn).

  2. Умножение справа f(i j) подстановки
    f = \begin{pmatrix} i_1 & ... & i_n\\ j_1 & ... & j_n \end{pmatrix}

    на цикл (i j) длины 2 приводит к транспозиции элементов i и j в верхней строке (перестановке) (i1,…,in).

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

  1. \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}
  2. \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} можно расположить в список, начиная с произвольной перестановки (i1,i2,…,in), так, что каждая следующая перестановка в этом списке получается из предыдущей с помощью некоторой транспозиции двух элементов.

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

\scriptstyle{(n-1)!} \left\{ \begin{array}{@{}l@{}} (i_1,i_2,...,i_n),\\ \quad \vdots\\ (i_1,...,i_2,...). \end{array} \right.

Совершая транспозицию i1 и i2 в последней перестановке первого блока и повторяя наше рассуждение, построим второй блок из различных (n-1)! перестановок с i2 на первом месте (т. е. перестановок элементов {i1,i3,…,in}), при этом каждая следующая перестановка получается из предыдущей применением транспозиции:

\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. От любой перестановки (i1,…,in) можно перейти к любой другой перестановке (j1,…,jn) с помощью конечного числа транспозиций.

Доказательство. В списке с началом (i1,…,in) надо найти перестановку (j1,…,jn).

Следствие 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)-й транспозицией элементов il-1 и jl-1, и найдем в нем нашу перестановку (k1,…,kn) из канонической записи подстановки \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)3).