RUDN-I

Доказательство теоремы 3.1.

1) При n = 1 имеем A1 = (a1), S(A1) = {e} — тождественная переста-

2) Покажем, что Bn Bn+1 (шаг индукции), где Bn — утверждение, что Pn = n! Итак, нужно показать, что если Pn = n! (допущение индукции), то Pn+1 = (n + 1)! Для этого получим формулу

ментов из An+1. Число перестановок, входящих в класс Cm, равно Pn (при всех m = 1, 2, . . . , n + 1); число классов равно (n + 1). Значит,

Определениеwww1. Пусть α = (ak1 , ak2 , . . . , akn ) — перестановка множества A = (a1, a2, . . . , an). Если пара номеров (kl, km), такова, что l < m, но kl > km, то говорят, что пара (kl, km) образует инверсию (элемент с большим номером стоит раньше).

число всех перестановок в S(An+1) равно Pn+1 = (n + 1)Pn, т.е. вер-

Иначе: инверсия означает, что элемент из A с меньшим номером при перестановке оказался правее элемента с большим номером.

Общее число инверсий в перестановке α обозначим N(α).

42 Тема 3. Перестановки

Определение 2. 1) Если N(α) — четное число, то перестановка называется четной, если N(α) — нечетно, то α называется нечетной.

Пример 2. Найти число инверсий в перестановке α = (a4, a2, a3, a1).

Для этого для каждого элемента считаем, сколько инверсий. с элемента-

ми, стоящими правее: a имеет 3 инверсии, a имеет 1 инверсию, a имеет 1 инверсию, итак, N(αmatematem)4 = 3 + 1 + 1 = 5; т.е. 2α — нечетная. 3

3.2. Транспозиции

Определение 1. Перестановка β S(An) называется транспозицией, если она переставляет только два элемента (остальные остаются на месте).

Запись транспозиции β = βij (i < j) означает, что β меняет местами i-ый и j-ый элементы, т.е.

Пусть α S(An), β — транспозиция. Суперпозиция β ◦ α есть перестановка β ◦ α S(An), называемая транспозицией перестановки α.

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

Доказательство. 1) Сначала рассмотрим случай, когда β = βi(i+1), т.е.

β ◦ α означает замену местами двух соседних элементов: aki и aki+1 в перестановке α:

Взаимное расположение этих элементов с любыми другими элементами не меняется, т.е. инверсии не появляются и не исчезают. Между самими этими элементами при замене их местами либо возникнет одна инверсия, либо исчезнет одна инверсия. Итак, общее число инверсий N(β ◦ α) = N(α) ± 1, т.е. четность перестановки меняется.

2) Рассмотрим общий случай β = βi(i+m+1), когда между двумя переставляемыми элементами стоят m элементов: меняем местами aki и aki+m+1 ,

α = (. . . , aki , aki+1 , . . . , aki+m , aki+m+1 , . . .),

β ◦ α = (. . . , aki+m+1 , aki+1 , . . . , aki+m , aki , . . .).

Такую замену проведем последовательно, меняя местами соседние эле-

затем со следующим, . . . , затем с aki+m , затем с aki+m+1 — всего (m + 1) транспозиция соседей. В результате получим перестановку

(. . . , aki+1 , . . . , aki+m , aki+m+1 , aki , . . .).

комую перестановку β ◦α. Итак, общий случай транспозиции β ◦α свелся

к применению m + (m + 1) = 2m + 1 транспозиций соседних элементов.

Согласно 1) при каждой такой транспозиции четность перестановки ме-

нялась. В итоге, она меняется (2m + 1) раз, т.е. четности перестановок β ◦ α и α разные.

Следствие. При n ≥ 2 число четных перестановок в S(An) равно числу нечетных перестановок (и равно n2!).

Доказательство. Пусть p — число всех нечетных перестановок, q — число всех четных перестановок. Для каждой нечетной перестановки поменяем местами 1-ый и 2-ой элементы. По теореме 1 она станет четной, т.е. мы получили p различных четных перестановок. Их число не больше, чем число q всех четных перестановок, т.е. p ≤ q. Поменяем в этом рассуждении нечетные перестановки на четные, получим точно так же, что q ≤ p. Значит, p = q.

Теорема 2. Всякая перестановка α S(An) может быть представлена как произведение транспозиций, причем число сомножителей четно, если α четная, и нечетно, если α нечетная.

Шаг 0. wwwЕсли α = e — тождественная перестановка, то поскольку β12 ◦ β12 = e, то α = e = β12 ◦ β12 — искомое разложение.

Доказательство. Обозначим

Пусть α = (ak1 , ak2 , . . . , akn ) S(An). Далее считаем, что α ≠ e.

