결합 도식

조합론에서 결합 도식(結合圖式, 영어: association scheme 어소시에이션 스킴^[*]) 또는 일관 구조(一貫構造, 영어: coherent configuration)는 어떤 특별한 조건을 만족시키는 일련의 이항 관계들이 주어진 유한 집합이며, 변 색칠이 주어진 완전 그래프로도 간주될 수 있다. 주어진 결합 도식으로부터 그 구조를 나타내는 결합 대수인 보스-메스너 대수(बसु-Mesner代數, 영어: Bose–Mesner algebra)가 존재한다.

정의

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

조합론적 정의

결합 도식 $(X,{\mathcal {R}})$은 다음과 같은 데이터로 주어진다.^{:2479, Definition 1:1, §1.1}

• 유한 집합 $X$
• $X\times X$의, $n+1$개의 부분 집합들 ${\mathcal {R}}$, $|{\mathcal {R}}|=n+1$

이는 다음 조건들을 만족시켜야 한다.

• ㉠ ${\mathcal {R}}$는 $X\times X$의 분할을 이룬다. 즉, $R,R'\in {\mathcal {R}}$이며 $R\neq R'$이라면 $R\cap R'=\varnothing$이며, 또한 $\textstyle \bigcup {\mathcal {R}}=X\times X$이다.
• ㉡ $\textstyle \{(x,x)\colon x\in X\}=\bigcup {\mathcal {R}}'$인 부분 집합 ${\mathcal {R}}'\subseteq {\mathcal {R}}$가 존재한다.
• ㉢ $\varnothing \not \in {\mathcal {R}}$
• ㉣ 임의의 $R\in {\mathcal {R}}$에 대하여, $R^{\operatorname {op} }\in {\mathcal {R}}$
• ㉤ 임의의 $R,R',R''\in {\mathcal {R}}$ 및 $(x,y)\in R$에 대하여, $|\{z\in X\colon x\sim _{R'}y\sim _{R''}z\}|\in \mathbb {N}$는 $(x,y)$에 의존하지 않는다.

여기서

• $R\in {\mathcal {R}}$에 대하여, $x\sim _{R}y$는 $(x,y)\in R$를 뜻한다.
• $R^{\operatorname {op} }=\{(y,x)\colon (x,y)\in R\}$는 $R$의 반대 이항 관계이다.

흔히, ${\mathcal {R}}$의 원소는 $(R_{0},R_{1},\dotsc ,R_{n})$으로 표기되며, 이 경우 $R_{0}=\{(x,x)\colon x\in X\}$이다. 또한,

$p_{ij}^{k}=|\{z\in X\colon x\sim _{i}y\sim _{j}z\}|\qquad (x\sim _{k}y)$

는 결합 도식의 구조 상수(構造常數, 영어: structure constant)라고 한다.

행렬을 통한 정의

결합 도식 $(X,n,{\mathcal {A}})$은 다음과 같은 데이터로 주어진다.^{:13–14, §1.3}

• 유한 집합 $X=\{0,1,\dotsc ,q-1\}$
• 자연수 $n$
• $n$개의, 모든 성분이 0 또는 1인 $q\times q$ 정사각 행렬들의 족 ${\mathcal {A}}=\{A_{0},A_{1},\dotsc ,A_{n}\}$.

이는 다음 조건들을 만족시켜야 한다.

• ㉠ $\textstyle \sum _{i=0}^{n}A_{i}$는 모든 성분이 1인 $k\times k$ 정사각 행렬이다.
• ㉡ $\textstyle 1_{k\times k}=\sum {\mathcal {A}}'$인 ${\mathcal {A}}'\subseteq {\mathcal {A}}$가 존재한다.
• ㉢ $0_{k\times k}\not \in {\mathcal {A}}$.
• ㉣ 임의의 $A\in {\mathcal {A}}$에 대하여, $A^{\top }\in {\mathcal {A}}$
• ㉤ 임의의 $A_{i},A_{j}\in {\mathcal {A}}$에 대하여, 그 곱 $A_{i}A_{j}$는 ${\mathcal {A}}$의 원소들의 자연수 계수 선형 결합이다. 즉, 각 $0\leq i,j,k\leq k$에 대하여, $\textstyle A_{i}A_{j}=\sum _{k=0}^{n}p_{ij}^{k}A_{k}$인 자연수 $p_{ij}^{k}$가 존재한다.

