代数幾何 I 古津先生 (2006/12/21)

# 最初の演習の続き ( 1 問だけのこってた.. )

11.
	S_n \ni \sigma :-> A_{\sigma}
		(\sigma{i},i} 成分が 1 ( i = 1..n )
			      他は 0

	[例]
		\sigam = ( 1 2 3 4 )
			   2 3 3 1
	の時、

		A_{\sigam} = ( 0 0 0 1 ) = ( e_{\sigma{1}, .., e_{\sigma{4} )
			       1 0 0 0
			       0 0 1 0
			       0 1 0 0

	となる。

	イ) A_{\sigam} は直交行列
		# 直交行列は、実ユニタリ行列のこと。
		# 成分は、すべて 0 と 1 すなわち、実数なので、ユニタリを示せばよい

		A_{\sigam}^*A_{\sigam} = E

	を示せばよい。

		# ちなみに、A_{\sigam} が実ベクトルなので、A^* = ^tA であることに注意

		A_{\sigam} は元々、単位縦ベクトルの並びなので、随伴(つまり転置)を取ると、		単位横ベクトルの並びになる。


		A_{\sigam}^*A_{\sigam}
		         e_{\sigma(1)}
			 e_{\sigma(2)}
		=	( ...          ) ( e_{\sigma(1)},..,e_{\sigma(n)} }
			 e_{\sigma{n)}
		

		=	( ( e_{\sigma{i)}, e_{\sigma{j)} )

		=	( \delta_{i,j} )
		=	E

	ロ) A_{\sigma}A_{\tau}=A_{\sigma\tau}

		# ロを示す前に、ちょっと準備

		B = ( b_{i,j} ), A_{\tau}, \tau \in S_n

		の時、

			BA_{\tau} = ( b_{\tau(1)}, b_{\tau(2)}, .., b_{\tau(n)} )

		# つまり、A_{\tau} は、列を入れ替える行列になっている。

	A_{\sigma}A_{\tau}
	=	(e_{\sigma(1)},e_{\sigma(2)},..,e_{\sigma(n)})A_{\tau}
		# ここで、上の性質を考えると、A_{\tau} は行を入れ替える。すなわち
	=	(e_{\sigma\tau(1)},e_{\sigma\tau(2)},..,e_{\sigma\tau(n)})
		よって、
	=	A_{\sigma\tau}

	ハ) |A_{\sigma}| = sgn \sigma
		# まず、互換の場合を示す

		\sigma = ( i,j ) の、

		A_{\sigma} = ( e_1, .., e_j, .., e_i, .. e_n )
					↑        ↑
					i 行目    j 行目
	よって、

		|A_{\sigma}| =   det( e_1, .., e_j, .., e_i, .. e_n )
			     = - det( e_1, .., e_i, .., e_j, .. e_n )
				# i 列目と j 列目を交換したので -1 が前に出る
			     = - |E|
			     = -1
			     = sgn \sigma
			     	# 互換の sgn は、-1 なので..

	[一般の場合]
		# 一般の置換は、互換の積に表せる
			\sigma = \tau_1 \tau_2 .. \tau_k

		A_{\sigma} = A_{\tau_1} A_{\tau_2} .. A_{\tau_k}
	よって、
		|A_{\sigma}| = |A_{\tau_1}| |A_{\tau_2}| .. |A_{\tau_k}|
			# 行列
			     = sgn\tau_1 sgn\tau_2 .. sgn\tau_k
			     = sgn \tau_1 \tau_2 .. \tau_k
			     = sgn \sigma
==

# 今日のこのあとは、代機とは無関係に、卒業演習の紹介

三山崩し (ニム)

	7, 5, 3, の小石の山を作る。
	そこから、石を取って行く ( 山を崩す ) ので、三山崩し

	プレイヤーは二人 ( 三人以上だと、問題が面倒になるので.. )

	[規則]
		交互にプレイする
		一つの山から 1 個以上の石を取る ( 上限はない )
		最後の 1 つを取った者が勝ち ( 正規形 )
			# 最後をとったものが負けというルール ( 逆形 ) もある
			# 逆形の方は、卒研で行うので、今日は正規形

		○ この問題は、確率要素がないので、必勝手順がある

		この問題は、
			先手必勝 (×)
			後手必勝 (○) (良形)
		か ?

		より、一般に、
			( l, m, n )
		はどっち ? という問題を考える

	実は、(7,5,3) は、実は先手必勝

	どのような場合に、先手必勝になるかを考えてみよう。

	# [注意]
	#	先手必勝 => 「いい加減にうってもよい」という意味ではなく、「つねに良い手をえらべばかてる」の意味
	#	後手必勝 => 相手が何をうってもかてるてがある

	# どうかんがえるか ?	


	(0,0,0) ○	# すでに、先手は負けている
	(l,0,0) ×	# 全部とれば先手の勝ち

	(l,l,0) ○	# まねっこができるので、後手の勝ち
	(l,m,0) ×	# 数が違うので、数をそろえれば良い。よって先手の勝ち

	(1,1,1) ×
	(2,1,1) ×
	(2,2,1) ×
	(2,2,2) ×
	(l,l,m) ×	# 同じものが二つある場合は、残りの山を全部取ればよい

	三つとも異なる場合だけが問題

	# 一番簡単な場合を考える

	(1,2,3)
		(2,2,1)
		(3,2,0) -> (2,2,0)

		(0,2,1)
		(3,1,1) -> (0,1,1)

		(3,0,1)
		(1,2,1) -> (1,0,1)

				↑全部○
			よって
		↑全部×
			よって
	↑全部○ということに..

