§ 3. 置換とその符号

§ 3. ^{置換とその符号}

1,2,· · ·, n の順列は見方を変えると、集合 {1,2,· · ·, n} ^から{1,2,· · · , n} ^{への全単射とみ} なすことができる。この全単射はn文字の置換と呼ばれる。ここではこの置換の性質を詳しく 調べる。後半では各置換に対して +1か−1の符号を定めることができることを説明し、順列 の転倒数との関係を明らかにする。

● 3 - 1 : 置換

集合 {1,2,· · · , n}^から {1,2,· · · , n} ^{への全単射を} n^{文字の置換という。}

例 3 - 1 - 1 1,2,3,4^の順列 2,3,1,4 ^は

17−→2, 27−→3, 37−→1, 47−→4

という集合{1,2,3,4} 上の全単射、すなわち、4 文字の置換とみなすことができる。逆に、

σ(1) = 4, σ(2) = 2, σ(3) = 1, σ(4) = 3

によって定義される4文字の置換σ :{1,2,3,4} −→ {1,2,3,4}^{が与えられれば、}1,2,3,4の順 列4,2,1,3が定まる。

n^{文字の置換}σ を表わすには、次のような表を用いると便利である：

( 1 2 · · · n

σ(1) σ(2) · · · σ(n) )

.

この表においては、上段の数字と下段の数字の組^「_σ(i)」ⁱ が重要で、これをひと固まりとし て、並べ方の順番を変えた表は同じ置換を表わすと約束する。

例 3 - 1 - 2 σ=

(1 2 3 4 4 2 1 3 )

はσ=

(2 4 3 1 2 3 1 4 )

と表わすこともでき、どちらも σ(1) = 4, σ(2) = 2, σ(3) = 1, σ(4) = 3

により定まる 4 ^{文字の置換}σ:{1,2,3,4} −→ {1,2,3,4} ^{を表わす。}

n文字の置換全体からなる集合を S_n という記号で表わす。

２つの置換σ ∈Sm とτ ∈Sn が写像として等しいときσ =τ と表わす。すなわち、

σ=τ ⇐⇒

