결합 도식

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

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

### 조합론적 정의
**결합 도식** (X,\mathcal R)은 다음과 같은 데이터로 주어진다.
* 유한 집합 X
* X\times X의, n+1개의 부분 집합들 \mathcal R, |\mathcal R|=n+1
이는 다음 조건들을 만족시켜야 한다.
* ㉠ \mathcal R는 X\times X의 분할을 이룬다. 즉, R,R'\in\mathcal R이며 R\ne 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</math> 및 <math>(x,y)\in R</math>에 대하여, <math>|\{z\in X\colon x\sim_{R'}y\sim_{R*}z\}|\in\mathbb N는 (x,y)에 의존하지 않는다.
여기서
* R\in\mathcal R에 대하여, x\sim_Ry는 (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_iy\sim_jz\}|\qquad(x\sim_ky)
는 결합 도식의 **구조 상수**(構造常數, )라고 한다.

### 행렬을 통한 정의
**결합 도식** (X,n,\mathcal A)은 다음과 같은 데이터로 주어진다.
* 유한 집합 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}^nA_i는 모든 성분이 1인 k\times k 정사각 행렬이다.
* ㉡ \textstyle1_{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_iA_j는 \mathcal A의 원소들의 자연수 계수 선형 결합이다. 즉, 각 0\le i,j,k\le k에 대하여, \textstyle A_iA_j=\sum_{k=0}^np^k_{ij}A_k인 자연수 p^k_{ij}가 존재한다.

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

### 기하학적 정의
결합 도식의 개념은 거리 공간과 유사하게 정의될 수도 있다.

**결합 도식** (X,D,\partial)은 다음과 같은 데이터로 주어진다.
* 유한 집합 X
* 유한 집합 D
* 함수 \partial\colon X\times X\to D. 이는 **거리 함수**(距離函數, )라고 한다.
이는 다음 조건들을 만족시켜야 한다.
* ㉡ 임의의 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')의 **부분 결합 도식**(部分結合圖式, )이라고 한다.

### 결합 도식 준동형
다음이 주어졌다고 하자.
* 유한 집합 X 위의 결합 도식 (X,\mathcal R)
* 유한 집합 X' 위의 결합 도식 (X',\mathcal R')
그렇다면, **결합 도식 사상**() (f,g)\colon (X,\mathcal R)\to(X',\mathcal R')은 다음과 같은 데이터로 구성된다.
* 함수 f\colon X\to X'
* 함수 g\colon \mathcal R\to\mathcal R'
이는 다음 조건을 만족시켜야 한다.
:임의의 x,y\in X 및 R\in\mathcal R에 대하여, 만약 x\sim_Ry라면, f(x)\sim_{g(R)}f(y)이다.

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

## 종류
결합 도식 X에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 결합 도식을 **대칭 결합 도식**(對稱結合圖式, )이라고 한다.
* 조합론적 정의 (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)에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 결합 도식을 **가환 결합 도식**(可換結合圖式,)이라고 한다.
* 그 보스-메스너 대수가 가환환이다.
* 조합론적 정의에서, 임의의 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>이 다음 조건을 만족시킨다면, *'균등 결합 도식**(均等結合圖式, )이라고 한다.
* 조합론적 정의 <math>(X,\mathcal R)</math>에서, <math>\{(x,x)\colon x\in X\}\in\mathcal R</math>이다.
* 행렬을 통한 정의 <math>(X,\mathcal A)</math>에서, <math>1_\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>의 **올**()이라고 하자. 올들로 구성된 [[집합의 분할]]을 <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>의 **직접곱**(直接곱, )이라고 한다.

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

== 성질 ==
=== 구조 상수 ===
임의의 결합 도식 <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>은 다음을 만족시킨다.
:<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>
이에 따라, 대칭 결합 도식은 특별한 [[변 색칠]]이 주어진 유한 [[완전 그래프]]로 여겨질 수 있다.

=== 보스-메스너 대수 ===
(행렬을 통한 정의의) 결합 도식 <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>에 대응하는 **보스-메스너 대수**라고 한다 (흔히, 정수 계수 대신 실수나 복소수 계수가 사용된다).

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

[[아르틴-웨더번 정리]]에 따라서, 복소수 계수 보스-메스너 계수는 다음과 같은 꼴로 유일하게 표현된다.
:<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\mathsf J_.</math>
로 놓는다. 여기서 <math>\mathsf J_</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>이다.)

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

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

이에 따라, 만약 두 결합 도식 <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>
라면, 서로 **쌍대**()라고 한다. 즉, 반선형 변환()
:<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>
를 만족시킬 경우, 이들이 서로 쌍대라고 한다.

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

특히, [[해밍 결합 도식]]은 스스로의 쌍대이다.

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

그 구조 상수는 다음과 같다.
:<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>는 결합 도식을 이루며, 이를 **자명한 결합 도식**(自明-結合圖式, )이라고 한다. 그 구조 상수는 다음과 같다.
:<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> 역시 결합 도식을 이룬다. 이를 **이산 결합 도식**(離散結合圖式, )이라고 한다. 그러나 <math>|X|\ge2</math>일 경우 이는 균등 결합 도식이 아니다.

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

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


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

주어진 집합 <Math>X</math> 위의, 특별한 조건을 만족시키는 결합 도식의 수는 다음과 같다.


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


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

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

### 정추이적 작용
유한군 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\ne 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)는 결합 도식을 이룬다. 또한, 이 결합 도식이 각종 조건을 만족시킬 필요 충분 조건은 다음과 같다.

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

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

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

## 같이 보기
* 블록 설계
## 각주

## 외부 링크
* 
* 
* 
* 

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