결합 도식

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

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

조합론적 정의 
결합 도식 은 다음과 같은 데이터로 주어진다.
 유한 집합 
 의, 개의 부분 집합들 , 
이는 다음 조건들을 만족시켜야 한다.
 ㉠ 는 의 분할을 이룬다. 즉, 이며 이라면 이며, 또한 이다.
 ㉡ 인 부분 집합 가 존재한다.
 ㉢ 
 ㉣ 임의의 에 대하여, 
 ㉤ 임의의  및 에 대하여, 는 에 의존하지 않는다.
여기서
 에 대하여, 는 를 뜻한다.
 는 의 반대 이항 관계이다.

흔히, 의 원소는 으로 표기되며, 이 경우 이다. 또한,

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

행렬을 통한 정의 
결합 도식 은 다음과 같은 데이터로 주어진다.
 유한 집합 
 자연수 
 개의, 모든 성분이 0 또는 1인  정사각 행렬들의 족 .
이는 다음 조건들을 만족시켜야 한다.
 ㉠ 는 모든 성분이 1인  정사각 행렬이다.
 ㉡ 인 가 존재한다.
 ㉢ .
 ㉣ 임의의 에 대하여, 
 ㉤ 임의의 에 대하여, 그 곱 는 의 원소들의 자연수 계수 선형 결합이다. 즉, 각 에 대하여, 인 자연수 가 존재한다.

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

로 치환하면 된다.

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

결합 도식 은 다음과 같은 데이터로 주어진다.
 유한 집합 
 유한 집합 
 함수 . 이는 거리 함수(距離函數, )라고 한다.
이는 다음 조건들을 만족시켜야 한다.
 ㉡ 임의의 에 대하여, 만약 라면, 이다.
 ㉢ 은 전사 함수이다.
 ㉣ 임의의 에 대하여, 라면 
 ㉤ 임의의 에 대하여, 만약 라면, 이자 가 되는 전단사 함수 가 존재한다.

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

를 대응시키면 된다.

부분 결합 도식 
같은 집합  위의 두 결합 도식  및 에 대하여, 만약 이라면, 를 의 부분 결합 도식(部分結合圖式, )이라고 한다.

결합 도식 준동형 
다음이 주어졌다고 하자.
 유한 집합  위의 결합 도식 
 유한 집합  위의 결합 도식 
그렇다면, 결합 도식 사상() 은 다음과 같은 데이터로 구성된다.
 함수 
 함수 
이는 다음 조건을 만족시켜야 한다.
임의의  및 에 대하여, 만약 라면, 이다.

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

종류 
결합 도식 에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 결합 도식을 대칭 결합 도식(對稱結合圖式, )이라고 한다.
 조합론적 정의 에서, 의 모든 원소는 대칭 관계이다. 즉, 만약 라면, 이다.
 행렬을 통한 정의 에서, 모든 는 대칭 행렬이다.
 기하학적 정의 에서, 임의의 에 대하여 이다.
결합 도식 에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 결합 도식을 가환 결합 도식(可換結合圖式,)이라고 한다.
 그 보스-메스너 대수가 가환환이다.
 조합론적 정의에서, 임의의  및 에 대하여, 
 행렬을 통한 정의 에서, 임의의 에 대하여 이다.
 기하학적 정의 에서, 임의의 에 대하여, 가 되는 자기 전단사 함수 가 존재한다.

결합 도식 이 다음 조건을 만족시킨다면, 균등 결합 도식(均等結合圖式, )이라고 한다.
 조합론적 정의 에서, 이다.
 행렬을 통한 정의 에서, 이다.
 기하학적 정의 에서, 이다.

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

연산

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

이 동치 관계에 대한 동치류를 의 올()이라고 하자. 올들로 구성된 집합의 분할을 로 표기할 때, 다음이 성립한다.

증명:
임의의 가 주어졌으며, 귀류법을 사용하여

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

이므로, 이는 결합 도식의 정의와 모순된다.
이에 따라, 결합 도식 의 임의의 올 이 주어졌을 때,

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

직접곱 
유한 개의 결합 도식

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

위에 이항 관계

를 줄 수 있다. 그렇다면, 는 결합 도식을 이루며, 이를 의 직접곱(直接곱, )이라고 한다.

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

성질

구조 상수 
임의의 결합 도식 의 구조 상수들 은 다음을 만족시킨다.

만약

일 때, 다음이 성립한다.

균등 결합 도식 의 구조 상수들 은 다음을 만족시킨다.

(여기서 는 크로네커 델타이다.)

대칭 결합 도식에 대응되는 변 색칠 
대칭 결합 도식 이 주어졌다고 하자. 그렇다면, 의 원소를 꼭짓점들로 하는 완전 그래프  위에, 의 원소를 색으로 하는 변 색칠 을 정의할 수 있다.

이에 따라, 대칭 결합 도식은 특별한 변 색칠이 주어진 유한 완전 그래프로 여겨질 수 있다.

보스-메스너 대수 
(행렬을 통한 정의의) 결합 도식 이 주어졌을 때, 의 선형 생성

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

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

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

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

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

를 만족시킨다 (는 크로네커 델타). 또한, 편의상

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

특히, 를 로 전개하였을 때의 계수

를 정의할 수 있다.

가환 결합 도식의 쌍대성 
가환 결합 도식 의 경우, 최소 멱등원의 수는 와 같으며, 멱영원들 은 보스-메스너 대수 의 기저를 이룬다. 이에 따라, 다음을 정의할 수 있다.

또한, 들은 모두 아다마르 곱에 대하여 닫혀 있으므로, 들의 아다마르 곱에 대한 구조 상수

를 정의할 수 있다. (아다마르 곱은 교환 법칙을 따르므로 이다.)

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

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

이에 따라, 만약 두 결합 도식 , 의 복소수 계수 보스-메스너 대수 , 가 각각

라면, 서로 쌍대()라고 한다. 즉, 반선형 변환()

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

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

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

예 
다음은 인 대칭 결합 도식의 한 예이다. 여기서 이다.
{| 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
|}

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

여기서 가 수록되었다면 는 생략하였으며, 수록되지 않은 구조 상수는 모두 0이다.

자명한 결합 도식 
크기가 2 이상인 임의의 유한 집합  위에

을 정의하면, 는 결합 도식을 이루며, 이를 자명한 결합 도식(自明-結合圖式, )이라고 한다. 그 구조 상수는 다음과 같다.

이는 사실 인 해밍 결합 도식과 같다.

이산 결합 도식 
임의의 유한 집합  위에,

를 정의하면,  역시 결합 도식을 이룬다. 이를 이산 결합 도식(離散結合圖式, )이라고 한다. 그러나 일 경우 이는 균등 결합 도식이 아니다.

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

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

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

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

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

임의의 곱집합  위에, 두 벡터 사이의 해밍 거리가 인 것을 각각 이항 관계로 삼으면, 이는 결합 도식을 이룬다. 이를 해밍 결합 도식이라고 한다.

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

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

를 정의하면, 는 결합 도식을 이루며, 그 구조 상수는

이다.

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

과 동형이다.

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

일반적 군 작용 
유한군 의, 유한 집합  위의 왼쪽 작용이 주어졌다고 하자. 그렇다면, 는  위에 다음과 같이 작용한다.

그렇다면, 의 작용에 대한 궤도들은 의 분할 을 정의한다.

이 경우, 는 결합 도식을 이룬다. 또한, 이 결합 도식이 각종 조건을 만족시킬 필요 충분 조건은 다음과 같다.

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

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

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

참고 문헌

외부 링크 
 
 
 
 

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