2010-12-17

似ているかどうか

$s_1=(1,2,3,4,5)$ と $s_2=(2,3,4,5,1)$ とは似ているだろうか似ていないだろうか
$s_1=(1,2,3,4,5)$ と $s_3=(2,1,4,3,5)$ とは似ているだろうか似ていないだろうか
似ているかどうかの基準によるだろう
$s_1,s_2$ は $1\to 2 \to 3 \to 4 \to 5 \to 1$ という循環の表現の一つであるとみれば、そっくり
$s_1,s_2$ は $(1,2),(3,4)$ の交換と見ればよく似ている
循環型の似通り方を評価する方法を考えよう
構成要素が同じ(1から5の数字という要素が同じ)の並び方を変えたものは「置換」と呼ぶが、N個の異なる要素の置換は $\sum n_i=N$ なる $(n_i)$ 個ずつの値のセットをそれぞれ循環させたものとして表すことができる
今、２つの置換 $s_i,s_j$ があって、それぞれが、同一であることは、要素数Nについて、N個の循環(循環の長さは１、自身から自身へ)である場合である。
上の例では、 $s_1\to s_2$ は長さ5の循環が１つの置換
$s_1 \to s_3$ は長さ２の循環が２つ、長さ１の循環が１つの置換
大小様々な循環で、全体が構成されているという考え方はこちらで書いたような部分に応用できる
演算的に考えれば、「群環体」的な、構造として特徴づけられるから、トポロジー的に評価できる(はず)

S1<-1:5
S2<-sample(S1)
s<-S2
SeqCircuit<-function(s){
	n<-length(s)
	s0<-1:n
	h<-list(c())
	counter<-1
	checker<-rep(1,n)
	while(sum(checker)>0){
		st<-s0[which(checker==1)][1]
		tmpval<-s[st]
		tmpseq<-c(tmpval)
		checker[tmpval]<-0
		while(tmpval!=st){
			tmpval2<-s[tmpval]
			tmpseq<-c(tmpseq,tmpval2)
			tmpval<-tmpval2
			checker[tmpval]<-0
		}
		h[[counter]]<-tmpseq
		counter<-counter+1
	}
	return(list(Circuits=h,NumCircuit=length(h),LengthCircuit=as.numeric(lapply(h,length))))
}

SeqCircuit(s)

これを行列を使って考えてみる
- 1,2,...というきれいな順列を対角正方行列に対応させる
- これを適当な順列に変換する行列は、すべての行、すべての列が、ただ１つの要素で値１を持ち、それ以外の要素は０となるような行列である
- この行列の特異値を求めると、上で述べた「循環」の個数だけ、値が１の特異値が得られる
- また、この特異値は複素数であるが、その絶対値はすべて１である
- さらにまた、この特異値である複素数を複素平面上に表すと、１周を等分する点に対応する
- したがって、長さNの順列で、それがk個の循環で構成された置換であって、それぞれの循環の構成要素数が $n_i,\sum_{i=1}^k n_i=N$ となるとき、円周を角度０の点から取り始めて、 $n_i$ 等分した点に対応する複素数(全部でN個)が特異値となる
- 値が１の特異値の個数が循環の個数となるのは、個々の循環は必ず角度０(実成分１、虚成分０）の点を持ち、その角度０の点は、各循環に１つしかないからである

S1<-1:20
S2<-sample(S1)
s<-S2
SeqCircuit<-function(s){
	n<-length(s)
	s0<-1:n
	h<-list(c())
	counter<-1
	checker<-rep(1,n)
	while(sum(checker)>0){
		st<-s0[which(checker==1)][1]
		tmpval<-s[st]
		tmpseq<-c(tmpval)
		checker[tmpval]<-0
		while(tmpval!=st){
			tmpval2<-s[tmpval]
			tmpseq<-c(tmpseq,tmpval2)
			tmpval<-tmpval2
			checker[tmpval]<-0
		}
		h[[counter]]<-tmpseq
		counter<-counter+1
	}
	return(list(Circuits=h,NumCircuit=length(h),LengthCircuit=as.numeric(lapply(h,length))))
}

m<-matrix(0,length(s),length(s))
for(i in 1:length(s)){
	m[i,s[i]]<-1
}

s
SCout<-SeqCircuit(s)
Angles<-Arg(eigen(m)[[1]])/(2*pi)
InvAngles<-sort(1/Angles)
num0<-length(which(Angles==0))
SCout[[2]] # 循環探索によって求めた、「循環の個数」
num0 # 特異値=0の数

SCout[[3]] # 循環の長さのリスト
Angles # 特異値の複素平面上の角(2piを１としてある)
InvAngles # 特異値の複素平面上の角が2piの何分の１にあたるか

Mod(eigen(m)[[1]]) # 特異値の絶対値がすべて1であることの確認

実行例

> s
 [1] 18  1 19  9 12  5 17  8  2 13 20 10  4  3  7 11 14 15 16  6
> SCout<-SeqCircuit(s)
> Angles<-Arg(eigen(m)[[1]])/(2*pi)
> InvAngles<-sort(1/Angles)
> num0<-length(which(Angles==0))
> SCout[[2]] # 循環探索によって求めた、「循環の個数」
[1] 2
> num0 # 特異値=0の数
[1] 2
> 
> SCout[[3]] # 循環の長さのリスト
[1] 19  1
> Angles # 特異値の複素平面上の角(2piを１としてある)
 [1]  0.47368421 -0.47368421  0.31578947 -0.31578947  0.42105263 -0.42105263  0.26315789 -0.26315789
 [9]  0.00000000  0.10526316 -0.10526316  0.36842105 -0.36842105  0.21052632 -0.21052632  0.05263158
[17] -0.05263158  0.00000000  0.15789474 -0.15789474
> InvAngles # 特異値の複素平面上の角が2piの何分の１にあたるか
 [1] -19.000000  -9.500000  -6.333333  -4.750000  -3.800000  -3.166667  -2.714286  -2.375000  -2.111111
[10]   2.111111   2.375000   2.714286   3.166667   3.800000   4.750000   6.333333   9.500000  19.000000
[19]        Inf        Inf
> 
> Mod(eigen(m)[[1]]) # 特異値の絶対値がすべて1であることの確認
 [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

さて、順列の置換が「複素平面上の等角回転」の合わさったものだということが分かったから、その置換を何度も繰り返すと、「もとに戻るはず」
循環距離の最小公倍数だけ繰り返せば、行列は単位行列に戻るだろう。最小公倍数は、素因数分解を利用するので、パッケージschoolmathのscm()関数を用いるとよい

library(schoolmath) # 最小公倍数を求めるため

LCM<-1
for(i in 1:length(SCout[[3]])){
	LCM<-scm(LCM,SCout[[3]][i])
}

m%^%LCM