주 메뉴 열기

정의편집

해밍 거리를 통한 정의편집

다음 데이터가 주어졌다고 하자.

그렇다면, 곱집합   위에 다음과 같은 이항 관계  들을 주자.

 

여기서

  •  해밍 거리이다.

그렇다면,  결합 도식을 이룬다. 이를  -해밍 결합 도식이라고 한다.[1]:18–19, §1.4.3[2]:2479, Example 1

군 작용을 통한 정의편집

해밍 결합 도식은 대신 군의 작용을 통해 정의될 수도 있다.[2]:2482, Example 1 (continued)

구체적으로, 곱집합  이 주어졌을 때, 다음과 같은 두 단사 군 준동형을 생각할 수 있다.

 
 

여기서

  •   의 원소의  개의 성분들 사이의 순열을 취하는 것이다.
  •   의 원소의  개의 성분들에 각각 순열을 가하는 것이다.

  정규 부분군이며, 분할 완전열

 

이 존재한다. 그렇다면,   으로 생성되는, 대칭군  부분군을 생각할 수 있으며, 이는   반직접곱

 

이다.

그렇다면,   위에  의 성분별 작용

 

을 가했을 때, 그 궤도들은   위의 결합 도식을 정의하며, 이를 해밍 결합 도식이라고 한다.

일반화 해밍 결합 도식편집

다음 데이터가 주어졌다고 하자.

  • 결합 도식  
  • 자연수  

그렇다면, 곱집합  의 임의의 두 원소  에 대하여,

 
 

를 정의하자. 그렇다면,

 

이다. 이제,  

  •  개의 성분을 가지며,
  • 모든 성분이 0 또는 1이며,
  • 모든 성분의 합이  

벡터들의 집합이라고 하자. 그렇다면,   위에 각  에 대하여

 

를 주면, 이는 결합 도식을 이룬다. 이를   위의  일반화 해밍 결합 도식(영어: generalized Hamming association scheme)이라고 한다.[3]

성질편집

해밍 결합 도식은 대칭 결합 도식이다. 즉, 그 모든 이항 관계대칭 관계이다.

대수적 성질편집

해밍 결합 도식  의 인접 행렬들이  라고 하자.

해밍 결합 도식의 구조 상수는 다음과 같다.[4]:334, §2.3

 
 

특히,  일 때 이는  인 항만 남게 되며, 이 경우 구조 상수는 다음과 같다.

 

그렇다면, 해밍 결합 도식의 복소수 계수 보스-메스너 대수의 최소 멱등원들은 다음과 같다.

 
 
 
 

여기서

 

크라우추크 다항식(Кравчук多項式, 영어: Krawtchouk polynomial)이다.[5]

또한, 다음이 성립한다.[2]:2481, §II.B, Example 1 (continued)

 
 

여기서   이 같은 것은 해밍 결합 도식이 스스로의 쌍대이기 때문이다.

편집

(2,2)-해밍 결합 도식은 다음과 같다.

AA AB BA BB
AA 0 1 1 2
AB 1 0 2 1
BA 1 2 0 1
BB 2 1 1 0

역사편집

“해밍 결합 도식”이라는 용어는 리처드 해밍의 이름을 땄으며, 해밍 거리에서 유래하였다.

크라우추크 다항식은 우크라이나의 수학자 미하일로 필리포비치 크라우추크(우크라이나어: Миха́йло Пили́пович Кравчу́к, 러시아어: Михаил Филиппович Кравчук 미하일 필리포비치 크랍추크[*], 1892~1942)가 도입하였다.[6]

참고 문헌편집

  1. Bailey, Rosemary Anne (2004). 《Association schemes: designed experiments, algebra and combinatorics》 (영어). Cambridge University Press. ISBN 978-0-521-82446-0. MR 2047311. doi:10.1017/CBO9780511610882. 
  2. 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. ISSN 0018-9448. doi:10.1109/18.720545. 
  3. Godsil, Chris (2010). “Generalized Hamming schemes” (영어). Bibcode:2010arXiv1011.1044G. arXiv:1011.1044. 
  4. Yoshikawa, Masayoshi. “Modular adjacency algebras of Hamming schemes” (PDF). 《Journal of Algebraic Combinatorics》 (영어) 20 (3): 331–340. ISSN 0925-9899. doi:10.1023/B:JACO.0000048521.68503.2b. 
  5. Coleman, Rodney (2011). “On Krawtchouk polynomials” (영어). Bibcode:2011arXiv1101.1798C. arXiv:1101.1798. 
  6. Krawtchouk, M. (1929년 9월 23일), “Sur une généralisation des polynomes d’Hermite”, 《Comptes rendus hebdomadaires des séances de l’Académie des sciences》 (프랑스어) 189: 620–622, JFM 55.0799.01 

외부 링크편집