결합 도식

조합론에서 '''결합 도식'''(結合圖式, ) 또는 '''일관 구조'''(一貫構造, )는 어떤 특별한 조건을 만족시키는 일련의 이항 관계들이 주어진 유한 집합이며, 변 색칠이 주어진 완전 그래프로도 간주될 수 있다. 주어진 결합 도식으로부터 그 구조를 나타내는 결합 대수인 '''보스-메스너 대수'''(बसु-Mesner代數, )가 존재한다.
결합 도식의 개념은 여러 가지로 정의될 수 있으나, 이 정의들은 모두 서로 동치이다.
=== 조합론적 정의 ===
'''결합 도식''' 은 다음과 같은 데이터로 주어진다.
* 유한 집합 
* 의, 개의 부분 집합들 , 
이는 다음 조건들을 만족시켜야 한다.
* ㉠ 는 의 분할을 이룬다. 즉, 이며 이라면 이며, 또한 이다.
* ㉡ 인 부분 집합 가 존재한다.
* ㉢ 
* ㉣ 임의의 에 대하여, 
* ㉤ 임의의  및 에 대하여, 는 에 의존하지 않는다.
여기서
* 에 대하여, x\sim_Ry는 를 뜻한다.
* 는 의 반대 이항 관계이다.
흔히, 의 원소는 으로 표기되며, 이 경우 이다. 또한,
:
는 결합 도식의 '''구조 상수'''(構造常數, )라고 한다.
=== 행렬을 통한 정의 ===
'''결합 도식''' 은 다음과 같은 데이터로 주어진다.
* 유한 집합 
* 자연수 
* 개의, 모든 성분이 0 또는 1인  정사각 행렬들의 족 .
이는 다음 조건들을 만족시켜야 한다.
* ㉠ 는 모든 성분이 1인  정사각 행렬이다.
* ㉡ 인 가 존재한다.
* ㉢ .
* ㉣ 임의의 A\in\mathcal A에 대하여, 
* ㉤ 임의의 에 대하여, 그 곱 는 의 원소들의 자연수 계수 선형 결합이다. 즉, 각 에 대하여, 인 자연수 가 존재한다.
이 두 정의는 서로 동치이다. 즉, 두 정의 사이를 번역하려면, 각 이항 관계 를 대신 정사각 행렬
:
로 치환하면 된다.
=== 기하학적 정의 ===
결합 도식의 개념은 거리 공간과 유사하게 정의될 수도 있다.
'''결합 도식''' 은 다음과 같은 데이터로 주어진다.
* 유한 집합 
* 유한 집합 
* 함수 . 이는 '''거리 함수'''(距離函數, )라고 한다.
이는 다음 조건들을 만족시켜야 한다.
* ㉡ 임의의 에 대하여, 만약 라면, 이다.
* ㉢ 은 전사 함수이다.
* ㉣ 임의의 에 대하여, 라면 
* ㉤ 임의의 에 대하여, 만약 라면, 이자 가 되는 전단사 함수 가 존재한다.
이 정의 역시 나머지 두 정의와 서로 동치이다. 즉, 각 에 대하여 이항 관계
:
를 대응시키면 된다.
=== 부분 결합 도식 ===
같은 집합  위의 두 결합 도식  및 에 대하여, 만약 이라면, 를 의 '''부분 결합 도식'''(部分結合圖式, )이라고 한다.
=== 결합 도식 준동형 ===
다음이 주어졌다고 하자.
* 유한 집합  위의 결합 도식 (X,\mathcal R)
* 유한 집합  위의 결합 도식 (X',\mathcal R')
그렇다면, '''결합 도식 사상'''() 은 다음과 같은 데이터로 구성된다.
* 함수 
* 함수 g\colon \mathcal R\to\mathcal R'
이는 다음 조건을 만족시켜야 한다.
:임의의  및 R\in\mathcal R에 대하여, 만약 라면, 이다.
이는 사실 이항 관계가 주어진 구조 사이의 준동형의 특수한 경우이다.
결합 도식 에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 결합 도식을 '''대칭 결합 도식'''(對稱結合圖式, )이라고 한다.
* 조합론적 정의 에서, 의 모든 원소는 대칭 관계이다. 즉, 만약 라면, 이다.
* 행렬을 통한 정의 에서, 모든 A\in\mathcal A는 대칭 행렬이다.
* 기하학적 정의 에서, 임의의 x,y\in X에 대하여 이다.
결합 도식 에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 결합 도식을 '''가환 결합 도식'''(可換結合圖式,)이라고 한다.
* 그 보스-메스너 대수가 가환환이다.
* 조합론적 정의에서, 임의의 R,R',R''\in\mathcal R 및 에 대하여, 
* 행렬을 통한 정의 에서, 임의의 A,B\in\mathcal A에 대하여 이다.
* 기하학적 정의 에서, 임의의 에 대하여, 가 되는 자기 전단사 함수 가 존재한다.
결합 도식 이 다음 조건을 만족시킨다면, '''균등 결합 도식'''(均等結合圖式, )이라고 한다.
* 조합론적 정의 에서, 이다.
* 행렬을 통한 정의 에서, 이다.
* 기하학적 정의 에서, 이다.
다음과 같은 포함 관계가 성립한다.
:대칭 결합 도식 ⊊ 가환 결합 도식 ⊊ 균등 결합 도식 ⊊ 결합 도식
=== 올 ===
결합 도식 이 주어졌을 때,  위에 다음과 같은 동치 관계를 정의할 수 있다.
:
이 동치 관계에 대한 동치류를 의 '''올'''()이라고 하자. 올들로 구성된 집합의 분할을 로 표기할 때, 다음이 성립한다.
:
'''증명:'''
임의의 가 주어졌으며, 귀류법을 사용하여
:
:
이라고 가정하자. 그렇다면,
:
:
이므로, 이는 결합 도식의 정의와 모순된다.
이에 따라, 결합 도식 의 임의의 올 이 주어졌을 때,
:
는 균등 결합 도식을 이룬다.
=== 직접곱 ===
유한 개의 결합 도식
:
:
이 주어졌다고 하자. 그렇다면, 곱집합
:
위에 이항 관계
:
:
를 줄 수 있다. 그렇다면, 는 결합 도식을 이루며, 이를 (X_i,\mathcal R_i)_{i\in I}의 '''직접곱'''(直接곱, )이라고 한다.
이는 군의 직접곱의 개념의 일반화이다.
=== 구조 상수 ===
임의의 결합 도식 의 구조 상수들 은 다음을 만족시킨다.
:
만약
:
:
:
일 때, 다음이 성립한다.
:
균등 결합 도식 의 구조 상수들 은 다음을 만족시킨다.
:
:
:
(여기서 는 크로네커 델타이다.)
=== 대칭 결합 도식에 대응되는 변 색칠 ===
대칭 결합 도식 이 주어졌다고 하자. 그렇다면, 의 원소를 꼭짓점들로 하는 완전 그래프  위에, 의 원소를 색으로 하는 변 색칠 을 정의할 수 있다.
:
이에 따라, 대칭 결합 도식은 특별한 변 색칠이 주어진 유한 완전 그래프로 여겨질 수 있다.
=== 보스-메스너 대수 ===
(행렬을 통한 정의의) 결합 도식 이 주어졌을 때, 의 선형 생성
:
은 정수 계수 결합 대수를 이룬다. 이를 에 대응하는 '''보스-메스너 대수'''라고 한다 (흔히, 정수 계수 대신 실수나 복소수 계수가 사용된다).
에르미트 수반에 대하여 닫혀 있는 복소수 행렬 결합 대수이므로, 복소수 계수 보스-메스너 대수는 항상 반단순 대수이다.
아르틴-웨더번 정리에 따라서, 복소수 계수 보스-메스너 계수는 다음과 같은 꼴로 유일하게 표현된다.
:
이에 따라, 위 분해에 등장하는 멱등원
:
들을 정의할 수 있으며, 이들은
:
를 만족시킨다 (는 크로네커 델타). 또한, 편의상
:
로 놓는다. 여기서 는 모든 성분이 1인  정사각 행렬(즉, 아다마르 곱의 항등원)이다. 이는 결합 도식의 공리에 따라 보스-메스너 대수의 원소이며, 0이 아닌 고윳값이 1개 밖에 없는 멱영원이므로 위 분해에 항상 등장한다.
특히, 를 로 전개하였을 때의 계수
:
를 정의할 수 있다.
=== 가환 결합 도식의 쌍대성 ===
가환 결합 도식 의 경우, 최소 멱등원의 수는 와 같으며, 멱영원들 은 보스-메스너 대수 의 기저를 이룬다. 이에 따라, 다음을 정의할 수 있다.
:
또한, 들은 모두 아다마르 곱에 대하여 닫혀 있으므로, 들의 아다마르 곱에 대한 구조 상수
:
를 정의할 수 있다. (아다마르 곱은 교환 법칙을 따르므로 이다.)
이에 따라, 다음과 같은 쌍대성이 존재한다.
 이항 연산
 아다마르 곱  
 행렬의 곱
 기저
  
 
 기저의 직교성
  
 
 멱등원 조건
 의 모든 성분은 0 또는 1 (아다마르 곱의 멱등원) 
 의 모든 고윳값은 0 또는 1 (행렬곱의 멱등원)
 항등원
  
 
 기저 원소의 쌍대성
  
  (각 성분의 복소켤레)
 기저의 합
  
 
 차수
  
 
 차수의 합
 
 
 구조 상수
 
 
 기저 변환
 
 