이 두 정의는 서로 동치이다. 즉, 두 정의 사이를 번역하려면, 각 이항 관계 $\sim _{i}$를 대신 정사각 행렬

$(A_{i})_{x,y}=x\sim _{i}y\qquad (x,y\in X)$

로 치환하면 된다.

기하학적 정의

결합 도식의 개념은 거리 공간과 유사하게 정의될 수도 있다.^{:2479, §Ⅱ.A}

결합 도식 $(X,D,\partial )$은 다음과 같은 데이터로 주어진다.

• 유한 집합 $X$
• 유한 집합 $D$
• 함수 $\partial \colon X\times X\to D$. 이는 거리 함수(距離函數, 영어: distance)라고 한다.

이는 다음 조건들을 만족시켜야 한다.

• ㉡ 임의의 $x,y,z\in X$에 대하여, 만약 $\partial (x,x)=\partial (y,z)$라면, $y=z$이다.
• ㉢ $\partial$은 전사 함수이다.
• ㉣ 임의의 $x,y,x',y'\in X$에 대하여, $\partial (x,y)=\partial (x',y')$라면 $\partial (y,x)=\partial (y',x')$
• ㉤ 임의의 $x,y,x',y'\in X$에 대하여, 만약 $\partial (x,y)=\partial (x',y')$라면, $\forall z\in X\colon \partial (x,z)=\partial (x',f(z))$이자 $\forall z\in X\colon \partial (z,y)=\partial (f(z),y')$가 되는 전단사 함수 $f\colon X\to X$가 존재한다.

이 정의 역시 나머지 두 정의와 서로 동치이다. 즉, 각 $\alpha \in D$에 대하여 이항 관계

$x\sim _{\alpha }y\iff \partial (x,y)=\alpha$

를 대응시키면 된다.

부분 결합 도식

