§ 3. 置換とその符号

Download (0)

Full text

(1)

§ 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)」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文字の置換全体からなる集合を Sn という記号で表わす。

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

σ=τ ⇐⇒

{ n=m、かつ、

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

3 - 2 : 置換の積

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 )

.

(2)

線形代数4・第3(20221010日)授業用アブストラクト

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 )

の逆置換はσ−1 =

(2 3 1 1 2 3

)

=

(1 2 3 3 1 2 )

である。

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

1n=

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

.

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

3 - 4 : 巡回置換

巡回置換とは、ある異なるk 個(k2)の数字i1,· · · , ik

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

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

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)

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−−−−−→(12) 2−−−−−→(14) 2−−−−−→(23) 3−−−−−→(13) 1

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

されることがわかる。 □

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

(3 - 5 a) (i1 i2 · · · ik) = (i1 i2)(i2 i3)· · ·(ik2 ik1)(ik1 ik).

このことと[定理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

とおく。ここで、 ∏

1i<jn

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

補題 3 - 6 - 1

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

1i<jn

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

1i<jn

(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 =∅を満たす。したがって、

1i<jn

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

(i,j)∈S1

(j−i))( ∏

(i,j)∈S2

(j−i) )

= (1)N(σ)( ∏

(i,j)∈S1

(j−i))( ∏

(i,j)∈S2

(i−j)

) · · · ·()

(4)

線形代数4・第3(20221010日)授業用アブストラクト

ここで、写像 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(σ)

1i<jn

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

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

(証明)

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

3 - 7 : 置換の符号の性質

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

定理 3 - 7 - 1

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

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

したがって、σ =σ1σ2· · ·σk(各i= 1,2,· · · , kに対してσi は互換)のとき、sgnσ= (1)k. (2) sgn (1n) = 1.

(3) sgn(σ1) = sgnσ.

(証明)

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

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

aI(σ, τ) := σ(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

aI(στ,1n) = ∏

I∈S

(aI(στ, τ)aI(τ,1n))

=(∏

I∈S

aI(στ, τ))(∏

I∈S

aI(τ,1n))

= (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 (1n) = 1とわかる。

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

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

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

(5)

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

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)4 = 1 である。

(6)

線形代数4・第

3

(2022

10

10

)

演習問題事前練習シート

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

(7)

学 籍 番 号 氏 名

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 )

について、

στ = , τ σ = , σ1=

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

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

(3)巡回置換 (i1 i2 · · · ik) はどのような互換の積で表わされるか。

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

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

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

sgnσ=

(3)σ が互換のとき、sgnσ= であり、一般に、σ =σ1σ2· · ·σk (各 σi は互換) と 表わされるとき、sgnσ= である。

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

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

書いてください。

Figure

Updating...

References

Related subjects :