УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу ОПРЕДЕЛИТЕЛЬ


Свойства перестановок

Т

Теорема 1. Число всех перестановок из n элементов равно n!.

Доказательство ЗДЕСЬ.

Итак, формула из определения определителя

\det A=\left| \begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \dots & & & \dots \\ a_{n1} & a_{n2} & \dots & a_{nn} \end{array}\right|=\sum (-1)^{\operatorname{inv}(\alpha_1,\alpha_2,\dots,\alpha_n)}a_{1\alpha_1}a_{2\alpha_2} \times \dots \times a_{n\alpha_n},

заключает в себе n! слагаемых. Покажем теперь, что в этой формуле количество слагаемых (мономов) с коэффициентом + 1 совпадает с количеством слагаемых с коэффициентом -1.


Перестановки с четным числом инверсий называются четными, с нечетным — нечетными.


Рассмотрим две перестановки

\Theta=(a_1,\dots,a_K, {\color{RubineRed} \alpha } ,b_1,\dots,b_{L}, {\color{ForestGreen} \beta },c_1,\dots,c_M)
\Xi=(a_1,\dots,a_K, {\color{ForestGreen} \beta },b_1,\dots,b_{L}, {\color{RubineRed} \alpha },c_1,\dots,c_M)

Говорят, что перестановка \Xi получена из перестановки \Theta в результате транспозиции.

Т

Теорема 2. Любая транспозиция меняет четность перестановки:

\operatorname{inv} \Theta - \operatorname{inv} \Xi = нечетное .

Доказательство. I. Предположим сначала, что L=0, т.е. производится транспозиция соседних элементов.

\operatorname{inv} \Theta= \operatorname{inv} (a_1,\dots,a_K, {\color{RubineRed} \alpha } , {\color{ForestGreen} \beta },c_1,\dots,c_M)=
= \sum_{1\le i <j \le K} \operatorname{inv}(a_i,a_j)+ \sum_{1\le i \le K} \operatorname{inv}(a_i, {\color{RubineRed} \alpha })+ \sum_{1\le i \le K} \operatorname{inv} (a_i,{\color{ForestGreen} \beta })+
+\sum_{\scriptstyle 1\le i \le K \atop \scriptstyle 1\le \ell \le M} \operatorname{inv}(a_i,c_{\ell})+\operatorname{inv} ({\color{RubineRed} \alpha },{\color{ForestGreen} \beta })+ \sum_{1\le \ell \le M}\operatorname{inv}({\color{RubineRed} \alpha },c_{\ell})+
+\sum_{1\le \ell \le M}\operatorname{inv}({\color{ForestGreen} \beta },c_{\ell})+\sum_{1\le i <j \le M} \operatorname{inv} (c_i,c_j)

Разложение для \operatorname{inv} \Xi отличается от этого только пятым слагаемым, которое меняется на \operatorname{inv} ({\color{ForestGreen} \beta },{\color{RubineRed} \alpha }). Поэтому

\operatorname{inv} \Theta - \operatorname{inv} \Xi =\operatorname{inv} ({\color{RubineRed} \alpha },{\color{ForestGreen} \beta })- \operatorname{inv} ({\color{ForestGreen} \beta },{\color{RubineRed} \alpha })= \pm 1.

II. Покажем, что сумма произвольного \underline{нечетного} числа чисел, каждое из которых равно +1 или -1 есть число нечетное. Пусть среди заданных чисел \omega_1,\dots,\omega_{2N+1} имеется p, равных 1, и q, равных -1. Тогда

2N+1=p+q, \quad и \ \omega_1+\dots+\omega_{2N+1}=p-q =2N+1-2q=2(N-q)+1.

III. Покажем теперь справедливость утверждения теоремы для любого L \ge 1.

\operatorname{inv} \Theta = \operatorname{inv} (a_1,\dots,a_K,{\color{RubineRed} \alpha }, b_1,\dots,b_{L},{\color{ForestGreen} \beta },c_1,\dots,c_M)=
=\ \operatorname{inv} (a_1,\dots,a_K,b_1,{\color{RubineRed} \alpha }, \dots,b_{L},{\color{ForestGreen} \beta },c_1,\dots,c_M) +\omega_1=\dots=
=\operatorname{inv} (a_1,\dots,a_K,b_1, \dots,b_{L},{\color{RubineRed} \alpha },{\color{ForestGreen} \beta },c_1,\dots,c_M) +\omega_1+\dots+\omega_L=
=\operatorname{inv} (a_1,\dots,a_K,b_1, \dots,b_{L},{\color{ForestGreen} \beta },{\color{RubineRed} \alpha },c_1,\dots,c_M) +\omega_1+\dots+\omega_L+\omega_{L+1}
=\operatorname{inv} (a_1,\dots,a_K,b_1, \dots,{\color{ForestGreen} \beta },b_{L},{\color{RubineRed} \alpha },c_1,\dots,c_M) + +\omega_1+\dots+\omega_L+\omega_{L+1}+\omega_{L+2}=
=\dots=
=\operatorname{inv} (a_1,\dots,a_K,{\color{ForestGreen} \beta },b_1, \dots,b_{L},{\color{RubineRed} \alpha },c_1,\dots,c_M) +\omega_1+\dots+\omega_{2L+1}= \operatorname{inv} \Xi + нечетное \, .

Т

Теорема 3. Число четных перестановок из n элементов равно числу нечетных (и равно n!/2).

Доказательство. Действительно, упорядочим все множество перестановок таким образом, чтобы каждая следующая получалась из предшествующей с помощью одной транспозиции. Возможность такого упорядочения доказывается индукцией по n.

Для n=2 это тривиально: (1,2) и (2,1).

Предположим, что утверждение верно для перестановок из (n-1)-го элемента, т.е. их можно расположить в требуемом порядке.

Все множество перестановок из n элементов разобьем на подмножества по тем же правилам, что и в доказательстве теоремы 1. На основании индукционного предположения перестановки из первого подмножества

(\alpha_1,\dots,\alpha_{n-1},n)

можно упорядочить нужным нам образом. В получившейся последовательности перестановок возьмем последнюю и переставим местами n и n-1; в результате получим перестановку из второго подмножества

(\beta_1,\dots,\beta_{n-1},n-1) \, .

По индукционному предположению и эти перестановки можно упорядочить так, как требуется. В последней получившейся переставим местами n-1 и n-2, получим перестановку из третьего класса

(\gamma_1,\dots,\gamma_{n-1},n-2)

и т.д.

Таким способом можно упорядочить все n! перестановок. По теореме 2 соседние перестановки должны иметь разные четности.

Т

Теорема 4. Если

(\alpha_1,\alpha_2,\dots,\alpha_n) \quad u \quad (\beta_1,\beta_2,\dots,\beta_n)

произвольные перестановки элементов \{1,2,\dots,n \}, то в разложении определителя

\det A=\sum (-1)^{\operatorname{inv}(\alpha_1,\alpha_2,\dots,\alpha_n)}a_{1\alpha_1}a_{2\alpha_2} \times \dots \times a_{n\alpha_n}

обязательно встретится слагаемое

(-1)^{\operatorname{inv} (\alpha_1,\alpha_2,\dots,\alpha_n)+\operatorname{inv} (\beta_1,\beta_2,\dots,\beta_n)} a_{\alpha_1 \beta_1} a_{\alpha_2 \beta_2} \times \dots \times a_{\alpha_n \beta_n} \, .


2019/02/25 23:47 редактировал au