パーミュテーション(並び替え)で、\(j\)-番目項目を\(l\)-番目位置へ移動するもの、に対して、サイン(符号)は、対応する、\(j\)-番目項目が欠けたパーミュテーション(並び替え)のサイン(符号)の\((-1)^{l - j}\)倍であることの記述/証明
話題
About: セット(集合)
この記事の目次
開始コンテキスト
- 読者は、パーミュテーション(並び替え)のサイン(符号)の定義を知っている。
ターゲットコンテキスト
- 読者は、任意のパーミュテーション(並び替え)で、\(j\)-番目項目を\(l\)-番目位置へ移動するもの、に対して、当該サイン(符号)は、対応する、\(j\)-番目項目が欠けたパーミュテーション(並び替え)のサイン(符号)の\((-1)^{l - j}\)倍であるという命題の記述および証明を得る。
オリエンテーション
本サイトにてこれまで議論された定義たちの一覧があります。
本サイトにてこれまで議論された命題たちの一覧があります。
本体
1: 構造化された記述
ここに'構造化された記述'のルールたちがある。
エンティティ(実体)たち:
\((1, ..., n)\):
\(\sigma\): \(: (1, ..., n) \mapsto (\sigma_1, ..., \sigma_n)\), \(\in \{\text{ 全てのパーミュテーション(並び替え)たち }\}\)で、\(\sigma_l = j\)を満たすもの
\((1, ..., \widehat{j}, ..., n)\):
\(\sigma'\): \(: (1, ..., \widehat{j}, ..., n) \mapsto (\sigma_1, ..., \widehat{\sigma_l}, ..., \sigma_n)\), \(\in \{\text{ 全てのパーミュテーション(並び替え)たち }\}\)
//
ステートメント(言明)たち:
\(sgn \sigma = (-1)^{l - j} sgn \sigma'\)
//
2: 証明
全体戦略: ステップ1: \(j \lt l\)だと仮定し、本命題が成立することを見る; ステップ2: \(l \lt j\)だと仮定し、本命題が成立することを見る; ステップ3: \(j = l\)だと仮定し、本命題が成立することを見る。
ステップ1:
\(j \lt l\)であると仮定しよう。
\(\sigma\)は、\((1, ..., j - 1, j, j + 1, ..., l - 1, l, l + 1, ..., n) \mapsto (1, ..., j - 1, l, j + 1, ..., l - 1, j = \sigma_l, l + 1, ..., n) \mapsto (\sigma_1, ..., \sigma_{j - 1}, \sigma_j, \sigma_{j + 1}, ..., \sigma_{l - 1}, j = \sigma_l, \sigma_{l + 1}, ..., \sigma_n)\)である。
その第1パーミュテーション(並び替え)は\(-1\)である、なぜなら、それは、単に\(j\)と\(l\)をスワップしているだけ。
その第2パーミュテーション(並び替え)のサイン(符号)を\((-1)^m\)としよう。
\(\sigma'\)は、\((1, ..., j - 1, \widehat{j}, j + 1, ..., l - 1, l, l + 1, ..., n) \mapsto (1, ..., j - 1, l, j + 1, ..., l - 1, \widehat{j = \sigma_l}, l + 1, ..., n) \mapsto (\sigma_1, ..., \sigma_{j - 1}, \sigma_j, \sigma_{j + 1}, ..., \sigma_{l - 1}, \widehat{j = \sigma_l}, \sigma_{l + 1}, ..., \sigma_n)\)である。
その第1パーミュテーション(並び替え)のサイン(符号)は\((-1)^{l - 1 - j}\)である、なぜなら、\(l\)は最初に\(l - 1\)とスワップされ、次に、\(l - 2\)、...、\(j + 1\)とスワップされ、したがって、\(l - 1, ..., j + 1\)と\(l - 1 - j\)回スワップされる: \(l\)は単に\(\widehat{j}\)とスワップするというわけにはいかない、なぜなら、\(\widehat{j}\)は存在せず、\(l\)は、存在しないものとスワップできない。
その第2パーミュテーション(並び替え)のサイン(符号)は\((-1)^m\)である、なぜなら、\(\sigma_l\)はどちらにせよ移動されない。
したがって、\(sgn \sigma = (-1) (-1)^m\)および\(sgn \sigma' = (-1)^{l - 1 - j} (-1)^m\)。
したがって、\((-1)^m = sgn \sigma' (-1)^{- l + 1 + j}\)、したがって、\(sgn \sigma = (-1) sgn \sigma' (-1)^{- l + 1 + j} = (-1)^{- l + j + 2} sgn \sigma' = (-1)^{- l + j + 2 l - 2 j} sgn \sigma' = (-1)^{l - j} sgn \sigma'\)。
ステップ2:
\(l \lt j\)であると仮定しよう。
本ロジックはステップ1と平行的なものであり、結果は容易に予期できるが、私たちはそれを勤勉に行なおう。
\(\sigma\)は、\((1, ..., l - 1, l, l + 1, ..., j - 1, j, j + 1, ..., n) \mapsto (1, ..., l - 1, j = \sigma_l, l + 1, ..., j - 1, l, j + 1, ..., n) \mapsto (\sigma_1, ..., \sigma_{l - 1}, j = \sigma_l, \sigma_{l + 1}, ..., \sigma_{j - 1}, \sigma_j, \sigma_{j + 1}, ..., \sigma_n)\)である。
その第1パーミュテーション(並び替え)のサイン(符号)は\(-1\)である、なぜなら、それは単に\(j\)と\(l\)をスワップしているだけである。
その第2パーミュテーション(並び替え)のサイン(符号)を\((-1)^m\)としよう。
\(\sigma'\)は、\((1, ..., l - 1, l, l + 1, ..., j - 1, \widehat{j}, j + 1, ..., n) \mapsto (1, ..., l - 1, \widehat{j = \sigma_l}, l + 1, ..., j - 1, l, j + 1, ..., n) \mapsto (\sigma_1, ..., \sigma_{l - 1}, \widehat{j = \sigma_l}, \sigma_{l + 1}, ..., \sigma_{j - 1}, \sigma_j, \sigma_{j + 1}, ..., \sigma_n)\)。
その第1パーミュテーション(並び替え)のサイン(符号)は\((-1)^{j - 1 - l}\)である、なぜなら、\(l\)は最初に\(l + 1\)とスワップされ、次に、\(l + 2\)、...、\(j - 1\)とスワップされ、したがって、\(l + 1, ..., j - 1\)と\(j - 1 - l\)回スワップされる: \(l\)を単に\(\widehat{j}\)とスワップするというわけにはいかない、なぜなら、(\widehat{j}\)は存在せず\(l\)は存在しないものとスワップすることはできない。
その第2パーミュテーション(並び替え)のサイン(符号)は\((-1)^m\)である、なぜなら、\(\sigma_l\)はいずれにせよ移動されない。
したがって、\(sgn \sigma = (-1) (-1)^m\)および\(sgn \sigma' = (-1)^{j - 1 - l} (-1)^m\)。
したがって、\((-1)^m = sgn \sigma' (-1)^{- j + 1 + l}\)、したがって、\(sgn \sigma = (-1) sgn \sigma' (-1)^{- j + 1 + l} = (-1)^{- j + l + 2} sgn \sigma' = (-1)^{l - j} sgn \sigma'\)。
ステップ3:
\(j = l\)であると仮定しよう。
本ロジックはステップと平行的であり結果は容易に予期できるが、それを勤勉に行なおう。
\(\sigma\)は、\((1, ..., j - 1, j, j + 1, ..., n) \mapsto (\sigma_1, ..., \sigma_{j - 1}, j = \sigma_j, \sigma_{j + 1}, ..., \sigma_n)\)である。
当該パーミュテーション(並び替え)のサイン(符号)を\((-1)^m\)としよう。
\(\sigma'\)は、\((1, ..., j - 1, \widehat{j}, j + 1, ..., n) \mapsto (\sigma_1, ..., \sigma_{l - 1}, \widehat{j = \sigma_j}, \sigma_{j + 1}, ..., \sigma_n)\)である。
当該パーミュテーション(並び替え)のサイン(符号)は\((-1)^m\)である、なぜなら、\(\sigma_j\)はいずれにせよ移動されない。
したがって、\(sgn \sigma = (-1)^m\)および\(sgn \sigma' = (-1)^m\)。
したがって、\(sgn \sigma = sgn \sigma' = sgn \sigma' (-1)^0 = sgn \sigma' (-1)^{l - j}\)。