{• n=m^、かつ、

• ^すべてのi= 1,· · ·, n についてσ(i) =τ(i).

● 3 - 2 : 置換の積

２つのn^{文字の置換}σ=

( 1 2 · · · n

σ(1) σ(2) · · · σ(n) )

とτ =

( 1 2 · · · n

τ(1) τ(2) · · · τ(n) )

から、

στ :=

( 1 2 · · · n

σ(τ(1)) σ(τ(2)) · · · σ(τ(n)) )

という n ^{文字の置換} στ を定義することができる。これを σ ^と τ ^{の積という。積}στ ^は合成 写像 σ◦τ :{1,2,· · · , n} −→ {1,2,· · ·, n} ^{のことに他ならない。}

例 3 - 2 - 1 σ =

(1 2 3 4 4 2 1 3

) , τ =

(1 2 3 4 4 3 1 2 )

∈S4 について、στ =

(1 2 3 4 3 1 4 2 )

.

線形代数４・第3回(2022年10月10日)授業用アブストラクト

● 3 - 3 : ^{逆置換と恒等置換}

n文字の置換σ =

( 1 2 · · · n

σ(1) σ(2) · · · σ(n) )

に対して、各 σ(i) をi に写すような置換 (σ(1) σ(2) · · · σ(n)

1 2 · · · n

)

を考えることができる。この置換をσ ^{の逆置換といい、記号} σ^{−1 で表わす。}

例 3 - 3 - 1 置換 σ =

(1 2 3 2 3 1 )

の逆置換はσ⁻¹ =

(2 3 1 1 2 3

)

=

(1 2 3 3 1 2 )

である。

1 から nまでの各数字 i に対して、i自身を対応させる n文字の置換(つまり、{1,· · ·, n} 上の恒等写像)をSn における恒等置換といい、記号 1_n で表わす( eで表わすこともある)：

1n=

(1 2 · · · n 1 2 · · · n )

.

前後の文脈から、数字の 1 と混乱する恐れのない場合には、1n を単に1 ^{で表わす。任意の} 置換σ ∈S_n に対して、σ1_n= 1_nσ =σ, σσ⁻¹=σ⁻¹σ = 1_n が成り立つ。

● 3 - 4 : ^巡回置換

巡回置換とは、ある異なるk 個(k≥2)の数字i₁,· · · , i_k を

i1 7−→i2, i27−→i3, · · ·, ik−1 7−→ik, ik7−→i1

のように写し、それ以外の数字は動かさないような置換のことをいう。このような置換を(i₁i₂ · · · i_k) のように表わす。k を巡回置換(i₁ i₂ · · · i_k) の長さという。

例 3 - 4 - 1 S5 において、(2 3 4 5) =

(1 2 3 4 5 1 3 4 5 2

) .

定理 3 - 4 - 2

任意の置換は(互いに共通の文字を含まない)巡回置換の積で表わされる。

上の定理を例を用いて説明する。

例 3 - 4 - 3 7 文字の置換σ =

(1 2 3 4 5 6 7 4 7 5 3 1 6 2 )

を互いに共通の文字を含まない巡回 置換の積の形に表わそう。まず、σ を次々に合成していったときに、1 がどのような数字に写 されていくのかを追跡すると、次のようになる。

1−−−−→^σ 4−−−−→^σ 3−−−−→^σ 5−−−−→^σ 1

次に、上の中に登場しない数字、例えば、2 について同様の考察を行なうと、

2−−−−→^σ 7−−−−→^σ 2.

今までに登場しなかった数字は 6 ^{のみであり、これは}σ により動かされない。したがって、

σ= (7 2)(1 4 3 5)

のように表わされる。 □

● 3 - 5 : 互換

(i j) の形で表される巡回置換、すなわち、長さ 2の巡回置換を互換と呼ぶ。

例 3 - 5 - 1 S4 における互換 (13), (23), (14), (12)^の積(13)(23)(14)(12)^は 4^{文字の置換} (1 2 3 4

1 4 2 3 )

に等しい。実際、σ = (13)(23)(14)(12)とおくと、σ の下で、1は 1−−−−−→⁽¹²⁾ 2−−−−−→⁽¹⁴⁾ 2−−−−−→⁽²³⁾ 3−−−−−→⁽¹³⁾ 1

のように写される(^{合成をとる順番に注意})^{。同様に、}2,3,4 ^{はそれぞれ}σ ^によって 2,1,3^に写

されることがわかる。 □

巡回置換(i1 i2 · · · i_k) は、次のように、互換の積に表わされる。

(3 - 5 a) (i1 i2 · · · i_k) = (i1 i2)(i2 i3)· · ·(i_k−2 i_k−1)(i_k−1 i_k).

このことと[^定理3 - 4 - 2]^{より、次を得る。}

定理 3 - 5 - 2

任意の置換は有限個の互換の積として書くことができる。

n文字の置換は上の定理より互換の積として表わされるが、その表わし方には一意性はない。

例 3 - 5 - 3 σ =

(1 2 3 4 5 4 1 5 2 3 )

について、σ= (34)(23)(12)(45)(34) = (35)(14)(24).

● 3 - 6 : 置換の符号

n≥2^とする。n ^{文字の置換}σ∈Sn に対して、

(3 - 6 a) sgnσ:= ∏

1≤i<j≤n

σ(j)−σ(i)

j−i ∈ Q

とおく。ここで、 ∏

1≤i<j≤n

は1≤i < j ≤nを満たすすべての整数の組(i, j) に渡って積をとる ことを意味する。sgnσ はσ を1,2,· · ·, nの順列とみなしたとき、転倒数 N(σ) の偶奇に一致 する。すなわち、

補題 3 - 6 - 1

任意の置換σ∈Sn に対して、sgnσ= (−1)^N(σ). (証明)

∏

1≤i<j≤n

(σ(j)−σ(i)) = (−1)^N(σ) ∏

1≤i<j≤n

(j−i) となることを示せばよい。転倒数の定義より、

N(σ) =♯{ (σ(i), σ(j))|1≤i < j≤n, σ(i)> σ(j) } が成り立つ(♯ は集合の元の個数を表わす)。

S1 ={ (σ(i), σ(j))|1≤i < j ≤n, σ(i)< σ(j)}, S2 ={ (σ(i), σ(j))|1≤i < j ≤n, σ(i)> σ(j)}

とおくと、S1∪ S2 ={(σ(i), σ(j)) |1≤i < j≤n },S1∩ S2 =∅を満たす。したがって、

∏

1≤i<j≤n

(σ(j)−σ(i)) =( ∏

(i^′,j^′)∈S1

(j^′−i^′))( ∏

(i^′,j^′)∈S2

(j^′−i^′) )

= (−1)^N(σ)( ∏

(i^′,j^′)∈S1

(j^′−i^′))( ∏

(i^′,j^′)∈S2

(i^′−j^′)

) · · · ·(∗)

線形代数４・第3回(2022年10月10日)授業用アブストラクト

ここで、写像 f :{ (σ(i), σ(j))|1≤i < j ≤n} −→ { (i, j)|1≤i < j ≤n }^を f(

(i^′, j^′))

= {

(i^′, j^′) ((i^′, j^′)∈ S1 のとき), (j^′, i^′) ((i^′, j^′)∈ S2 のとき) により定義する。f は全単射である。したがって、(∗) = (−1)^N(σ) ∏

1≤i<j≤n

(j−i) を得る。 □ 補題 3 - 6 - 2

σ ^{が互換のとき、}sgnσ =−1^である。

(^証明)

σ = (k l) (1≤k < l≤n) ^とおく。σ を順列だと思って転倒数を計算すると、nk+1 =· · ·= n_l−1= 1, n_k =l−kであり、これら以外のn_i は0である。故に、N(σ) = (l−k−1) + (l−k) = 2(l−k)−1 であり、sgnσ = (−1)^2(l−k)−1 =−1 である。 □

● 3 - 7 : ^{置換の符号の性質}

置換の符号は次の性質を持つ。

定理 3 - 7 - 1

任意のσ, τ ∈Sn に対して、次が成り立つ。

(1) sgn(στ) = (sgnσ)(sgnτ).

したがって、σ =σ₁σ₂· · ·σ_k(各i= 1,2,· · · , kに対してσ_i は互換)のとき、sgnσ= (−1)^k. (2) sgn (1_n) = 1.

(3) sgn(σ⁻¹) = sgnσ.

(^証明)

(1) まず、{1,· · ·, n} の相異なる２元からなる部分集合 {i, j} (i ̸=j) の全体 S ^{を考える。}

I ={i, j} ∈ S ^および σ, τ ∈Sn に対して、

a_I(σ, τ) := σ(j)−σ(i) τ(j)−τ(i) とおくと、sgnσ は次のように表わすことができる：sgnσ = ∏

I∈SaI(σ,1n).

写像 I ={i, j} ∈ S 7−→τ(I) ={τ(i), τ(j)} ∈ S ^はS 上の全単射であるから、

sgnσ = ∏

I∈Sa_τ(I)(σ,1n) = ∏

I∈SaI(στ, τ) と書くこともできる。したがって、

sgn (στ) =∏

I∈S

a_I(στ,1_n) = ∏

I∈S

(a_I(στ, τ)a_I(τ,1_n))

=(∏

I∈S

a_I(στ, τ))(∏

I∈S

a_I(τ,1_n))

= (sgnσ)(sgnτ)

となる。特に、σ∈Sn がσ=σ1σ2· · ·σk(^各i= 1,2,· · · , k^に対してσi は互換) ^{と表わされる} とき、[^補題3 - 6 - 2]^{を用いて、}sgnσ = sgn(σ1σ2· · ·σ_k) = sgn(σ1)sgn(σ2)· · ·sgn(σ_k) = (−1)^k となることがわかる。

(2)置換の符号の定義により、直ちに sgn (1_n) = 1とわかる。

(3) (1)^と(2)^より、sgn(σ⁻¹)sgnσ= sgn(σ⁻¹σ) = sgn (1n) = 1^{を得る。したがって、}sgn(σ⁻¹) と sgnσ は同符号である。また、(1)の後半部分の主張により、sgnσ ∈ {±1} ^{であるから、}

sgn(σ⁻¹) = sgnσ であることがわかる。 □

注意. (1)から、置換を互換の積で表わしたときの互換の個数の偶奇は一定なことがわかる。

線形代数４事前練習用演習問題

pre3-1. ^次の 4^{文字の置換} σ ^とτ ^の積 τ σ ^{を求めよ。}

σ=

(1 2 3 4 2 3 4 1 )

, τ =

(1 2 3 4 4 3 2 1 )

pre3-2. 7^{文字の置換}

σ =

(1 2 3 4 5 6 7 4 7 5 3 1 6 2 )

について以下の問いに答えよ。

(1)σ を互いに共通の文字を含まない巡回置換の積の形に表わせ。

(2)σ ^{を互換の積で表わせ。}

(3) sgnσ を求めよ。

ヒントと略解（最初は見ずに解答してください）

(τ σ)(1) =τ( σ(1))

=τ(2) = 3, pre3-1.

(τ σ)(2) =τ( σ(2))

=τ(3) = 2, (τ σ)(3) =τ(

σ(3))

=τ(4) = 1, (τ σ)(4) =τ(

σ(4))

=τ(1) = 4 より、τ σ=

(1 2 3 4 3 2 1 4 )

.

pre3-2. (1) [例3 - 4 - 3]と同様にして、巡回置換の積に分解することができる。

σ= (1 4 3 5)(2 7)

(2) (3 - 5 a)を利用して、巡回置換を互換の積に書き換える。

σ= (1 4)(4 3)(3 5)(2 7) となる。

(3) (2)^より σ ^は4 個の互換の積で表わされるから、sgnσ= (−1)⁴ = 1 ^である。

線形代数４・第

3

回

(2022

年

10

月

10

日

)

演習問題事前練習シート

※このシートをA4片面１枚に印刷して、授業前までに事前練習用演習問題の解答をここに書 いてください。略解を参照して答え合わせをしたものを授業に持参してください。但し、この シートは提出せず、各自で保管してください。

学 籍 番 号 氏 名

Q1. (1)n文字の置換とは何か。定義を述べよ。

(2)n 文字の置換の全体からなる集合をどのような記号で表わすか？

(3)^{恒等置換と呼ばれる} n^{文字の置換}1n とはどのような置換のことをいうか。

(4) 2つの n文字の置換σ とτ が等しいことを示すには、何を確かめればよいか。

(5)n 文字の置換は 1から nまでの数字の順列 1対 1に対応する。

(i) 4^{文字の置換}σ =

(1 2 3 4 3 4 2 1

)

に対応する順列は である。

(ii) ^順列 5,4,3,2,1 ^{に対応する置換は である。}

Q2. 4文字の置換 σ=

(1 2 3 4 4 3 2 1 )

, τ =

(1 2 3 4 2 4 1 3 )

について、

στ = , τ σ = , σ⁻¹=

Q3. (1) 5 文字の置換における巡回置換σ= (1 2 3 4) はどのような置換を表わすか。

(2)互換 (i j) とはどのような置換を意味するか。

(3)巡回置換 (i₁ i₂ · · · i_k) はどのような互換の積で表わされるか。

Q4. n≥2 とし、σ をn文字の置換とする。

(1)符号 sgnσ はどのように定義されるか？sgnσ =

(2)符号 sgnσ は、σ に対応する順列の転倒数N(σ) からどのように求められるか？

sgnσ=

(3)σ が互換のとき、sgnσ= であり、一般に、σ =σ₁σ₂· · ·σ_k (各 σ_i は互換) と 表わされるとき、sgnσ= である。

(4) sgn (1n) = ^であり、sgnσ⁻¹ = ^である。

Q5. ^第3回の授業で学んだ事柄について、わかりにくかったことや考えたことなどがあれば、

書いてください。