결합 도식 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''결합 도식'''(結合圖式, {{llang|en|association scheme|어소시에이션 스킴}}) 또는 '''일관 구조'''(一貫構造, {{llang|en|coherent configuration}})는 어떤 특별한 조건을 만족시키는 일련의 [[이항 관계]]들이 주어진 [[유한 집합]]이며, [[변 색칠]]이 주어진 [[완전 그래프]]로도 간주될 수 있다.<ref name="Bailey">{{서적 인용| first=Rosemary Anne | last=Bailey | url=http://www.maths.qmul.ac.uk/~rab/Asbook | title=Association schemes: designed experiments, algebra and combinatorics|publisher=Cambridge University Press|year=2004|isbn=978-0-521-82446-0| mr=2047311|doi=10.1017/CBO9780511610882|언어=en}}</ref><ref name="Zieschang">{{서적 인용| last=Zieschang | first=Paul-Hermann |  title=Theory of association schemes |  publisher=Springer-Verlag |  year=2005 |doi=10.1007/3-540-30593-9 | 총서=Springer Monographs in Mathematics|isbn=978-3-540-26136-0|issn=1439-7382|언어=en }}</ref><ref name="DL">{{저널 인용|doi=10.1109/18.720545|제목=Association schemes and coding theory|issn=0018-9448|저널= Institute of Electrical and Electronics Engineers Transactions on Information Theory|권=44|호=6|날짜=1998-10|이름=Philippe|성=Delsarte|이름2=Vladimir Iosifovich|성2=Levenshtein|저자링크2=블라디미르 레벤시테인|쪽= 2477–2504|url=http://www.keldysh.ru/papers/1998/source/article/DELFIN.PS|언어=en}}</ref><ref>{{저널 인용|제목=Introduction to association schemes|이름=Johan Jacob|성=Seidel|저널=Séminaire Lotharingien de Combinatoire|issn=1286-4889|권=26|쪽=B26g|날짜=1991|url=https://www.emis.de/journals/SLC/opapers/s26seidel.html|zbl=0981.05535|언어=en}}</ref> 주어진 결합 도식으로부터 그 구조를 나타내는 [[결합 대수]]인 '''보스-메스너 대수'''(बसु-Mesner代數, {{llang|en|Bose–Mesner algebra}})가 존재한다.

== 정의 ==
결합 도식의 개념은 여러 가지로 정의될 수 있으나, 이 정의들은 모두 서로 [[동치]]이다.

=== 조합론적 정의 ===
'''결합 도식''' <math>(X,\mathcal R)</math>은 다음과 같은 데이터로 주어진다.<ref name="DL"/>{{rp|2479, Definition 1}}<ref name="Bailey"/>{{rp|1, §1.1}}
* [[유한 집합]] <math>X</math>
* <math>X\times X</math>의, <math>n+1</math>개의 [[부분 집합]]들 <math>\mathcal R</math>, <math>|\mathcal R|=n+1</math>
이는 다음 조건들을 만족시켜야 한다.
* ㉠ <math>\mathcal R</math>는 <math>X\times X</math>의 [[집합의 분할|분할]]을 이룬다. 즉, <math>R,R'\in\mathcal R</math>이며 <math>R\ne R'</math>이라면 <math>R\cap R'=\varnothing</math>이며, 또한 <math>\textstyle\bigcup\mathcal R=X\times X</math>이다.
* ㉡ <math>\textstyle\{(x,x)\colon x\in X\}=\bigcup\mathcal R'</math>인 [[부분 집합]] <math>\mathcal R'\subseteq \mathcal R</math>가 존재한다.
* ㉢ <math>\varnothing\not\in\mathcal R</math>
* ㉣ 임의의 <math>R\in\mathcal R</math>에 대하여, <math>R^{\operatorname{op}}\in\mathcal R</math>
* ㉤ 임의의 <math>R,R',R''\in\mathcal R</math> 및 <math>(x,y)\in R</math>에 대하여, <math>|\{z\in X\colon x\sim_{R'}y\sim_{R''}z\}|\in\mathbb N</math>는 <math>(x,y)</math>에 의존하지 않는다.
여기서
* <math>R\in\mathcal R</math>에 대하여, <Math>x\sim_Ry</math>는 <math>(x,y)\in R</math>를 뜻한다.
* <math>R^{\operatorname{op}}=\{(y,x)\colon(x,y)\in R\}</math>는 <math>R</math>의 반대 [[이항 관계]]이다.

흔히, <math>\mathcal R</math>의 원소는 <math>(R_0,R_1,\dotsc,R_n)</math>으로 표기되며, 이 경우 <math>R_0=\{(x,x)\colon x\in X\}</math>이다. 또한,
:<math>p_{ij}^k=|\{z\in X\colon x\sim_iy\sim_jz\}|\qquad(x\sim_ky)</math>
는 결합 도식의 '''구조 상수'''(構造常數, {{llang|en|structure constant}})라고 한다.

=== 행렬을 통한 정의 ===
'''결합 도식''' <math>(X,n,\mathcal A)</math>은 다음과 같은 데이터로 주어진다.<ref name="Bailey"/>{{rp|13–14, §1.3}}
* [[유한 집합]] <math>X=\{0,1,\dotsc,q-1\}</math>
* [[자연수]] <math>n</math>
* <math>n</math>개의, 모든 성분이 0 또는 1인 <math>q\times q</math> [[정사각 행렬]]들의 족 <math>\mathcal A=\{A_0,A_1,\dotsc,A_n\}</math>.
이는 다음 조건들을 만족시켜야 한다.
* ㉠ <math>\textstyle\sum_{i=0}^nA_i</math>는 모든 성분이 1인 <math>k\times k</math> [[정사각 행렬]]이다.
* ㉡ <math>\textstyle1_{k\times k}=\sum\mathcal A'</math>인 <math>\mathcal A'\subseteq \mathcal A</math>가 존재한다.
* ㉢ <math>0_{k\times k}\not\in\mathcal A</math>.
* ㉣ 임의의 <Math>A\in\mathcal A</math>에 대하여, <math>A^\top\in\mathcal A</math>
* ㉤ 임의의 <math>A_i,A_j\in\mathcal A</math>에 대하여, 그 곱 <math>A_iA_j</math>는 <math>\mathcal A</math>의 원소들의 자연수 계수 [[선형 결합]]이다. 즉, 각 <math>0\le i,j,k\le k</math>에 대하여, <math>\textstyle A_iA_j=\sum_{k=0}^np^k_{ij}A_k</math>인 자연수 <math>p^k_{ij}</math>가 존재한다.

이 두 정의는 서로 [[동치]]이다. 즉, 두 정의 사이를 번역하려면, 각 [[이항 관계]] <math>\sim_i</math>를 대신 [[정사각 행렬]]
:<math>(A_i)_{x,y}=x\sim_iy\qquad(x,y\in X)</math>
로 치환하면 된다.

=== 기하학적 정의 ===
결합 도식의 개념은 [[거리 공간]]과 유사하게 정의될 수도 있다.<ref name="DL"/>{{rp|2479, §Ⅱ.A}}

'''결합 도식''' <math>(X,D,\partial)</math>은 다음과 같은 데이터로 주어진다.
* [[유한 집합]] <math>X</math>
* [[유한 집합]] <math>D</math>
* [[함수]] <math>\partial\colon X\times X\to D</math>. 이는 '''거리 함수'''(距離函數, {{llang|en|distance}})라고 한다.
이는 다음 조건들을 만족시켜야 한다.
* ㉡ 임의의 <math>x,y,z\in X</math>에 대하여, 만약 <math>\partial(x,x)=\partial(y,z)</math>라면, <math>y=z</math>이다.
* ㉢ <math>\partial</math>은 [[전사 함수]]이다.
* ㉣ 임의의 <math>x,y,x',y'\in X</math>에 대하여, <math>\partial(x,y)=\partial(x',y')</math>라면 <math>\partial(y,x)=\partial(y',x')</math>
* ㉤ 임의의 <math>x,y,x',y'\in X</math>에 대하여, 만약 <math>\partial(x,y)=\partial(x',y')</math>라면, <math>\forall z\in X\colon \partial(x,z)=\partial(x',f(z))</math>이자 <math>\forall z\in X\colon\partial(z,y)=\partial(f(z),y')</math>가 되는 [[전단사 함수]] <math>f\colon X\to X</math>가 존재한다.

이 정의 역시 나머지 두 정의와 서로 동치이다. 즉, 각 <math>\alpha\in D</math>에 대하여 [[이항 관계]]
:<math>x\sim_\alpha y\iff \partial(x,y)=\alpha</math>
를 대응시키면 된다.

=== 부분 결합 도식 ===
같은 집합 <math>X</math> 위의 두 결합 도식 <math>(X,\mathcal R)</math> 및 <math>(X,\mathcal R')</math>에 대하여, 만약 <math>\mathcal R\subseteq\mathcal R'</math>이라면, <math>(X,\mathcal R)</math>를 <math>(X,\mathcal R')</math>의 '''부분 결합 도식'''(部分結合圖式, {{llang|en|subscheme}})이라고 한다.

=== 결합 도식 준동형 ===
다음이 주어졌다고 하자.
* [[유한 집합]] <math>X</math> 위의 결합 도식 <Math>(X,\mathcal R)</math>
* [[유한 집합]] <math>X'</math> 위의 결합 도식 <Math>(X',\mathcal R')</math>
그렇다면, '''결합 도식 사상'''({{llang|en|morphism of association schemes}}) <math>(f,g)\colon (X,\mathcal R)\to(X',\mathcal R')</math>은 다음과 같은 데이터로 구성된다.<ref name="Zieschang"/>{{rp|83, Chapter 5}}
* 함수 <math>f\colon X\to X'</math>
* 함수 <Math>g\colon \mathcal R\to\mathcal R'</math>
이는 다음 조건을 만족시켜야 한다.
:임의의 <math>x,y\in X</math> 및 <Math>R\in\mathcal R</math>에 대하여, 만약 <math>x\sim_Ry</math>라면, <math>f(x)\sim_{g(R)}f(y)</math>이다.

이는 사실 [[이항 관계]]가 주어진 [[구조 (논리학)|구조]] 사이의 [[준동형]]의 특수한 경우이다.

== 종류 ==
결합 도식 <math>X</math>에 대하여 다음 조건들이 서로 [[동치]]이며, 이를 만족시키는 결합 도식을 '''대칭 결합 도식'''(對稱結合圖式, {{llang|en|symmetric association scheme}})이라고 한다.<ref name="DL"/>{{rp|2479, §II.A}}
* 조합론적 정의 <math>(X,\mathcal R)</math>에서, <math>\mathcal R</math>의 모든 원소는 [[대칭 관계]]이다. 즉, 만약 <math>R\in\mathcal R</math>라면, <math>R=R^{\operatorname{op}}</math>이다.
* 행렬을 통한 정의 <math>(X,\mathcal A)</math>에서, 모든 <Math>A\in\mathcal A</math>는 [[대칭 행렬]]이다.
* 기하학적 정의 <math>(X,\partial)</math>에서, 임의의 <Math>x,y\in X</math>에 대하여 <math>\partial(x,y)=\partial(y,x)</math>이다.
결합 도식 <math>(X,\mathcal R)</math>에 대하여 다음 두 조건이 서로 [[동치]]이며, 이를 만족시키는 결합 도식을 '''가환 결합 도식'''(可換結合圖式,{{llang|en|commutative association scheme}})이라고 한다.
* 그 보스-메스너 대수가 [[가환환]]이다.
* 조합론적 정의에서, 임의의 <Math>R,R',R''\in\mathcal R</math> 및 <math>(x,y)\in R</math>에 대하여, <math>|\{z\in X\colon x\sim_{R'}z\sim_{R''}y\}|=|\{z\in X\colon x\sim_{R''}z\sim_{R'}y\}|</math>
* 행렬을 통한 정의 <math>(X,\mathcal A)</math>에서, 임의의 <Math>A,B\in\mathcal A</math>에 대하여 <math>AB=BA</math>이다.
* 기하학적 정의 <math>(X,\partial)</math>에서, 임의의 <math>x,y\in X</math>에 대하여, <math>\forall z\in X\colon
(\partial(x,z),\partial(z,y))=(\partial(y,f(z)),\partial(f(z),x))</math>가 되는 [[자기 함수|자기]] [[전단사 함수]] <math>f\colon X\to X</math>가 존재한다.

결합 도식 <math>(X,\mathcal R)</math>이 다음 조건을 만족시킨다면, '''균등 결합 도식'''(均等結合圖式, {{llang|en|homogeneous association scheme}})이라고 한다.
* 조합론적 정의 <math>(X,\mathcal R)</math>에서, <math>\{(x,x)\colon x\in X\}\in\mathcal R</math>이다.
* 행렬을 통한 정의 <math>(X,\mathcal A)</math>에서, <math>1_{|X|\times|X|}\in\mathcal A</math>이다.
* 기하학적 정의 <math>(X,\partial)</math>에서, <math>\forall x,y\in X\colon \partial(x,x)=\partial(y,y)</math>이다.

다음과 같은 포함 관계가 성립한다.
:대칭 결합 도식 ⊊ 가환 결합 도식 ⊊ 균등 결합 도식 ⊊ 결합 도식

== 연산 ==
=== 올 ===
결합 도식 <math>(X,\partial)</math>이 주어졌을 때, <math>X</math> 위에 다음과 같은 [[동치 관계]]를 정의할 수 있다.
:<math>x\approx y\iff \partial(x,x)=\partial(y,y)</math>
이 동치 관계에 대한 동치류를 <math>X</math>의 '''올'''({{llang|en|fibre}})이라고 하자. 올들로 구성된 [[집합의 분할]]을 <math>(X_\alpha)_{\alpha\in I}</math>로 표기할 때, 다음이 성립한다.
:<math>\forall R\in\mathcal R\exists \alpha,\beta\in I\colon R\subseteq X_\alpha\times X_\beta</math>
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
임의의 <math>x,y,y'\in X</math>가 주어졌으며, [[귀류법]]을 사용하여
:<math>\partial(x,y)=\partial(x,y')</math>
:<math>\partial(y,y)\ne\partial(y',y')</math>
이라고 가정하자. 그렇다면,
:<math>\{z\in X\colon \partial(x,z)=\partial(x,y),\;\partial(z,y)=\partial(y,y)\} = \{y\}</math>
:<math>\{z\in X\colon \partial(x,z)=\partial(x,y),\;\partial(z,y')=\partial(y,y)\} = \varnothing</math>
이므로, 이는 결합 도식의 정의와 모순된다.
</div></div>
이에 따라, 결합 도식 <math>(X,\partial)</math>의 임의의 올 <math>X_i</math>이 주어졌을 때,
:<math>(X_i,\partial\restriction X_i^2)</math>
는 균등 결합 도식을 이룬다.

=== 직접곱 ===
유한 개의 결합 도식
:<math>(X_i,\mathcal R_i)_{i\in I}</math>
:<math>|I|<\aleph_0</math>
이 주어졌다고 하자. 그렇다면, [[곱집합]]
:<math>X=\prod_{i\in I}X_i</math>
위에 [[이항 관계]]
:<math>\mathcal R=\prod_{i\in I}\mathcal R_i</math>
:<math>(x_i)_{i\in I}\sim_{(R_i)_{i\in I}}(y_i)_{i\in I}\iff\forall i\in I\colon x_i\sim_{R_i}y_i</math>
를 줄 수 있다. 그렇다면, <math>(X,\mathcal R)</math>는 결합 도식을 이루며, 이를 <Math>(X_i,\mathcal R_i)_{i\in I}</math>의 '''직접곱'''(直接곱, {{llang|en|direct product}})이라고 한다.<ref name="Zieschang"/>{{rp|140, Chapter 7}}

이는 [[군 (수학)|군]]의 [[직접곱]]의 개념의 일반화이다.

== 성질 ==
=== 구조 상수 ===
임의의 결합 도식 <math>X</math>의 구조 상수들 <math>(p_{ij}^k)_{1\le i,j,k\le n}</math>은 다음을 만족시킨다.
:<math>\sum_{i,j,k=0}^np_{ij}^k|R_k|=|X|^3</math>
만약
:<math>R_i^{\operatorname{op}}=R_{\bar\imath}</math>
:<math>R_j^{\operatorname{op}}=R_{\bar\jmath}</math>
:<math>R_k^{\operatorname{op}}=R_{\bar k}</math>
일 때, 다음이 성립한다.
:<math>p_{jk}^i=p_{\bar k\bar\jmath}^{\bar\imath}</math>

균등 결합 도식 <math>(X,\mathcal R)</math>의 구조 상수들 <math>(p_{ij}^k)_{1\le i,j,k\le n}</math>은 다음을 만족시킨다.<ref name="Bailey"/>{{rp|26, Exercise 1.1(a)}}
:<math>p_{0i}^j=p_{i0}^j=\delta_i^j</math>
:<math>p_{ij}^0=p_{\bar\jmath\bar\imath}^0=\delta_j^{\bar\imath}p_{i\bar\imath}^0</math>
:<math>\sum_{i,j=0}^np_{ij}^0=\sum_{i=0}^np_{i\bar\imath}^0=|X|</math>
(여기서 <math>\delta_i^j</math>는 [[크로네커 델타]]이다.)

=== 대칭 결합 도식에 대응되는 변 색칠 ===
대칭 결합 도식 <math>(X,\mathcal R)</math>이 주어졌다고 하자. 그렇다면, <math>X</math>의 원소를 꼭짓점들로 하는 [[완전 그래프]] <math>K_X</math> 위에, <math>\mathcal R\setminus\{R_0\}</math>의 원소를 색으로 하는 [[변 색칠]] <math>c\colon \operatorname E(K_X)\to \mathcal R\setminus\{R_0\}</math>을 정의할 수 있다.
:<math>c\colon (x,y)\mapsto R\iff (x,y)\in R\qquad(R\in\mathcal R,\;R\ne R_0)</math>
이에 따라, 대칭 결합 도식은 특별한 [[변 색칠]]이 주어진 유한 [[완전 그래프]]로 여겨질 수 있다.<ref name="Bailey"/>{{rp|7–8, §1.2}}

=== 보스-메스너 대수 ===
(행렬을 통한 정의의) 결합 도식 <math>(X,\mathcal A)</math>이 주어졌을 때, <math>\mathcal A</math>의 [[선형 생성]]
:<math>\operatorname{Span}_{\mathbb Z}\mathcal A\subseteq\operatorname{Mat}(|X|,|X|;\mathbb Z)</math>
은 정수 계수 [[결합 대수]]를 이룬다. 이를 <math>X</math>에 대응하는 '''보스-메스너 대수'''라고 한다 (흔히, 정수 계수 대신 실수나 복소수 계수가 사용된다).<ref name="DL"/>{{rp|2480, Definition 2}}

[[에르미트 수반]]에 대하여 닫혀 있는 복소수 행렬 [[결합 대수]]이므로, 복소수 계수 보스-메스너 대수는 항상 [[반단순 대수]]이다.

[[아르틴-웨더번 정리]]에 따라서, 복소수 계수 보스-메스너 계수는 다음과 같은 꼴로 유일하게 표현된다.
:<math>\prod_{a=1}^k\operatorname{Mat}(m_a,m_a;\mathbb C)</math>
이에 따라, 위 분해에 등장하는 [[멱등원]]
:<math>E_a=(0,0,\dotsc,0,1_{m_a\times m_a},0,\dotsc,0)</math>
들을 정의할 수 있으며, 이들은
:<math>E_aE_b=\delta_{ab}E_a\qquad(a,b\in\{0,\dotsc,k\})</math>
를 만족시킨다 (<math>\delta_{ab}</math>는 [[크로네커 델타]]). 또한, 편의상
:<math>E_0=\frac1{|X|}\mathsf J_{|X|\times|X|}.</math>
로 놓는다. 여기서 <math>\mathsf J_{|X|\times|X|}</math>는 모든 성분이 1인 <math>|X|\times|X|</math> [[정사각 행렬]](즉, [[아다마르 곱]]의 항등원)이다. 이는 결합 도식의 공리에 따라 보스-메스너 대수의 원소이며, 0이 아닌 고윳값이 1개 밖에 없는 멱영원이므로 위 분해에 항상 등장한다.

특히, <math>E_a</math>를 <math>D_i</math>로 전개하였을 때의 계수
:<math>|X|E_a=\sum_{i=0}^nQ_{ai}D_j</math>
를 정의할 수 있다.

=== 가환 결합 도식의 쌍대성 ===
가환 결합 도식 <math>X</math>의 경우, 최소 멱등원의 수는 <math>|X|=n</math>와 같으며, [[멱영원]]들 <math>(E_a)_{0\le a\le n}</math>은 보스-메스너 대수 <math>\mathcal A</math>의 [[기저 (선형대수학)|기저]]를 이룬다. 이에 따라, 다음을 정의할 수 있다.
:<math>D_i=\sum_{a=0}^nP_{i,a}E_a</math>
또한, <math>D_i</math>들은 모두 [[아다마르 곱]]에 대하여 닫혀 있으므로, <math>E_a</math>들의 [[아다마르 곱]]에 대한 구조 상수
:<math>E_a\bigcirc E_b=q_{ab}^cE_c</math>
를 정의할 수 있다. (아다마르 곱은 [[교환 법칙]]을 따르므로 <math>q_{ab}^c=q_{ba}^c</math>이다.)

이에 따라, 다음과 같은 쌍대성이 존재한다.
{| class=wikitable
|-
! 이항 연산
| [[아다마르 곱]] <math>\bigcirc</math> || 행렬의 곱
|-
! 기저
| <math>D_i</math> || <math>E_a</math>
|-
! 기저의 직교성
| <math>D_i\bigcirc D_j=\delta_{ij}D_i</math> || <math>E_aE_b=\delta_{ab}E_a</math>
|-
! [[멱등원]] 조건
| <math>D_i</math>의 모든 성분은 0 또는 1 ([[아다마르 곱]]의 [[멱등원]]) || <math>E_a</math>의 모든 [[고윳값]]은 0 또는 1 (행렬곱의 [[멱등원]])
|-
! 항등원
| <math>D_0=1_{n\times n}</math> || <math>E_0 = \mathsf J_{n\times n} / |X|</math>
|-
! 기저 원소의 쌍대성
| <math>D_{\bar\imath} = D_i^\top</math> || <math>E_{\bar a} = E_a^\top = \bar E_a</math> (각 성분의 [[복소켤레]])
|-
! 기저의 합
| <math>\textstyle\sum_iD_i=\mathsf J_{|X|\times|X|}</math> || <math>\textstyle\sum_aE_a=1_{|X|\times|X|}</math>
|-
! 차수
| <math>v_i=\{y\in X\colon x\sim_iy\}\;(\forall x\in X)</math> || <math>m_a=\dim_{\mathbb C}\operatorname{im}E_a</math>
|-
! 차수의 합
| <math>\textstyle\sum_iv_i=|X|</math>
| <math>\textstyle\sum_am_a=|X|</math>
|-
! 구조 상수
| <math>D_iD_j=p_{ij}^kD_k</math>
| style="background-color: #ffff80" | <math>|X|E_a\bigcirc E_b=q_{ab}^cE_c</math>
|-
! 기저 변환
| style="background-color: #ffff80"  | <math>\textstyle D_i=\sum_{a=0}^nP_{ia}E_a</math>
| <math>\textstyle E_a=\sum_{i=0}^nQ_{ai}D_i</math>
|}
이 표에서, 배경색이 노란 칸은 가환 결합 도식일 경우에만 정의되는 것이다.

이에 따라, 만약 두 결합 도식 <math>X</math>, <math>Y</math>의 복소수 계수 보스-메스너 대수 <math>\mathcal A_X</math>, <math>\mathcal A_Y</math>가 각각
:<math>(\mathcal A_X,\cdot,\bigcirc,(D_i)_i)\cong(\mathcal A_Y,\bigcirc,\cdot,(E_a)_a)</math>
라면, 서로 '''쌍대'''({{llang|en|dual}})라고 한다. 즉, 반선형 변환({{llang|en|antilinear map}})
:<math>f\colon \mathcal A_X\to\mathcal A_Y</math>
:<math>f(\lambda M)=\bar\lambda f(M)\qquad(\lambda\in\mathbb C,\;M\in\mathcal A_X)</math>
:<math>f(MN)=f(M)\bigcirc f(N)</math>
:<math>f(M\bigcirc N)=f(M)f(N)</math>
를 만족시킬 경우, 이들이 서로 쌍대라고 한다.

[[아다마르 곱]]은 항상 [[교환 법칙]]을 따르므로, 쌍대성은 오직 두 가환 결합 도식 사이에만 존재할 수 있다.<ref>{{저널 인용|제목=Duality in coherent configurations|url=http://www.mat.univie.ac.at/~neum/scan/59|doi=10.1007/BF02122684|날짜=1989-03|권=9|호=1|쪽=59–67|저널=Combinatorica|이름=Arnold|성=Neumaier|issn=0209-9683|zbl=0673.05015|언어=en|access-date=2017-06-05|archive-date=2004-11-08|archive-url=https://web.archive.org/web/20041108231725/http://www.mat.univie.ac.at/~neum/scan/59/|url-status=}}</ref>

특히, [[해밍 결합 도식]]은 스스로의 쌍대이다.<ref name="DL"/>{{rp|2482, Example 1 (continued)}}

== 예 ==
다음은 <math>n=3</math>인 대칭 결합 도식의 한 예이다. 여기서 <math>X=\{\mathsf A,\mathsf B,\mathsf C,\mathsf D,\mathsf E,\mathsf F\}</math>이다.
:{| class=wikitable
|-
! !! A !! B !! C !! D !! E !! F
|-
! A
| 0 || 1 || 1 || 2 || 3 || 3
|-
! B
| 1 || 0 || 1 || 3 || 2 || 3
|-
! C
| 1 || 1 || 0 || 3 || 3 || 2
|-
! D
| 2 || 3 || 3 || 0 || 1 || 1
|-
! E
| 3 || 2 || 3 || 1 || 0 || 1
|-
! F
| 3 || 3 || 2 || 1 || 1 || 0
|}

그 구조 상수는 다음과 같다.
:<math>1 = p_{00}^0 = p_{01}^1 = p_{02}^2 = p_{03}^3 = p_{11}^1 = p_{23}^1 = p_{33}^1 =  p_{22}^2 = p_{12}^3 = p_{13}^3</math>
:<math>2 = p_{11}^0 = p_{33}^0 = p_{13}^2</math>
여기서 <math>p_{ij}^k</math>가 수록되었다면 <math>p_{ji}^k</math>는 생략하였으며, 수록되지 않은 구조 상수는 모두 0이다.

=== 자명한 결합 도식 ===
크기가 2 이상인 임의의 [[유한 집합]] <math>X</math> 위에
:<math>R_0=\{(x,x)\colon x\in X\}</math>
:<math>R_1=X\times X\setminus R_0</math>
:<math>\mathcal R=\{R_0,R_1\}</math>
을 정의하면, <math>(X,2,\mathcal R)</math>는 결합 도식을 이루며, 이를 '''자명한 결합 도식'''(自明-結合圖式, {{llang|en|trivial association scheme}})이라고 한다.<ref name="Cameron"/>{{rp|§1.1}} 그 구조 상수는 다음과 같다.
:<math>p_{00}^0=p_{01}^1=p_{10}^1=1</math>
:<math>p_{00}^1=p_{01}^0=p_{10}^0=0</math>
:<math>p_{11}^0=|X|-1</math>
:<math>p_{11}^1=|X|-2</math>
이는 사실 <math>n=1</math>인 [[해밍 결합 도식]]과 같다.

=== 이산 결합 도식 ===
임의의 [[유한 집합]] <math>X</math> 위에,
:<math>\mathcal R=\{\{(x,y)\}\colon x,y\in X\}</math>
를 정의하면, <math>(X,\mathcal R)</math> 역시 결합 도식을 이룬다. 이를 '''이산 결합 도식'''(離散結合圖式, {{llang|en|discrete association scheme}})이라고 한다.<ref name="Cameron"/>{{rp|§1.1}} 그러나 <math>|X|\ge2</math>일 경우 이는 균등 결합 도식이 아니다.

=== 작은 결합 도식 ===
크기 1의 결합 도식은 유일하며, 이는 대칭 결합 도식이다.
{| class=wikitable
|-
! !! A
|-
! A
| 0
|}
크기 2의 결합 도식은 다음 두 가지가 있다.
{| class=wikitable
|+ (가)
|-
! !! A !! B
|-
! A
| 0 || 1
|-
! B
| 1 || 0
|}
{| class=wikitable
|+ (나)
|-
! !! A !! B
|-
! A
| 0 || 2
|-
! B
| 3 || 1
|}
(가)는 자명한 결합 도식이며, (나)는 이산 결합 도식이다. (가)는 대칭 결합 도식이지만, (나)는 균등 결합 도식이 아니다.

주어진 집합 <Math>X</math> 위의, 특별한 조건을 만족시키는 결합 도식의 수는 다음과 같다.<ref name="Cameron">{{서적 인용|장=Coherent configurations, association schemes and permutation groups|성=Cameron|이름=Peter J.|장url=https://pdfs.semanticscholar.org/8c40/8f8ba917c1bd2ae7126bae8e816365e5894d.pdf|zbl=1022.05085|제목=Groups, combinatorics and geometry. Durham 2001|쪽=55–71|출판사=World Scientific|editor1-last=Ivanov|editor1-first=A. A.|editor2-first=M. W.|editor2-last=Liebeck|editor3-first= J.|editor3-last= Saxl |doi=10.1142/9789812564481_0004|isbn=978-981-238-312-9 |언어=en}}</ref>{{rp|Table 1}}
{| class=wikitable
! <math>|X|</math> || 균등 결합 도식의 수<br>{{OEIS|57495}} || 대칭 결합 도식의 수
|-
! 1
| 1 || 1
|-
! 2
| 1 || 1
|-
! 3
| 2 || 1
|-
! 4
| 4 || 3
|-
! 5
| 3 || 2
|-
! 6
| 8 || 4
|-
! 7
| 4 || 2
|-
! 8
| 21 || 10
|-
! 9
| 12 || 6
|-
! 10
| 13 || 8
|-
! 11
| 4 || 2
|-
! 12
| 59 || 21
|}

=== 해밍 결합 도식과 존슨 결합 도식 ===
{{본문|해밍 결합 도식}}
{{본문|존슨 결합 도식}}
임의의 [[곱집합]] <math>X=F^n</math> 위에, 두 벡터 사이의 [[해밍 거리]]가 <math>0,1,\dotsc,n</math>인 것을 각각 [[이항 관계]]로 삼으면, 이는 결합 도식을 이룬다. 이를 '''[[해밍 결합 도식]]'''이라고 한다.

특히, <math>F=\{0,1\}</math>일 때, 주어진 [[해밍 무게]]의 벡터들만을 취한 부분 결합 도식을 '''[[존슨 결합 도식]]'''이라고 한다.

=== 정추이적 작용 ===
[[유한군]] <math>G</math>의, [[유한 집합]] <math>X</math> 위의 왼쪽 [[정추이적 작용]]이 주어졌다고 하자. (특히, <math>|G|=|X|</math>이다.) 그렇다면,
:<math>n=|G|</math>
:<math>\mathcal R=\{\{(x,gx)\colon x\in X\}\colon g\in G\}</math>
를 정의하면, <math>(X,n,\mathcal R)</math>는 결합 도식을 이루며, 그 구조 상수는
:<math>p_{gh}^k=\begin{cases}
1&gh=k\\
0&gh\ne k
\end{cases}\qquad(g,h,k\in G)</math>
이다.

이에 대응하는 보스-메스너 대수는 [[군환]]
:<math>\mathbb Z[G]</math>
과 동형이다.

또한, <math>G</math>에 대응하는 결합 도식이 가환 결합 도식일 [[필요 충분 조건]]은 <math>G</math>가 [[아벨 군]]인 것이다.

=== 일반적 군 작용 ===
[[유한군]] <math>G</math>의, [[유한 집합]] <math>X</math> 위의 왼쪽 [[군의 작용|작용]]이 주어졌다고 하자. 그렇다면, <math>G</math>는 <math>X^2=X\times X</math> 위에 다음과 같이 작용한다.
:<math>g\cdot(x,y)=(g\cdot x,g\cdot y)\qquad(x,y\in X,\;g\in G)</math>
그렇다면, <math>G</math>의 작용에 대한 궤도들은 <math>X^2</math>의 [[집합의 분할|분할]] <math>X^2/G</math>을 정의한다.

이 경우, <math>(X,X^2/G)</math>는 결합 도식을 이룬다.<ref name="DL"/>{{rp|2482, §II.D}} 또한, 이 결합 도식이 각종 조건을 만족시킬 [[필요 충분 조건]]은 다음과 같다.
{| class=wikitable
! 결합 도식 !! [[군의 작용]]
|-
| 올 || <math>X</math> 위의 <math>G</math>-[[군의 작용|작용]]의 궤도
|-
| 균등 결합 도식 || <math>G\to\operatorname{Sym}(X)</math>가 [[추이적 작용]]
|-
| 대칭 결합 도식 || 임의의 <math>x,y\in X</math>에 대하여, <math>(g\cdot x,g\cdot y)=(y,x)</math>가 되는 <math>g\in G</math>가 존재
|-
| 자명 결합 도식 || <math>G\to\operatorname{Sym}(X)</math>가 2-[[추이적 작용]]
|-
| 이산 결합 도식 || <math>G\to\operatorname{Sym}(X)</math>가 자명한 작용 (즉, <math>g\cdot x=x\forall g\in G,\;x\in X</math>)
|}

== 역사 ==
1952년에 [[라지 찬드라 보스]]와 시마모토(T. Shimamoto)가 [[블록 설계]]의 이론에 대한 응용을 위해 결합 도식의 개념 및 용어를 도입하였다.<ref>{{저널 인용|last=Bose|first=Raj Chandra|저자링크=라지 찬드라 보스|last2=Shimamoto|first2=T.|title=Classification and analysis of partially balanced incomplete block designs with two associate classes|url=https://archive.org/details/sim_journal-of-the-american-statistical-association_1952-06_47_258/page/n41|journal=Journal of the American Statistical Association|year=1952|volume=47|pages=151–184|doi=10.1080/01621459.1952.10501161|zbl= 0048.11603|언어=en}}</ref> 보스와 시마모토의 논문에서, “결합 도식”({{llang|en|association scheme}})이라는 용어는 대칭 결합 대수를 뜻했다.

1959년에 [[라지 찬드라 보스]]와 데일 마시 메스너({{llang|en|Dale Marsh Mesner}})는 보스-메스너 대수를 도입하였다.<ref>{{저널 인용| last1=Bose|first1=Raj Chandra|저자링크=라지 찬드라 보스| last2=Mesner|first2=Dale Marsh|year=1959|title=On linear associative algebras corresponding to association schemes of partially balanced designs| url=https://archive.org/details/sim_annals-of-mathematical-statistics_1959-03_30_1/page/n22|journal=Annals of Mathematical Statistics|volume=30|issue=1|pages=21–38 | doi=10.1214/aoms/1177706356 | mr = 102157 | zbl=0089.15002 | jstor = 2237117|issn=0003-4851|언어=en}}</ref>

이후 도널드 고든 히그먼({{llang|en|Donald Gordon Higman}}, 1928~2006)이 1970년에 [[군론]]에서의 응용을 위하여 본 문서의 결합 도식과 동치인 개념을 도입하였으며, 히그먼은 이 개념을 “일관 구조”({{llang|en|coherent configuration}})라고 불렀다.<ref>{{저널 인용|이름=Donald Gordon|성=Higman|제목=
Coherent configurations Ⅰ|저널=Rendiconti del Seminario Matematico della Università di Padova|권=44|날짜=1970|쪽=1–25|url=http://www.numdam.org/item?id=RSMUP_1970__44__1_0|mr= 325420 |zbl=0279.05025 | 언어=en}}</ref>{{rp|6, §3}}

== 같이 보기 ==
* [[블록 설계]]
== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Association scheme}}
* {{웹 인용|url=http://www.maths.qmul.ac.uk/~rab/MTHM028/|제목=MAS417 / MTHM028. Association schemes and partially balanced designs|출판사=Queen Mary University of London|이름=Rosemary Anne |성=Bailey|날짜=2006-03-20|언어=en}}
* {{웹 인용|url=https://cameroncounts.wordpress.com/2014/06/08/terminology-association-scheme-or-coherent-configuration/|제목=Terminology: association scheme or coherent configuration?|이름=Peter|성=Cameron|날짜=2014-06-08|웹사이트=Peter Cameron’s Blog|언어=en}}
* {{웹 인용|url=http://www.math.is.tohoku.ac.jp/~combin/ac2014/docs/tanaka.pdf|제목=Delsarte 理論入門. Introduction to Delsarte theory|이름=Hajime|성=Tanaka|날짜=2014-06-16|언어=en}}

{{전거 통제}}

[[분류:분산 분석]]
[[분류:실험 설계]]
[[분류:대수적 조합론]]