2. Перестановки.

Пусть имеется каких-нибудь элементов, расставленных в определенном порядке. Назовем это перестановкой, образованной из наших элементов. Докажем прежде всего, что таких различных перестановок будет При это очевидно, ибо два элемента могут образовывать две различные перестановки. При это непосредственно следует из подсчета перестановок (б), где роль элементов играют числа 1, 2, 3. Без труда можно убедиться, что (5) дают всевозможные перестановки из этих трех элементов. Докажем наше утверждение при любом целом по закону индукции.

Предполагая, что наше утверждение справедливо при некотором , докажем, что оно справедливо и для числа элементов Положим, что элементов дают перестановок и рассмотрим какие-нибудь элементов, которые обозначим

Обратим сначала внимание на те перестановки, у которых первым элементом будет Чтобы получить всевозможные такие перестановки, надо поставить на первое место Q, а затем писать всевозможные перестановки из оставшихся элементов, и число таких перестановок будет по предположению равно Таким образом, число перестановок из элементов начинающихся с элемента Q, будет равно Совершенно так же число перестановок из элементов начинающихся с элемента будет равно также . В общем, число различных перестановок из элементов будет

что и требовалось доказать.

Мы можем, конечно, считать, что за элементы взяты целые числа, начиная с единицы, чего мы и будем придерживаться в дальнейшем, Назовем транспозицией операцию, которая состоит в том, что в некоторой перестановке мы меняем местами два элемента. Непосредственно очевидно, что из всякой перестановки мы можем получить всякую другую перестановку, совершая несколько транспозиций. Например, возьмем две перестановки из четырех элементов

Можно перейти от первой из этих перестановок ко второй при помощи транспозиций путем следующего перехода:

Здесь нам понадобились три транспозиции, чтобы перейти от первой перестановки ко второй. Если бы мы совершали транспозиции иным образом, то мы могли бы и другим путем перейти от первой перестановки ко второй при помощи транспозиций, т. е., иначе говоря, число транспозиций, необходимых для перехода от одной перестановки к другой, не есть строго определенное число. Можно переходить от одной перестановки к другой при помощи различного числа транспозиций. Но для нас будет существенным доказать, что эти различные числа для двух заданных перестановок будут всегда или все четные или все нечетные. Иначе это выражают, говоря, что эти числа всегда одинаковой четности. Чтобы выяснить это, введем понятие о беспорядке, которым мы уже пользовались в предыдущем номере.

Пусть имеются перестановки из элементов 1, 2, . Назовем основной перестановкой ту перестановку

в которой числа идут возрастающим порядком. Назовем беспорядком в некоторой перестановке тот факт, когда два элемента этой перестановки следуют не в том порядке, в каком они стоят в основной перестановке (12), т. иначе говоря, когда большее число стоит левее меньшего. Назовем перестановками первого класса те перестановки, в которых число беспорядков есть число четное, и перестановками второго класса, — те, где это число есть число нечетное. Основным для дальнейшего будет следующая теорема:

Транспозиция меняет число беспорядков на число нечетное.

Возьмем некоторую перестановку

и положим, что мы применяем к этой перестановке транспозиции по отношению к элементам k и , т. е. меняем эти два элемента взаимно местами. После такой транспозиции взаимное расположение элементов k и относительно элементов, стоящих левее k или правее останется прежним. Изменится лишь взаимное расположение элементов k и относительно тех элементов, которые стоят в перестановке между k и , а также изменится, конечно, взаимное расположение элементов k и одного относительно другого. Подсчитаем общее изменение числа беспорядков. Положим, что между элементами k и в перестановке (13) стоит всего элементов, и пусть эти средние элементы по сравнению с элементом k дают а порядков и беспорядков, относительно же элемента дают порядков и беспорядков. Имеем, очевидно:

В результате транспозиции порядок перейдет в беспорядок и наоборот, т. е., точнее говоря, если элемент k с некоторым средним элементом до транспозиции был в порядке, то после транспозиции он окажется в беспорядке и наоборот, и то же самое для элемента . Таким образом общее число беспорядков у элементов k и относительно средних элементов до транспозиции было и после транспозиции т. е. изменение числа беспорядков будет

Пользуясь (14), можем переписать это число в виде:

откуда непосредственно следует, что это число у будет четным. Остается обратить внимание на взаимное расположение самих элементов k и .

Если до транспозиции они образовывали порядок, то после они образуют беспорядок и наоборот, т. е. здесь изменение числа беспорядков равно единице, и таким образом общее изменение числа беспорядков, происшедших от транспозиции, будет числом нечетным.