같은 집합 $X$ 위의 두 결합 도식 $(X,{\mathcal {R}})$ 및 $(X,{\mathcal {R}}')$에 대하여, 만약 ${\mathcal {R}}\subseteq {\mathcal {R}}'$이라면, $(X,{\mathcal {R}})$를 $(X,{\mathcal {R}}')$의 부분 결합 도식(部分結合圖式, 영어: subscheme)이라고 한다.

결합 도식 준동형

다음이 주어졌다고 하자.

• 유한 집합 $X$ 위의 결합 도식 $(X,{\mathcal {R}})$
• 유한 집합 $X'$ 위의 결합 도식 $(X',{\mathcal {R}}')$

그렇다면, 결합 도식 사상(영어: morphism of association schemes) $(f,g)\colon (X,{\mathcal {R}})\to (X',{\mathcal {R}}')$은 다음과 같은 데이터로 구성된다.^{:83, Chapter 5}

• 함수 $f\colon X\to X'$
• 함수 $g\colon {\mathcal {R}}\to {\mathcal {R}}'$

이는 다음 조건을 만족시켜야 한다.

임의의 $x,y\in X$ 및 $R\in {\mathcal {R}}$에 대하여, 만약 $x\sim _{R}y$라면, $f(x)\sim _{g(R)}f(y)$이다.

이는 사실 이항 관계가 주어진 구조 사이의 준동형의 특수한 경우이다.

종류

결합 도식 $X$에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 결합 도식을 대칭 결합 도식(對稱結合圖式, 영어: symmetric association scheme)이라고 한다.^{:2479, §II.A}

• 조합론적 정의 $(X,{\mathcal {R}})$에서, ${\mathcal {R}}$의 모든 원소는 대칭 관계이다. 즉, 만약 $R\in {\mathcal {R}}$라면, $R=R^{\operatorname {op} }$이다.
• 행렬을 통한 정의 $(X,{\mathcal {A}})$에서, 모든 $A\in {\mathcal {A}}$는 대칭 행렬이다.
• 기하학적 정의 $(X,\partial )$에서, 임의의 $x,y\in X$에 대하여 $\partial (x,y)=\partial (y,x)$이다.

결합 도식 $(X,{\mathcal {R}})$에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 결합 도식을 가환 결합 도식(可換結合圖式,영어: commutative association scheme)이라고 한다.

• 그 보스-메스너 대수가 가환환이다.
• 조합론적 정의에서, 임의의 $R,R',R''\in {\mathcal {R}}$ 및 $(x,y)\in R$에 대하여, $|\{z\in X\colon x\sim _{R'}z\sim _{R''}y\}|=|\{z\in X\colon x\sim _{R''}z\sim _{R'}y\}|$
• 행렬을 통한 정의 $(X,{\mathcal {A}})$에서, 임의의 $A,B\in {\mathcal {A}}$에 대하여 $AB=BA$이다.
• 기하학적 정의 $(X,\partial )$에서, 임의의 $x,y\in X$에 대하여, $\forall z\in X\colon (\partial (x,z),\partial (z,y))=(\partial (y,f(z)),\partial (f(z),x))$가 되는 자기 전단사 함수 $f\colon X\to X$가 존재한다.

결합 도식 $(X,{\mathcal {R}})$이 다음 조건을 만족시킨다면, 균등 결합 도식(均等結合圖式, 영어: homogeneous association scheme)이라고 한다.

• 조합론적 정의 $(X,{\mathcal {R}})$에서, $\{(x,x)\colon x\in X\}\in {\mathcal {R}}$이다.
• 행렬을 통한 정의 $(X,{\mathcal {A}})$에서, $1_{|X|\times |X|}\in {\mathcal {A}}$이다.
• 기하학적 정의 $(X,\partial )$에서, $\forall x,y\in X\colon \partial (x,x)=\partial (y,y)$이다.

다음과 같은 포함 관계가 성립한다.

대칭 결합 도식 ⊊ 가환 결합 도식 ⊊ 균등 결합 도식 ⊊ 결합 도식

연산

올

결합 도식 $(X,\partial )$이 주어졌을 때, $X$ 위에 다음과 같은 동치 관계를 정의할 수 있다.

$x\approx y\iff \partial (x,x)=\partial (y,y)$

이 동치 관계에 대한 동치류를 $X$의 올(영어: fibre)이라고 하자. 올들로 구성된 집합의 분할을 $(X_{\alpha })_{\alpha \in I}$로 표기할 때, 다음이 성립한다.

$\forall R\in {\mathcal {R}}\exists \alpha ,\beta \in I\colon R\subseteq X_{\alpha }\times X_{\beta }$

증명:

임의의 $x,y,y'\in X$가 주어졌으며, 귀류법을 사용하여

$\partial (x,y)=\partial (x,y')$

$\partial (y,y)\neq \partial (y',y')$

이라고 가정하자. 그렇다면,

$\{z\in X\colon \partial (x,z)=\partial (x,y),\;\partial (z,y)=\partial (y,y)\}=\{y\}$

$\{z\in X\colon \partial (x,z)=\partial (x,y),\;\partial (z,y')=\partial (y,y)\}=\varnothing$

이므로, 이는 결합 도식의 정의와 모순된다.

이에 따라, 결합 도식 $(X,\partial )$의 임의의 올 $X_{i}$이 주어졌을 때,

$(X_{i},\partial \upharpoonright X_{i}^{2})$

는 균등 결합 도식을 이룬다.

직접곱

유한 개의 결합 도식

$(X_{i},{\mathcal {R}}_{i})_{i\in I}$

$|I|<\aleph _{0}$

이 주어졌다고 하자. 그렇다면, 곱집합

$X=\prod _{i\in I}X_{i}$

위에 이항 관계

${\mathcal {R}}=\prod _{i\in I}{\mathcal {R}}_{i}$

$(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}$

를 줄 수 있다. 그렇다면, $(X,{\mathcal {R}})$는 결합 도식을 이루며, 이를 $(X_{i},{\mathcal {R}}_{i})_{i\in I}$의 직접곱(直接곱, 영어: direct product)이라고 한다.^{:140, Chapter 7}

이는 군의 직접곱의 개념의 일반화이다.

성질

구조 상수

임의의 결합 도식 $X$의 구조 상수들 $(p_{ij}^{k})_{1\leq i,j,k\leq n}$은 다음을 만족시킨다.

$\sum _{i,j,k=0}^{n}p_{ij}^{k}|R_{k}|=|X|^{3}$

만약

$R_{i}^{\operatorname {op} }=R_{\bar {\imath }}$

$R_{j}^{\operatorname {op} }=R_{\bar {\jmath }}$

$R_{k}^{\operatorname {op} }=R_{\bar {k}}$

일 때, 다음이 성립한다.

$p_{jk}^{i}=p_{{\bar {k}}{\bar {\jmath }}}^{\bar {\imath }}$

균등 결합 도식 $(X,{\mathcal {R}})$의 구조 상수들 $(p_{ij}^{k})_{1\leq i,j,k\leq n}$은 다음을 만족시킨다.^{:26, Exercise 1.1(a)}

$p_{0i}^{j}=p_{i0}^{j}=\delta _{i}^{j}$

$p_{ij}^{0}=p_{{\bar {\jmath }}{\bar {\imath }}}^{0}=\delta _{j}^{\bar {\imath }}p_{i{\bar {\imath }}}^{0}$

$\sum _{i,j=0}^{n}p_{ij}^{0}=\sum _{i=0}^{n}p_{i{\bar {\imath }}}^{0}=|X|$

(여기서 $\delta _{i}^{j}$는 크로네커 델타이다.)

대칭 결합 도식에 대응되는 변 색칠

대칭 결합 도식 $(X,{\mathcal {R}})$이 주어졌다고 하자. 그렇다면, $X$의 원소를 꼭짓점들로 하는 완전 그래프 $K_{X}$ 위에, ${\mathcal {R}}\setminus \{R_{0}\}$의 원소를 색으로 하는 변 색칠 $c\colon \operatorname {E} (K_{X})\to {\mathcal {R}}\setminus \{R_{0}\}$을 정의할 수 있다.

$c\colon (x,y)\mapsto R\iff (x,y)\in R\qquad (R\in {\mathcal {R}},\;R\neq R_{0})$

이에 따라, 대칭 결합 도식은 특별한 변 색칠이 주어진 유한 완전 그래프로 여겨질 수 있다.^{:7–8, §1.2}

보스-메스너 대수

(행렬을 통한 정의의) 결합 도식 $(X,{\mathcal {A}})$이 주어졌을 때, ${\mathcal {A}}$의 선형 생성

$\operatorname {Span} _{\mathbb {Z} }{\mathcal {A}}\subseteq \operatorname {Mat} (|X|,|X|;\mathbb {Z} )$

은 정수 계수 결합 대수를 이룬다. 이를 $X$에 대응하는 보스-메스너 대수라고 한다 (흔히, 정수 계수 대신 실수나 복소수 계수가 사용된다).^{:2480, Definition 2}

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

아르틴-웨더번 정리에 따라서, 복소수 계수 보스-메스너 계수는 다음과 같은 꼴로 유일하게 표현된다.

$\prod _{a=1}^{k}\operatorname {Mat} (m_{a},m_{a};\mathbb {C} )$

이에 따라, 위 분해에 등장하는 멱등원

$E_{a}=(0,0,\dotsc ,0,1_{m_{a}\times m_{a}},0,\dotsc ,0)$

들을 정의할 수 있으며, 이들은

$E_{a}E_{b}=\delta _{ab}E_{a}\qquad (a,b\in \{0,\dotsc ,k\})$

를 만족시킨다 ($\delta _{ab}$는 크로네커 델타). 또한, 편의상

$E_{0}={\frac {1}{|X|}}{\mathsf {J}}_{|X|\times |X|}.$

로 놓는다. 여기서 ${\mathsf {J}}_{|X|\times |X|}$는 모든 성분이 1인 $|X|\times |X|$ 정사각 행렬(즉, 아다마르 곱의 항등원)이다. 이는 결합 도식의 공리에 따라 보스-메스너 대수의 원소이며, 0이 아닌 고윳값이 1개 밖에 없는 멱영원이므로 위 분해에 항상 등장한다.

특히, $E_{a}$를 $D_{i}$로 전개하였을 때의 계수

$|X|E_{a}=\sum _{i=0}^{n}Q_{ai}D_{j}$

를 정의할 수 있다.

가환 결합 도식의 쌍대성

가환 결합 도식 $X$의 경우, 최소 멱등원의 수는 $|X|=n$와 같으며, 멱영원들 $(E_{a})_{0\leq a\leq n}$은 보스-메스너 대수 ${\mathcal {A}}$의 기저를 이룬다. 이에 따라, 다음을 정의할 수 있다.

$D_{i}=\sum _{a=0}^{n}P_{i,a}E_{a}$

또한, $D_{i}$들은 모두 아다마르 곱에 대하여 닫혀 있으므로, $E_{a}$들의 아다마르 곱에 대한 구조 상수

$E_{a}\bigcirc E_{b}=q_{ab}^{c}E_{c}$

를 정의할 수 있다. (아다마르 곱은 교환 법칙을 따르므로 $q_{ab}^{c}=q_{ba}^{c}$이다.)

이에 따라, 다음과 같은 쌍대성이 존재한다.

이항 연산	아다마르 곱 $\bigcirc$	행렬의 곱
기저	$D_{i}$	$E_{a}$
기저의 직교성	$D_{i}\bigcirc D_{j}=\delta _{ij}D_{i}$	$E_{a}E_{b}=\delta _{ab}E_{a}$
멱등원 조건	$D_{i}$의 모든 성분은 0 또는 1 (아다마르 곱의 멱등원)	$E_{a}$의 모든 고윳값은 0 또는 1 (행렬곱의 멱등원)
항등원	$D_{0}=1_{n\times n}$	$E_{0}={\mathsf {J}}_{n\times n}/|X|$
기저 원소의 쌍대성	$D_{\bar {\imath }}=D_{i}^{\top }$	$E_{\bar {a}}=E_{a}^{\top }={\bar {E}}_{a}$ (각 성분의 복소켤레)
기저의 합	$\textstyle \sum _{i}D_{i}={\mathsf {J}}_{|X|\times |X|}$	$\textstyle \sum _{a}E_{a}=1_{|X|\times |X|}$
차수	$v_{i}=\{y\in X\colon x\sim _{i}y\}\;(\forall x\in X)$	$m_{a}=\dim _{\mathbb {C} }\operatorname {im} E_{a}$
차수의 합	$\textstyle \sum _{i}v_{i}=|X|$	$\textstyle \sum _{a}m_{a}=|X|$
구조 상수	$D_{i}D_{j}=p_{ij}^{k}D_{k}$	$|X|E_{a}\bigcirc E_{b}=q_{ab}^{c}E_{c}$
기저 변환	$\textstyle D_{i}=\sum _{a=0}^{n}P_{ia}E_{a}$	$\textstyle E_{a}=\sum _{i=0}^{n}Q_{ai}D_{i}$

이 표에서, 배경색이 노란 칸은 가환 결합 도식일 경우에만 정의되는 것이다.

이에 따라, 만약 두 결합 도식 $X$, $Y$의 복소수 계수 보스-메스너 대수 ${\mathcal {A}}_{X}$, ${\mathcal {A}}_{Y}$가 각각

$({\mathcal {A}}_{X},\cdot ,\bigcirc ,(D_{i})_{i})\cong ({\mathcal {A}}_{Y},\bigcirc ,\cdot ,(E_{a})_{a})$

라면, 서로 쌍대(영어: dual)라고 한다. 즉, 반선형 변환(영어: antilinear map)

$f\colon {\mathcal {A}}_{X}\to {\mathcal {A}}_{Y}$

$f(\lambda M)={\bar {\lambda }}f(M)\qquad (\lambda \in \mathbb {C} ,\;M\in {\mathcal {A}}_{X})$

$f(MN)=f(M)\bigcirc f(N)$

$f(M\bigcirc N)=f(M)f(N)$

를 만족시킬 경우, 이들이 서로 쌍대라고 한다.

아다마르 곱은 항상 교환 법칙을 따르므로, 쌍대성은 오직 두 가환 결합 도식 사이에만 존재할 수 있다.

특히, 해밍 결합 도식은 스스로의 쌍대이다.^{:2482, Example 1 (continued)}

예

다음은 $n=3$인 대칭 결합 도식의 한 예이다. 여기서 $X=\{{\mathsf {A}},{\mathsf {B}},{\mathsf {C}},{\mathsf {D}},{\mathsf {E}},{\mathsf {F}}\}$이다.

	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

그 구조 상수는 다음과 같다.

$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}$

$2=p_{11}^{0}=p_{33}^{0}=p_{13}^{2}$

여기서 $p_{ij}^{k}$가 수록되었다면 $p_{ji}^{k}$는 생략하였으며, 수록되지 않은 구조 상수는 모두 0이다.

자명한 결합 도식

크기가 2 이상인 임의의 유한 집합 $X$ 위에

$R_{0}=\{(x,x)\colon x\in X\}$

$R_{1}=X\times X\setminus R_{0}$

${\mathcal {R}}=\{R_{0},R_{1}\}$

을 정의하면, $(X,2,{\mathcal {R}})$는 결합 도식을 이루며, 이를 자명한 결합 도식(自明-結合圖式, 영어: trivial association scheme)이라고 한다.^:§1.1 그 구조 상수는 다음과 같다.

$p_{00}^{0}=p_{01}^{1}=p_{10}^{1}=1$

$p_{00}^{1}=p_{01}^{0}=p_{10}^{0}=0$

$p_{11}^{0}=|X|-1$

$p_{11}^{1}=|X|-2$

이는 사실 $n=1$인 해밍 결합 도식과 같다.

이산 결합 도식

임의의 유한 집합 $X$ 위에,

${\mathcal {R}}=\{\{(x,y)\}\colon x,y\in X\}$

를 정의하면, $(X,{\mathcal {R}})$ 역시 결합 도식을 이룬다. 이를 이산 결합 도식(離散結合圖式, 영어: discrete association scheme)이라고 한다.^:§1.1 그러나 $|X|\geq 2$일 경우 이는 균등 결합 도식이 아니다.

작은 결합 도식

크기 1의 결합 도식은 유일하며, 이는 대칭 결합 도식이다.

	A
A	0

크기 2의 결합 도식은 다음 두 가지가 있다.

(가)

	A	B
A	0	1
B	1	0

(나)

	A	B
A	0	2
B	3	1

(가)는 자명한 결합 도식이며, (나)는 이산 결합 도식이다. (가)는 대칭 결합 도식이지만, (나)는 균등 결합 도식이 아니다.

주어진 집합 $X$ 위의, 특별한 조건을 만족시키는 결합 도식의 수는 다음과 같다.^{:Table 1}

$|X|$	균등 결합 도식의 수 (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

해밍 결합 도식과 존슨 결합 도식

 이 부분의 본문은 해밍 결합 도식입니다.

 이 부분의 본문은 존슨 결합 도식입니다.

임의의 곱집합 $X=F^{n}$ 위에, 두 벡터 사이의 해밍 거리가 $0,1,\dotsc ,n$인 것을 각각 이항 관계로 삼으면, 이는 결합 도식을 이룬다. 이를 해밍 결합 도식이라고 한다.

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

정추이적 작용

유한군 $G$의, 유한 집합 $X$ 위의 왼쪽 정추이적 작용이 주어졌다고 하자. (특히, $|G|=|X|$이다.) 그렇다면,

$n=|G|$

${\mathcal {R}}=\{\{(x,gx)\colon x\in X\}\colon g\in G\}$

를 정의하면, $(X,n,{\mathcal {R}})$는 결합 도식을 이루며, 그 구조 상수는

$p_{gh}^{k}={\begin{cases}1&gh=k\\0&gh\neq k\end{cases}}\qquad (g,h,k\in G)$

이다.

이에 대응하는 보스-메스너 대수는 군환

$\mathbb {Z} [G]$

과 동형이다.

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

일반적 군 작용

유한군 $G$의, 유한 집합 $X$ 위의 왼쪽 작용이 주어졌다고 하자. 그렇다면, $G$는 $X^{2}=X\times X$ 위에 다음과 같이 작용한다.

$g\cdot (x,y)=(g\cdot x,g\cdot y)\qquad (x,y\in X,\;g\in G)$

그렇다면, $G$의 작용에 대한 궤도들은 $X^{2}$의 분할 $X^{2}/G$을 정의한다.

이 경우, $(X,X^{2}/G)$는 결합 도식을 이룬다.^{:2482, §II.D} 또한, 이 결합 도식이 각종 조건을 만족시킬 필요 충분 조건은 다음과 같다.

결합 도식	군의 작용
올	$X$ 위의 $G$-작용의 궤도
균등 결합 도식	$G\to \operatorname {Sym} (X)$가 추이적 작용
대칭 결합 도식	임의의 $x,y\in X$에 대하여, $(g\cdot x,g\cdot y)=(y,x)$가 되는 $g\in G$가 존재
자명 결합 도식	$G\to \operatorname {Sym} (X)$가 2-추이적 작용
이산 결합 도식	$G\to \operatorname {Sym} (X)$가 자명한 작용 (즉, $g\cdot x=x\forall g\in G,\;x\in X$)

역사

1952년에 라지 찬드라 보스와 시마모토(T. Shimamoto)가 블록 설계의 이론에 대한 응용을 위해 결합 도식의 개념 및 용어를 도입하였다. 보스와 시마모토의 논문에서, “결합 도식”(영어: association scheme)이라는 용어는 대칭 결합 대수를 뜻했다.

1959년에 라지 찬드라 보스와 데일 마시 메스너(영어: Dale Marsh Mesner)는 보스-메스너 대수를 도입하였다.

이후 도널드 고든 히그먼(영어: Donald Gordon Higman, 1928~2006)이 1970년에 군론에서의 응용을 위하여 본 문서의 결합 도식과 동치인 개념을 도입하였으며, 히그먼은 이 개념을 “일관 구조”(영어: coherent configuration)라고 불렀다.^{:6, §3}

외부 링크

• “Association scheme”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Bailey, Rosemary Anne (2006년 3월 20일). “MAS417 / MTHM028. Association schemes and partially balanced designs” (영어). Queen Mary University of London. 
• Cameron, Peter (2014년 6월 8일). “Terminology: association scheme or coherent configuration?”. 《Peter Cameron’s Blog》 (영어). 
• Tanaka, Hajime (2014년 6월 16일). “Delsarte 理論入門. Introduction to Delsarte theory” (PDF) (영어).