Лекции по алгебре - Фаддеев Д.К.
Скачать (прямая ссылка):
ТЕОРИЯ ОПРЕДЕЛИТЕЛЕЙ
87
Теперь разобьем все п\ перестановок п элементов на два класса, по признаку, кажущемуся довольно искусственным, но именно это разбиение будет нужно для разумного правила расстановки знаков в определителе.
Пусть (а,, о&2, •••, OLn)—некоторая перестановка чисел 1, 2, ... п. Скажем, что пара элементов (а,-, а;), і <С/, образует инверсию, если сх< > а/. Число всех пар элементов перестановки, образующих инверсию, называется числом инверсий в перестановке и обозначается inv(cxi, а?, ап). Так, inv(3, 5, 1, 4, 2, 6,
8, 7) = 7 (инверсии образуют пары (З, 1), (3, 2), (5, 1), (5, 4),
Перестановки, содержащие четное число инверсий, называются четными, содержащие нечетное число инверсий — нечетными.
Подстановкой на множестве {1, 2, п} называется взаимно однозначное отображение множества на себя. Удобно задавать подстановку прямым указанием замен для каждого элемента, посредством записи образа под прообразом. Так, запись
1, 2, 3, 4, 5, соответственно, на 5, 1, 3, 2, 4; порядок расположения ее столбцов безразличен. В такой записи в «числителе» и в «знаменателе» оказываются перестановки. Удобно в «числителе» записывать элементы в натуральном расположении.
Последовательное применение двух подстановок приводит к подстановке, называемой их произведением. Так,
/ 1 2 3 4 5 6 \ / 1 2 3 4 5 6 \ _ / 1 2 3 4 5 6\ \5 2 1 6 4 3j"U 1 2 4 3 5 J-VS 1 6 5 4 2)
(мы считаем первой действующей ту подстановку, которая записана слева). Почти очевидно, что при умножении подстановок имеет место ассоциативность. Действительно, пусть а, х и ср — подстановки на-множестве {1, 2, п}. Сделать (от)ср— все равно, что сначала сделать а, потом т, затем ср; сделать же о (тер) — все равно, что сначала сделать о, потом тер, т. е. к результату применения о применить т и затем ср.
Тождественная подстановка, при которой каждому элементу сопоставляется он сам, играет роль единицы в этом умножении. Если запись подстановки а перевернуть, т. е. ее числитель сделать знаменателем, а знаменатель числителем, мы придем к обратной подстановке а~1, произведение которой на а как в одном, так и в обратном порядке, дает единичную подстановку. Умножение подстановок, вообще говоря, некоммутативно, например,
V2 1 ЗМ2 3 \) \Ъ 2 і)' \2 З l)\2 1 .з)~\ 1 3 2)-
Число всех возможных подстановок на множестве из п элементов равно п\, ибо таково число возможных знаменателей при фиксированном числителе.
(5, 2), (4, 2), (8, 7)).
2 3 4 1 3 2
задает подстановку, которая заменяет элементы
88
МАТРИЦЫ И ОПРЕДЕЛИТЕЛИ
[ГЛ. IV
Подстановка называется транспозицией, если она п — 2 элемента оставляет на местах, а остальные два элемента переставляет местами. Вместо того чтобы записывать, например, транспо-
/1234564
зицию ^ 1 5 3 4 2 6 7' ПИШУТ кратко (2, 5).
Предложение 2. Пусть в некоторой перестановке сделана транспозиция. Она равна произведению нечетного числа транспозиций соседних элементов.
Доказательство. Пусть дана перестановка
(«. Ь.....c,.d, е.....f, g,jh .... k, I),
и транспозиция меняет местами сип. Обозначим через m число элементов d, е, ..., f, g, лежащих между с и Л. Переставим местами с с d, затем ссе,..., с с f, с с g. После этого мы придем к перестановке
(а, Ь, .... d, е, f, g, с, h.....k, I).
Мы сделали последовательно m транспозиций. Теперь переставим с и ft. Придем к
(а, Ь, d, е, .... f, g, п, с, k, I).
Теперь «перегоним» ft на место, которое занимало с, переставив ft по очереди с g, с с е, с d. Мы придем к перестановке
(а, Ь, h, d, е, f, g, с, ...,&,/),
т. е. как будто мы сделали одну транспозицию (с, ft). Всего мы сделали m + 1 + m = 2rn + 1 транспозиций соседних элементов. Таким образом, транспозиция (с, К) равна произведению 2m + 1 транспозиций соседних элементов. Все это рассуждение равносильно одному равенству:
(с, п) = (с, d) (с, е)... (с, f) (с, g) (с, h) (g, h) (U п) ... (е, ft) (d, ft).
Предложение 3. При транспозиции соседних элементов число инверсий в перестановке меняется на одну единицу.
Доказательство. Нам нужно сравнить число инверсий в перестановках
(а, Ь.....с, d, е, f, k, I)
и
(а, Ь.....с, е, d,f, k, I).
Обозначим через Z1 и i[ число инверсий в парах, не содержащих элементов d и е, в обеих перестановках соответственно; через I2 и Ґ2— число инверсий в парах, содержащих один из элементов due; через i3 и I3 — число инверсий в паре d, е и через і и і' — полное число инверсий. Ясно, что І = t*i + к + із, і' — ї\ + 4 + 'з-
Далее, очевидно, что I1= і[. Число /2 тоже равно i'v так как каждый из элементов d и е расположен относительно остальных элементов одинаковым образом в обеих перестановках. На-
ТЕОРИЯ ОПРЕДЕЛИТЕЛЕЙ
8»
конец, если Z3== 0» то ї'з = 1, и если I3=I, то і"з = 0. Поэтому
i' — t = »"i + »2 + *з — 'i — h~h~h~ 1»что и требовалось
доказать.
Следствие 1. Если в перестановке сделать транспозицию соседних элементов, то четность перестановки изменится на противоположную.
