결합 도식

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

정의편집

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

조합론적 정의편집

결합 도식  은 다음과 같은 데이터로 주어진다.[3]:2479, Definition 1[1]:1, §1.1

  • 유한 집합  
  •  의,  개의 부분 집합 ,  

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

  •   분할을 이룬다. 즉,  이며  이라면  이며, 또한  이다.
  •  부분 집합  가 존재한다.
  •  
  • ㉣ 임의의  에 대하여,  
  • ㉤ 임의의   에 대하여,   에 의존하지 않는다.

여기서

  •  에 대하여,   를 뜻한다.
  •   의 반대 이항 관계이다.

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

 

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

행렬을 통한 정의편집

결합 도식  은 다음과 같은 데이터로 주어진다.[1]:13–14, §1.3

  • 유한 집합  
  • 자연수  
  •  개의, 모든 성분이 0 또는 1인   정사각 행렬들의 족  .

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

  •  는 모든 성분이 1인   정사각 행렬이다.
  •   가 존재한다.
  •  .
  • ㉣ 임의의  에 대하여,  
  • ㉤ 임의의  에 대하여, 그 곱   의 원소들의 자연수 계수 선형 결합이다. 즉, 각  에 대하여,  인 자연수  가 존재한다.

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

 

로 치환하면 된다.

기하학적 정의편집

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

결합 도식  은 다음과 같은 데이터로 주어진다.

  • 유한 집합  
  • 유한 집합  
  • 함수  . 이는 거리 함수(距離函數, 영어: distance)라고 한다.

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

  • ㉡ 임의의  에 대하여, 만약  라면,  이다.
  •  전사 함수이다.
  • ㉣ 임의의  에 대하여,  라면  
  • ㉤ 임의의  에 대하여, 만약  라면,  이자  가 되는 전단사 함수  가 존재한다.

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

 

를 대응시키면 된다.

부분 결합 도식편집

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

결합 도식 준동형편집

다음이 주어졌다고 하자.

  • 유한 집합   위의 결합 도식  
  • 유한 집합   위의 결합 도식  

그렇다면, 결합 도식 사상(영어: morphism of association schemes)  은 다음과 같은 데이터로 구성된다.[2]:83, Chapter 5

  • 함수  
  • 함수  

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

임의의   에 대하여, 만약  라면,  이다.

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

종류편집

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

  • 조합론적 정의  에서,  의 모든 원소는 대칭 관계이다. 즉, 만약  라면,  이다.
  • 행렬을 통한 정의  에서, 모든  대칭 행렬이다.
  • 기하학적 정의  에서, 임의의  에 대하여  이다.

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

  • 그 보스-메스너 대수가 가환환이다.
  • 조합론적 정의에서, 임의의   에 대하여,  
  • 행렬을 통한 정의  에서, 임의의  에 대하여  이다.
  • 기하학적 정의  에서, 임의의  에 대하여,  가 되는 자기 전단사 함수  가 존재한다.

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

  • 조합론적 정의  에서,  이다.
  • 행렬을 통한 정의  에서,  이다.
  • 기하학적 정의  에서,  이다.

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

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

연산편집

편집

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

 

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

 

증명:

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

 
 

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

 
 

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

이에 따라, 결합 도식  의 임의의 올  이 주어졌을 때,

 

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

직접곱편집

유한 개의 결합 도식

 
 

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

 

위에 이항 관계

 
 

를 줄 수 있다. 그렇다면,  는 결합 도식을 이루며, 이를  직접곱(直接곱, 영어: direct product)이라고 한다.[2]:140, Chapter 7

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

성질편집

구조 상수편집

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

 

만약

 
 
 

일 때, 다음이 성립한다.

 

균등 결합 도식  의 구조 상수들  은 다음을 만족시킨다.[1]:26, Exercise 1.1(a)

 
 
 

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

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

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

 

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

보스-메스너 대수편집

(행렬을 통한 정의의) 결합 도식  이 주어졌을 때,  선형 생성

 

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

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

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

 

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

 

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

 

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

 

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

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

 

를 정의할 수 있다.

가환 결합 도식의 쌍대성편집

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

 

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

 

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

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

이항 연산 아다마르 곱   행렬의 곱
기저    
기저의 직교성    
멱등원 조건  의 모든 성분은 0 또는 1 (아다마르 곱멱등원)  의 모든 고윳값은 0 또는 1 (행렬곱의 멱등원)
항등원    
기저 원소의 쌍대성     (각 성분의 복소켤레)
기저의 합    
차수    
차수의 합    
구조 상수    
기저 변환    

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

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

 

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

 
 
 
 

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

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

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

