Association schemes

Association Schemes: Designed Experiments, Algebra and Combinatorics (Cambridge Studies in Advanced Mathematics)

• その他の資料
• Wiki記事
• ひとまず、Wiki記事のみを拾い読みして、Association schemeの概略をつかんでみる
• Association schemeの条件
  • 集合がある
  • のすべての要素ペアには「関係」が定義されている
  • 「関係」はいくつかに分類されているという。それをとする→これは工夫次第でいじれそうな条件かもしれない。集合をマルチファジィ集合にするような緩め方、とか
  • ここでは特別な関係で「自身と同じ」という関係とする
  • また、この「関係」は対称性であるとする→これはもしかすると外せそうな条件だ
  • 最後の条件が本質(だろう)
    • 今、２要素の間の関係がkであるときに、２要素のそれぞれとある要素との関係をとると、i,jであるとする。この３者関係を満足する要素の数が、初めの２要素の取り方によらずにi,j,kによって等しいという条件を入れると、「かなりの制約」が生じる
• 上記で定めた「制約」された要素間関係は、対称性を持っている(要素ペアにおける「関係」の対称性だけでなく)
• これを表す方法は大きく３つ
  • 「分割」を用いる方法
  • 「グラフ」で表現する方法
  • 「行列」で表す方法
• 以下の例は、要素が長方形型に整理できて、要素間の関係が、その長方形型における行や列の異動によって決まる、というルールにすると、Associate schemeに乗ってくる、というそういう例である

n<-3
m<-4

v<-n*m
M<-matrix(1:v,n,m)
A<-matrix(0,v,v)

for(i in 1:v){
	tmp1<-which(M==i,arr.ind=TRUE)
	for(j in 1:v){
		tmp2<-which(M==j,arr.ind=TRUE)
		if(i==j){
			A[i,j]<-0
		}else{
			if(tmp1[1]==tmp2[1]){
				A[i,j]<-1
			}else if(tmp1[2]==tmp2[2]){
				A[i,j]<-2
			}else{
				A[i,j]<-3
			}
		}
	}
}
# 関係が同じ要素を抜き出して、(0,1)でできた行列のリストにする
As<-list()
for(i in 0:n){
	As[[i+1]]<-matrix(0,v,v)
	As[[i+1]][which(A==i,arr.ind=TRUE)]<-1
}
As

# その和は全要素が１の行列
Asum<-matrix(0,v,v)
for(i in 1:(3+1)){
	Asum<-Asum+As[[i]]
}
Asum

# AiAj = sum cijj Ak =AjAiだという
for(i in 0:(3-1)){
	for(j in (i+1):3){
		print(As[[i+1]]%*%As[[j+1]])
	}
}
J<-matrix(1,v,v)

As[[2]]%*%J
J%*%As[[2]]

• このようにして定めたAssociation schemeにどのような性質があるかを考える
  • 行列によって、関係を表すと次のようになる
    • 
    • のはなくても意味が通じるので書き直す
    • 
  • これは、つぎのようなルールで作った行列である
    • 正方行列
    • 値は、１個以上の値のいずれかを取る
    • 対角成分は等しい値をとる(非対角成分の値は対角成分と異なる→これも必須にしなくてもよいかもしれない…identicalな要素が複数回登場する場合などは、非対角成分に対角成分の値が出てもよいことにすればうまくいくだろうから)
    • 対称行列(「関係」を対称性と定義で与えたから)

v<-7
n<-3

m<-matrix(sample(1:n,v^2,replace=TRUE),v,v)
diag(m)<-0
m[lower.tri(m)]<-0
m<-m+t(m)
m

# 関係が同じ要素を抜き出して、(0,1)でできた行列のリストにする
As<-list()
for(i in 0:n){
	As[[i+1]]<-matrix(0,v,v)
	As[[i+1]][which(m==i,arr.ind=TRUE)]<-1
}
As

# その和は全要素が１の行列
Asum<-matrix(0,v,v)
for(i in 1:(n+1)){
	Asum<-Asum+As[[i]]
}
Asum

# AiAj = sum cijj Ak =AjAiだという
for(i in 0:(n-1)){
	for(j in (i+1):n){
		print(As[[i+1]]%*%As[[j+1]])
	}
}

• 長方形を変えて、かつ、エッジの色を「関係のグループ」で色分けしてみるとこうなる

NN<-3:5
MM<-3:5

par(mfcol=c(length(NN),length(MM)))

for(NNi in 1:length(NN)){
	n<-NN[NNi]
	for(MMi in 1:length(MM)){
		m<-MM[MMi]
		
#n<-sample(2:5,1)
#m<-sample(2:5,1)

v<-n*m
M<-matrix(1:v,n,m)
A<-matrix(0,v,v)

for(i in 1:v){
	tmp1<-which(M==i,arr.ind=TRUE)
	for(j in 1:v){
		tmp2<-which(M==j,arr.ind=TRUE)
		if(i==j){
			A[i,j]<-0
		}else{
			if(tmp1[1]==tmp2[1]){
				A[i,j]<-1
			}else if(tmp1[2]==tmp2[2]){
				A[i,j]<-2
			}else{
				A[i,j]<-3
			}
		}
	}
}
# 関係が同じ要素を抜き出して、(0,1)でできた行列のリストにする
As<-list()
for(i in 0:n){
	As[[i+1]]<-matrix(0,v,v)
	As[[i+1]][which(A==i,arr.ind=TRUE)]<-1
}
As

# その和は全要素が１の行列
Asum<-matrix(0,v,v)
for(i in 1:(3+1)){
	Asum<-Asum+As[[i]]
}
Asum

# AiAj = sum cijj Ak =AjAiだという
for(i in 0:(3-1)){
	for(j in (i+1):3){
		print(As[[i+1]]%*%As[[j+1]])
	}
}
J<-matrix(1,v,v)

As[[2]]%*%J
J%*%As[[2]]


A

t<-seq(from=0,to=1,length=v+1)*2*pi
t<-t[-length(t)]

plot(cos(t),sin(t))

for(i in 1:length(As)){
	for(j in 1:length(As[[i]][,1])){
		for(k in 1:length(As[[i]][1,])){
			if(As[[i]][j,k]==1){
				segments(cos(t[j]),sin(t[j]),cos(t[k]),sin(t[k]),col=i,lwd=1)
			}
			
		}
	}
}
	}
}