§ 4. Перестановки и подстановки

Здесь собран вспомогательный материал, который пона­добится при изучении определителей.

1. Перестановки. Перестановкой порядка п, называет­ся набор чисел 1,2,...,»,, расположенных (переставленных) в определенном порядке. Будем использовать обозначение

X = (м - 'г, • • • ,гп);

здесь числа гь г2.....1п, принимают одно из значений 1,2..... п,

причем среди них нет повторяющихся. Если для какой-либо пары (гк,»;) при к < I окажется 4 > ц, то скажем, что этой паре в перестановке X соответствует беспорядок (инверсия). Напри­мер, в перестановке I = (3,5.2,1,4) инверсии соответствуют парам (3,2), (3,1), (5,2), (5,1), (5.4), (2,1). В зависимости от четности числа беспорядков перестановку называют четной или нечетной. Тождественная перестановка I = (1,2,..., п) — четная. Перестановка в рассмотренном примере также чет­ная (число инверсий равно 6).

Поменяем в 1 местами какие-нибудь два элемента; такая операция называется транспозицией.

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

Доказательство. Сначала предположим, что поменяли ме­стами два соседних элемента г*, г*+1- Тогда либо добавится один новый беспорядок (если гк < 1к+)), либо один беспорядок исчезнет (если гд. > 1к+\). В любом случае число беспорядков изменится на единицу, и четность перестановки поменяется. Рассмотрим теперь общий случай. Пусть переставлены ме­стами гк и «к+«+ь -ч > 0- Эту транспозицию можно осуществить

так. Переставим г* последовательно с г^1, й+2,____й^.^ь на

что потребуется (* + 1) "соседних" транспозиций. Затем последовательно переставим с ____.1к+2.Ч+\, что потребуетеще 8 "соседних" транспозиций. Таким образом, четность из­менится 2я 4-1 раз, т.е. окажется противоположной исходной.

Легко понять, что любую перестановку X можно перевести в любую другую перестановку 3 некоторым числом транс­позиций. Этот результат может быть достигнут различными способами. Однако, если четность X и 3 одинакова, то число транспозиций обязательно четно, ибо каждая транспозиция меняет четность. Напротив, если четность X и 3 различна, то число потребных транспозиций — нечетное. В частно­сти, любая четная перестановка получается из тождественной четным, а нечетная перестановка — нечетным числом транс­позиций.

Всего различных перестановок порядка п имеется п). Ко­личество четных и нечетных перестановок одинаково и равно п!/2. Это следует из того, что если мы все и! перестано­вок одновременно подвергнем какой-нибудь одной и той же транспозиции, то четные перестановки перейдут в нечетные и наоборот.

Перестановкам сопоставляют знак перестановки е(1): е(Т) = 4-1, если X — четная; е(Х) = — 1, если X — нечетная.

2. Подстановки. Подстановкой порядка п называется взаимно однозначное отображение множества, состоящего из п различных предметов, на себя. Пронумеруем эти предметы. Пусть первый предмет отображается в предмет с номером г'|, второй — в предмет с номером *2 и т.д. Числа X — (ц,..., *„) образуют перестановку, которая однозначно определяет нашу подстановку. Символически это можно записать так:

где а — рассматриваемая подстановка. Ту же подстановку можно записать и иначе. Пусть в первый предмет переходит предмет с номером уі, во второй — с номером іг, и т.д. Тогда <т запишется в виде

 

(1)

 

]\: 32,

1, 2,

Например,

/1,   2.   З,   4,   5\ _ /4.   З,   1,   5. 2\ \3,   5,   2,   1,   4.) ~ \1,   2,   3,   4,   5) -

Вообще, ясно, что а можно записать в виде

(3)

если (3) получено из (1) применением одной и той же переста­новки к элементам обеих строк формулы (1). Таким образом, подстановка а определяется парой перестановок (К., С), опре­деленных с точностью до одной и той же перестановки над элементами К и С. Вместо (1)-(3) удобно коротко писать

о-=(/,!) = (.7, /) = (£,£).

Тождественную подстановку будем обозначать через 1:

1 = (1,1) = (1С, К),

где К — любая перестановка.

Совокупность всех подстановок обозначим через V,,. Так как всякая подстановка единственным образом записывается в виде (1), то множество "Р„ содержит п\ элементов.

3. Произведение подстановок. Выполняя последователь­но подстановки (отображения) г и а, мы снова получим подста­новку, отвечающую композиции этих отображений. Эта под­становка обозначается через сгт и называется произведением подстановок т и <т. Это произведение при н > 2 не коммута­тивно: сгт и та, вообще говоря, различны. При образовании произведения <тт удобно представить т и а в виде г = (1,1С), а = (/С, С). Ясно, что тогда о~т = (/,£)• Например, пусть

/1.   2,   3,   4. ГЛ

УЗ,   5,   2,   1,   4 / 1

_ / 1.   2.   3,   4,   5\ = /3,   5.   2,   1. 4\ 47     \ 5,   3.   4,   1.   2) ~ \4,   2.   3,   5, \)'

Тогда

= (1,   2,   3.   4, 5\ ат~ ^4,   2,   3,   5,   \) ■

Упражнение. Найдите для этого примера подстановку та. Приведем свойства произведения подстановок.

1. Ассоциативность:

р,(ат) = (р.а)т.

Для доказательства представим подстановки в виде: т = (/,£), а = (£,£), ,* = (£, Л Тогда <7г = (/,£), р(ат) = (1^). С другой стороны, р,а = (/С, ,7), (а»сг)т = (/, ч7). •

2. Существование "единицы". Для тождественной подста­новки    и любой подстановки а, очевидно,

1(7 = (7 Т. = (7.

3. Существование обратной подстановки. Для любой под­становки а существует подстановка р, такая что

ра = ар — 1.

Подстановка р называется обратной к подстановке а и обо­значается через <7~\ Легко понять, что для а = (1,1) обратной является подстановка <т-1 = (I. /). В частности, I-1 = !.

Свойства 1,2,3 означают, что множество подстановок Тп с операцией произведения образует группу, то есть множество с ассоциативной внутренней операцией, в котором существует единица и каждый элемент имеет обратный.

4. Знак подстановки. Знаком подстановки а = (/С, С) на­зывается число е(а) = е(К)е(£). Проверим корректность этого определения Знак е(а) зависит только от а, но не от того, ка­кой именно парой перестановок задается а. В самом деле, если элементы К и С подвергнуть одной и той же перестановке, то четность и К, и £ либо сохранится (если выполняемая переста­новка четная), либо изменится. В обоих случаях произведение е(К)е(С) останется прежним.

Очевидно, е(1) = 1. Покажем теперь, что

е(ат) = е(«х)е(т). (4)

Для доказательства представим подстановки в виде т = (/,/С), а = (К, С). Тогда от = (/,£) и е(т) = е{1)е(К) = е(/С), е{<т) = е(£)е(£), е(<гт) = е(£). Поэтому, е{а)е{т) = (е(£))2Б(£) = е(£) = е(<тт). •

Из (4), в частности, следует, что е(<тт) = е(то). Кроме того, е((т~])е(<т) = е(<т~1а) — е(1) = 1, а потому

ф-1) = е(а).

Подстановка называется четной, если е(<г) = 1, и нечетной, если е(о-) = — 1. Множество четных подстановок образует груп­пу (подгруппу группы Рп). Множество нечетных подстановок не образует группу, поскольку произведение двух нечетных подстановок является четной подстановкой.