편집

다음은  인 대칭 결합 도식의 한 예이다. 여기서  이다.

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 이상인 임의의 유한 집합   위에

 
 
 

을 정의하면,  는 결합 도식을 이루며, 이를 자명한 결합 도식(自明-結合圖式, 영어: trivial association scheme)이라고 한다.[6]:§1.1 그 구조 상수는 다음과 같다.

 
 
 
 

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

이산 결합 도식편집

임의의 유한 집합   위에,

 

를 정의하면,   역시 결합 도식을 이룬다. 이를 이산 결합 도식(離散結合圖式, 영어: discrete association scheme)이라고 한다.[6]:§1.1 그러나  일 경우 이는 균등 결합 도식이 아니다.

작은 결합 도식편집

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

A
A 0

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

(가)
A B
A 0 1
B 1 0
(나)
A B
A 0 2
B 3 1

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

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

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

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

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

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

정추이적 작용편집

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

 
 

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

 

이다.

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

 

과 동형이다.

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

일반적 군 작용편집

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

 

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

이 경우,  는 결합 도식을 이룬다.[3]:2482, §II.D 또한, 이 결합 도식이 각종 조건을 만족시킬 필요 충분 조건은 다음과 같다.

결합 도식 군의 작용
  위의  -작용의 궤도
균등 결합 도식  추이적 작용
대칭 결합 도식 임의의  에 대하여,  가 되는  가 존재
자명 결합 도식  가 2-추이적 작용
이산 결합 도식  가 자명한 작용 (즉,  )

역사편집

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

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

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

참고 문헌편집

  1. Bailey, Rosemary Anne (2004). 《Association schemes: designed experiments, algebra and combinatorics》 (영어). Cambridge University Press. doi:10.1017/CBO9780511610882. ISBN 978-0-521-82446-0. MR 2047311. 
  2. Zieschang, Paul-Hermann (2005). 《Theory of association schemes》. Springer Monographs in Mathematics (영어). Springer-Verlag. doi:10.1007/3-540-30593-9. ISBN 978-3-540-26136-0. ISSN 1439-7382. 
  3. Delsarte, Philippe; Levenshtein, Vladimir Iosifovich (1998년 10월). “Association schemes and coding theory”. 《Institute of Electrical and Electronics Engineers Transactions on Information Theory》 (영어) 44 (6): 2477–2504. doi:10.1109/18.720545. ISSN 0018-9448. 
  4. Seidel, Johan Jacob (1991). “Introduction to association schemes”. 《Séminaire Lotharingien de Combinatoire》 (영어) 26: B26g. ISSN 1286-4889. Zbl 0981.05535. 
  5. Neumaier, Arnold (1989년 3월). “Duality in coherent configurations”. 《Combinatorica》 (영어) 9 (1): 59–67. doi:10.1007/BF02122684. ISSN 0209-9683. Zbl 0673.05015. 
  6. Cameron, Peter J. 〈Coherent configurations, association schemes and permutation groups〉 (PDF). Ivanov, A. A.; Liebeck, M. W.; Saxl, J. 《Groups, combinatorics and geometry. Durham 2001》 (영어). World Scientific. 55–71쪽. doi:10.1142/9789812564481_0004. ISBN 978-981-238-312-9. Zbl 1022.05085. 
  7. Bose, Raj Chandra; Shimamoto, T. (1952). “Classification and analysis of partially balanced incomplete block designs with two associate classes”. 《Journal of the American Statistical Association》 (영어) 47: 151–184. doi:10.1080/01621459.1952.10501161. Zbl 0048.11603. 
  8. Bose, Raj Chandra; Mesner, Dale Marsh (1959). “On linear associative algebras corresponding to association schemes of partially balanced designs”. 《Annals of Mathematical Statistics》 (영어) 30 (1): 21–38. doi:10.1214/aoms/1177706356. ISSN 0003-4851. JSTOR 2237117. MR 102157. Zbl 0089.15002. 
  9. Higman, Donald Gordon (1970). “Coherent configurations Ⅰ”. 《Rendiconti del Seminario Matematico della Università di Padova》 (영어) 44: 1–25. MR 325420. Zbl 0279.05025. 

외부 링크편집