Выясним некоторые следствия, вытекающие из доказанной теоремы.

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

Следствие II. Всякая перестановка может быть получена из основной путем транспозиций. Из доказанной теоремы непосредственно следует, что первый класс образуют те перестановки, которые получаются из основной путем четного числа транспозиций, а второй класс — те перестановки, которые получаются из основной путем нечетного числа транспозиций.

Следствие III. Выбор основной перестановки совершенно произволен. Мы могли бы вместо перестановки (12) выбрать за основную какую-нибудь другую перестановку, при этом, конечно, при определении беспорядков надо сравнивать перестановку с основной, т. е. исходить из того порядка элементов, в котором они стоят в основной перестановке. Нетрудно видеть, что если мы возьмем вместо перестановки (12) за основную перестановку какую-нибудь из перестановок первого класса, то перестановки первого класса останутся по-прежнему перестановками первого класса, а перестановки второго класса останутся перестановками второго класса. Наоборот, если мы за основную перестановку возьмем какую-нибудь перестановку второго класса, то перестановки второго класса станут перестановками первого класса, и перестановки первого класса станут перестановками второго класса.

Например, если в шести перестановках из элементов 1, 2, 3 мы примем за основную перестановку 2, 1, 3, то перестановками первого класса будут перестановки:

Во второй из этих перестановок мы имеем два беспорядка: 1 стоит перед 2 и 3 перед 2, а в основной 2 стоит перед 1 и 2 перед 3. Перестановками второго класса будут перестановки:

В первой из этих перестановок мы имеем один беспорядок по сравнению с основной 2, 1, 3, а именно 1 стоит перед 2.

Принимая во внимание сказанное выше, мы можем формулировать правило знаков в выражении (8) следующим образом: мы пишем перед произведением знак плюс, если перестановка из вторых значков принадлежит первому классу, и знай минус, перестановка из вторых значков принадлежит второму классу, чем за основную перестановку принята перестановка 1, 2,..., n.

Выясним теперь одно из основных свойств определителя. Переставим в таблице, дающей определитель, первый и второй столбцы. Числа, которые мы раньше обозначали через мы по-прежнему будем обозначать этими же буквами с теми же самыми значками. Вместо таблицы (6) будем иметь таблицу:

Мы можем теперь, пользуясь определением, выражаемым формулой (8), составить определитель, соответствующий таблице (15). В этой таблице столбцы пронумерованы в следующем порядке: и эту перестановку мы должны считать за основную. Она получилась из прежней основной при помощи одной транспозиции и, следовательно, раньше принадлежала ко второму классу. Таким образом прежние перестановки второго класса станут при новом выборе основной перестановки перестановками первого класса и наоборот. Следовательно, определитель, соответствующий таблице (15), будет суммой тех же слагаемых, которые стоят в формуле (8), но вследствие указанного только что изменения в распределении перестановок вторых значков по классам знаки у членов новой суммы будут противоположны знакам слагаемых суммы (8), т. е. при перестановке двух столбцов величина определителя меняет знак. Мы доказали это свойство, переставляя первый и второй столбцы. Точно такое же доказательство годится и при перестановке двух любых столбцов. Так, например, имеет место формула:

Второй определитель получается из первого перестановкой второго и третьего столбцов.

Выясним еще одно свойство определителя. Возьмем некоторое слагаемое суммы (8):

Переставляя порядок сомножителей, мы можем привести в полный порядок вторые значки, но при этом первые значки будут образовывать некоторую перестановку и предыдущее выражение запишется в виде:

Переход от к можно совершить при помощи нескольких транспозиций сомножителей. Всякая такая транспозиция будет одновременно транспозицией в перестановке как первых, так и вторых значков. Если число необходимых транспозиций для перехода от к будет четным, то отсюда будет следовать, что перестановка принадлежит первому классу, так как она переходит в основную при помощи четного числа транспозиций и, следовательно, очевидно, может быть получена из основной также при помощи четного числа транспозиций. Но при этом и перестановка принадлежит к первому классу, так как она одновременно получается из основной при помощи того же четного числа транспозиций. Точно так же, если принадлежит второму классу, то и принадлежит второму классу. Отсюда следует, что и, следовательно, мы можем написать:

Итак, если мы сравним соответствующие слагаемые в суммах (8) и (10), то увидим, что эти суммы в точности совпадают. В сумме (10) строки играют ту же роль, что столбцы в сумме (8), и из наших рассуждений непосредственно следует, что если в таблице заменить все строки столбцами и столбцы строками, не меняя их порядка, то величина определителя от этого не изменится.

Так, например, мы имеем равенство следующих двух определителей третьего порядка: