조합론에서 해밍 결합 도식(Hamming結合圖式, 영어: Hamming association scheme)은 해밍 거리가 주어진 곱집합으로 구성된 결합 도식이다.
해밍 거리를 통한 정의
편집
다음 데이터가 주어졌다고 하자.
- 유한 집합
- 자연수
그렇다면, 곱집합 위에 다음과 같은 이항 관계 들을 주자.
-
여기서
- 은 해밍 거리이다.
그렇다면, 은 결합 도식을 이룬다. 이를 -해밍 결합 도식이라고 한다.[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]
참고 문헌
편집
- ↑ 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.
- ↑ 가 나 다 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.
- ↑ Godsil, Chris (2010). “Generalized Hamming schemes” (영어). arXiv:1011.1044. Bibcode:2010arXiv1011.1044G.
- ↑ Yoshikawa, Masayoshi. “Modular adjacency algebras of Hamming schemes” (PDF). 《Journal of Algebraic Combinatorics》 (영어) 20 (3): 331–340. doi:10.1023/B:JACO.0000048521.68503.2b. ISSN 0925-9899.
- ↑ Coleman, Rodney (2011). “On Krawtchouk polynomials” (영어). arXiv:1101.1798. Bibcode:2011arXiv1101.1798C.
- ↑ 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
외부 링크
편집