# 全部、しらみつぶしでやってもよいが、大変なので、すこし系統的に考えてみる

	[ゲームの性質]
		1. (0,0,0) は ○ ( 正規形なので.. )
		2. ○ -> ○ となる手はない ( ○の定義より )
		3. × -> ○ となる手はある ( ×の定義より )
		4. □ -> ○ ならば、□は ○
		5. □ からどうやっても×しかでない場合は、実は□は○

	# ゲームの話しだが、やっぱり数学的にできるので..

	[定理 1]
		(m,n) に対して、(l,m,n) が ○ になる l が、ただ一つ存在する

	proof)
	# まず、唯一性を示す
		(l,m,n) ○
		(l',m,n) ○
	(l>l')とする。
		(l,m,n) -> (l',m,n)
	とできるが、これは「○ -> ○」なので、矛盾。

	# 次に存在 ( m + n に関する帰納法による )

	0) m + n = 0 の時は、(0,0,0) なので、存在する
	p) m + n = p の場合
		(l,m,n) の内、m,n から石をとり、m'+n' とすると、
		その結果として m'+n' は、p より小くなるので、
			(l,m',n')
		が○となる l が、それぞれ存在する ( 帰納法の仮定 )

		(l_1,     m-1, n)	○
		(l_2,     m-2, n)	○
		(l_m,     m-m, n)	○
		(l_{m+1}, m,   n-1)	○
		(l_{m+n}, m,   n-n)	○

	このような l_k とはことなる最小の数を l とすると、実は、

		(l,m,n) が○

	を示す。
		proof)
			(l,m-i,n) ×	(なぜなら (l,m-i,n) は×だった )
			(l,m,n-i) ×	(なぜなら (l,m,n-i) は×だった )
			(l',m,n) ×
				l'=l_i ( 1 <= i <= m -> (l_i,m-i,n) が○
				l'=l_{m+i} ( 1 <= i <= n ) -> (l_i,m-i,n) が○

	定義 (l.m,n) が○の時
		l = m ^ n
	とする。

	[定理 1.2]
		m ^ n <= m + n

		proof)
			0 ^ 0 = 0
			m + n >= 1 の時 m ^ n = l <= m + n

		系
			| m - n | <= m ^ n
			proof)
				(l.m,n) が ○なら
				(m,l.n), (n,l.m) も○
			よって、
				m = l ^ n	 m < l + n
				n = l ^ m 	 n < l + m
			よって、
				|m-n| <= l

	[定理 1.3] ( 単位元 )
		0 ^ m = m
		m ^ 0 = m
		proof)
			(m,m,0), (m,m,0) は○

		系
			m ^ m = 0

	[定理 1.4] ( 交換法則 )
		m ^ n = m ^ n

	[定理 1.5] (逆元)
		n,n に対して
			l ^ m = n となる l が唯一つある。
		proof)
			m ^ n = l とおくと
				( l, m, n ) は○
				( n, l, m ) は○
			よって、
				l ^ m = n

	[定理 1.6] (結合律)
		( l ^ m ) ^ n = l ^ ( m ^ n )

		# 証明はできるが、面倒なので、今回はサボる

	# 定理 1.1 - 1.6 より ( Z_{>0} ^ ) は、加法群

	## 群にかんする話題は、来年以降、学ぶ

	## ここまでやっても、なかなか法則性がみえないので、ちょっと具体例をやってみる

		0^1 = 1
		1^1 = 1
		2^1 = 3
		3^1 = 2

	# なんとなく、規則性質がみえてきたので、それを帰納法で証明してしまう !!

	[定理 1.7]
		p = 2n		の時	p ^ 1 = p + 1
		p = 2n + 1	の時	p ^ 1 = p - 1

		proof) # n に関する帰納法

		0,1) n = 0,1 の時は、上記の具体例で O.K
		n)
			q = 2(n+1) とする
				q+1 = q-1, q, q+1
			のいずれか
				(q,q,1) ×なので、 q ではない
			仮定より
				2n^1 = 2n+1
			よって、
				(2n+1,2n,1) は○
			よって、
				(2n+1,2n+2,1) は×
			つまり、	( q-1, q, 1) は×
			よって、
				q-1 でない
			よって、
				q^1 = q+1

		(q+1)^1 = q

		(2n_3)^1 = 2n+2

	# 三つ山が異なっても、残りが一つが 1 なら、必勝法がわかった

	# 同様に 2 の場合も考える
	#	具体的な例を考えて、規則性を探し、帰納法で証明

		0^2 = 2
		1^2 = 2
		2^2 = 0
		3^2 = 1
		4^2 = 6
		5^2 = 7
		6^2 = 4
		7^2 = 5

	[命題]
		p = 4n, 4n+1
			p^2 = p+2
		p = 4n+2, 4n+3
			p^2 = p-2

		# 証明は、帰納法で

	演算表を作ると..

		^ | 0 1 2 3
		--+--------
		0 | 0 1 2 3
		1 | 1 0 3 2
		2 | 2 3 0 1
		3 | 3 2 1 0

	ここで、{0.1} は閉じている (部分群になる), {0,1,2,3} は閉じている。
		# {0,1,2} は駄目であることに注意

	この規則を一般化すると...

	[定理 1.8]
		i) { 0, .., 2^n-1 } は部分群
		ii) p < 2^n の時
			p ^ 2^n = p + 2^n

		系
			2^m + 2^n = 2^m + 2^n	( m \ne n )
				  = 0		( m = n )

	# ここまでくれば、そろそろ ^ の正体がみえてくるが.. その説明は来週 !!
	# !! この問題は、当然試験にでない