이 표에서, 배경색이 노란 칸은 가환 결합 도식일 경우에만 정의되는 것이다.
이에 따라, 만약 두 결합 도식 , 의 복소수 계수 보스-메스너 대수 , 가 각각
:
라면, 서로 '''쌍대'''()라고 한다. 즉, 반선형 변환()
:
:
:
:
를 만족시킬 경우, 이들이 서로 쌍대라고 한다.
아다마르 곱은 항상 교환 법칙을 따르므로, 쌍대성은 오직 두 가환 결합 도식 사이에만 존재할 수 있다.
특히, 해밍 결합 도식은 스스로의 쌍대이다.
다음은 인 대칭 결합 도식의 한 예이다. 여기서 이다.
:
 
 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
그 구조 상수는 다음과 같다.
:
:
여기서 가 수록되었다면 는 생략하였으며, 수록되지 않은 구조 상수는 모두 0이다.
=== 자명한 결합 도식 ===
크기가 2 이상인 임의의 유한 집합  위에
:
:
:
을 정의하면, 는 결합 도식을 이루며, 이를 '''자명한 결합 도식'''(自明-結合圖式, )이라고 한다. 그 구조 상수는 다음과 같다.
:
:
:
:
이는 사실 인 해밍 결합 도식과 같다.
=== 이산 결합 도식 ===
임의의 유한 집합  위에,
:
를 정의하면,  역시 결합 도식을 이룬다. 이를 '''이산 결합 도식'''(離散結合圖式, )이라고 한다. 그러나 일 경우 이는 균등 결합 도식이 아니다.
=== 작은 결합 도식 ===
크기 1의 결합 도식은 유일하며, 이는 대칭 결합 도식이다.
 
 A
 A
 0