Шаг 1. Обозначим i1 — номер элемента a1 в перестановке α. Если i1 = 1, т.е. ak1 = a1, то на этом шаге α нас устраивает. Полагаем тогда α = α1,

44 Тема 3. Перестановки

т.е. α = e ◦ α1 = β1i1 ◦ α1, где α1 = (a1, ak2 , . . . , akn ). Если 2 ≤ i1 ≤ n, то имеем

↑

Итак, в результате шагаmatematem1, в обоих случаях имеем

α = β1i1 ◦ α1,

где α1 = (a1, ak2 , . . . , ak1 , . . . , akn ) S(An).

Шаг 2. Обозначим i2 — номер элемента a2 в перестановке α1. Если i2 = 2, т.е. α1 = (a1, a2, . . .), то α1 нас устраивает на этом шаге. Полагаем тогда

α = β1i1 ◦ α = β1i1 ◦ β2i2 ◦ α .

α = β1i1 ◦ β2i2 ◦ α2, α2 = (a1, a2, . . .)

и т.д.

На каждом шаге число элементов, стоящих по порядку увеличивается, так что на k-ом шаге получим

если m четно, то и α будет четной. Теорема 2 доказана.

Осталось заметить, чтоmatematemкаждая транспозиция меняет четность перестановки (см. теорему 1). Так что, если m нечетно, то α будет нечетной,

Замечание 1. Приведенное доказательство дает алгоритм разложения перестановки в произведение транспозиций.

Пример. Представить перестановку α = (4, 3, 1, 2) в виде произведения транспозиций.

= β13 ◦ β24 ◦ β34 ◦ (1, 2, 3, 4) = β13 ◦ β24 ◦ β34.

Напомним, что знак перестановки — это число sign α = (−1)N(α),

где N(α) — число инверсий в α.

Теорема 3. При умножении перестановок их знаки перемножаются.

Доказательство. Пусть α1, α2 S(An). Тогда α1◦α2 S(An). Покажем, что

sign(α ◦ α ) = sign α · sign α .

Следствие. Взаимно обратные перестановки имеют одинаковую четность.

Доказательство. Действительно, пусть α S(An), β = α−1. Тогда α ◦

либо sign α = sign α−1 = −1.

3.3. Теоретические упражнения к теме 3

3.1. Каждой перестановке α элементов конечного множества A сопоставим обратную к ней α−1. Показать, что отображение, заданное правилом f(α) = α−1, является биекцией на множестве S(A) всех перестановок множества A. Таким образом, когда α пробегает множество S(A), то и α−1 пробегает множество S(A).

3.2. Для перестановки α = (5, 3, 4, 1, 2) найти обратную. Найти число инверсий в перестановках α, α−1 и разложить их в произведение транспозиций.

3.4. Пусть X, Y — конечные множества с числом элементов m и n, соответственно. Найти общее число отображений и число инъективных отображений множества X во множество Y . Получить отсюда формулу числа биекций (при m = n) и, в частности, формулу для числа всех перестановок множества X.

47

Тема 4. Определители

Изложение теории определителей мы начинаем с определителей 2-го и

лителей). Затем вводится общее понятие определителя n-го порядка и разбираются общие свойства определителей, включая формулы разложения определителя по строке и столбцу, полилинейность и кососимметричность. Рассмотрены примеры вычисления важнейших определителей (треугольный, определитель Вандермонда, блочно-треугольный). Применения определителей в теории систем линейных уравнений (в частности, формулы Крамера) отнесены к теме 5 (алгебра матриц). Там же приведена характеризация определителя как полилинейной, кососимметрической функции.

4.1. Определители второго и третьего порядка

Действительно, поменяем местами две одинаковых строки. Матрица, а значит и определитель, не изменится. Но по свойству 2◦ определитель меняет знак. Значит, det A = − det A, т.е. det A = 0.

4◦. Определитель является линейной функцией строк (столбцов) матрицы.

Это значит, что 1) при умножении строки (столбца) на число определитель умножается

на это число, например,

линейную комбинацию других строк (столбцов).

полученный из исходного вычеркиванием i-ой строки и j-го столбца. Ал-

Определитель равен сумме произведений элементов любой строки (любого столбца) на их алгебраические дополнения.

Для n = 3 это свойство можно получить непосредственно из определения (см. упражнение 4.2).

4.2. Понятие определителя n-го порядка

Замечание. Конечную сумму a1 +a2 +. . .+an можно записать в краткой форме

При этом неважно, какой буквой обозначен индекс суммирования. Для той же суммы верно равенство

∑n

Однако, если в одном месте используются различные суммы, например,

(i) и

n

то индексы суммирования нужно обозначать разными буквами. Например, можно использовать (i) и (iii), но нужно избегать совместного использования (ii) и (iii).

Пусть A = aij — квадратная матрица n-го порядка. Приведем различные формы записи