크기 2의 결합 도식은 다음 두 가지가 있다.
+ (가)
 
 A 
 B
 A
 0 
 1
 B
 1 
 0
+ (나)
 
 A 
 B
 A
 0 
 2
 B
 3 
 1
(가)는 자명한 결합 도식이며, (나)는 이산 결합 도식이다. (가)는 대칭 결합 도식이지만, (나)는 균등 결합 도식이 아니다.
주어진 집합 X 위의, 특별한 조건을 만족시키는 결합 도식의 수는 다음과 같다.
  
 균등 결합 도식의 수 
 대칭 결합 도식의 수
 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
=== 해밍 결합 도식과 존슨 결합 도식 ===
임의의 곱집합  위에, 두 벡터 사이의 해밍 거리가 인 것을 각각 이항 관계로 삼으면, 이는 결합 도식을 이룬다. 이를 '''해밍 결합 도식'''이라고 한다.
특히, 일 때, 주어진 해밍 무게의 벡터들만을 취한 부분 결합 도식을 '''존슨 결합 도식'''이라고 한다.
=== 정추이적 작용 ===
유한군 의, 유한 집합  위의 왼쪽 정추이적 작용이 주어졌다고 하자. (특히, 이다.) 그렇다면,
:
:
를 정의하면, 는 결합 도식을 이루며, 그 구조 상수는
:
이다.
이에 대응하는 보스-메스너 대수는 군환
:
과 동형이다.
또한, 에 대응하는 결합 도식이 가환 결합 도식일 필요 충분 조건은 가 아벨 군인 것이다.
=== 일반적 군 작용 ===
유한군 의, 유한 집합  위의 왼쪽 작용이 주어졌다고 하자. 그렇다면, 는  위에 다음과 같이 작용한다.
:
그렇다면, 의 작용에 대한 궤도들은 의 분할 을 정의한다.
이 경우, 는 결합 도식을 이룬다. 또한, 이 결합 도식이 각종 조건을 만족시킬 필요 충분 조건은 다음과 같다.
 결합 도식 
 군의 작용
 올 
  위의 -작용의 궤도
 균등 결합 도식 
 가 추이적 작용
 대칭 결합 도식 
 임의의 에 대하여, 가 되는 가 존재
 자명 결합 도식 
 가 2-추이적 작용
 이산 결합 도식 
 가 자명한 작용 (즉, )
1952년에 라지 찬드라 보스와 시마모토(T. Shimamoto)가 블록 설계의 이론에 대한 응용을 위해 결합 도식의 개념 및 용어를 도입하였다. 보스와 시마모토의 논문에서, “결합 도식”()이라는 용어는 대칭 결합 대수를 뜻했다.
1959년에 라지 찬드라 보스와 데일 마시 메스너()는 보스-메스너 대수를 도입하였다.
이후 도널드 고든 히그먼(, 1928~2006)이 1970년에 군론에서의 응용을 위하여 본 문서의 결합 도식과 동치인 개념을 도입하였으며, 히그먼은 이 개념을 “일관 구조”()라고 불렀다.
* 
* 
* 
* 
분류:분산 분석
분류:실험 설계
분류:대수적 조합론