결합 도식

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

결합 도식은 유한 집합 X와 X × X의 부분 집합들로 구성된 조합론적 구조이다. 이 구조는 여러 가지 정의가 있으며, 조합론적, 행렬, 기하학적 정의가 존재한다. 결합 도식은 대칭, 가환, 균등 결합 도식 등 다양한 종류로 분류되며, 해밍 도식, 존슨 도식 등이 예시로 제시된다. 결합 도식은 부분 결합 도식, 결합 도식 사상 등의 연산을 통해 다루어지며, 보스-메스너 대수, 구조 상수, 올, 직접곱 등의 개념과 성질을 갖는다. 결합 도식은 부호 이론, 설계 이론 등 다양한 분야에 활용되며, 특히 해밍 도식과 존슨 도식은 부호 이론에서 중요한 역할을 한다. 이 개념은 1952년 보스와 시마모토에 의해 도입되었으며, 보스-메스너 대수, D. G. 히그만에 의해 발전되었다.

결합 도식

개요

정의	유한 집합에서의 관계들의 모임
다른 이름	어소시에이션 스킴 (Association scheme)

역사

초기 연구	R. C. Bose와 K. R. Nair (1939)
보스-메스너 대수	R. C. Bose와 D. M. Mesner (1959)

관련 개념	코히어런트 구성 거리-정규 그래프 존스 다항식

참고 문헌	http://www.maths.qmul.ac.uk/~rab/Asbook http://www.springer.com/gp/book/9783540261360

외부 링크	https://www.emis.de/journals/SLC/wpapers/s26seidel.html

2. 정의

결합 도식의 개념은 여러 가지 방식으로 정의될 수 있으며, 이 정의들은 모두 서로 동치이다. 주로 사용되는 정의 방식으로는 이항 관계들의 집합을 이용하는 조합론적 정의, 행렬들의 대수를 이용하는 정의, 그리고 거리 공간과 유사한 개념을 이용하는 기하학적 정의 등이 있다. 어떤 정의를 사용하든 본질적으로 동일한 수학적 구조를 다루게 된다. 각 정의 방식에 대한 자세한 내용은 아래 하위 섹션에서 설명한다.

2.1. 조합론적 정의

결합 도식 $(X,\mathcal R)$ 은 다음과 같은 데이터로 주어진다.
* 유한 집합 $X$
* $X\times X$ 의, $n+1$ 개의 부분 집합들로 구성된 족 $\mathcal R = \{R_0, R_1, \dots, R_n\}$ . 여기서 $|\mathcal R|=n+1$ 이며, 각 $R_i$ 는 이항 관계로 볼 수 있다.

이 데이터는 다음 조건들을 만족시켜야 한다.
* ㉠ $\mathcal R$ 는 $X\times X$ 의 분할을 이룬다. 즉, 서로 다른 임의의 $R, R' \in \mathcal R$ 에 대해 $R \cap R' = \varnothing$ 이며, $\textstyle\bigcup_{i=0}^n R_i = X\times X$ 이다. 모든 순서쌍 $(x,y) \in X \times X$ 는 정확히 하나의 $R_i$ 에 속한다.
* ㉡ $R_0 = \{(x,x)\colon x\in X\}$ 이다. 즉, $R_0$ 는 항등 관계이다.
* ㉢ 모든 $R_i$ 는 공집합이 아니다 ( $\varnothing\not\in\mathcal R$ ).
* ㉣ 임의의 $R_i \in \mathcal R$ 에 대하여, 그것의 반대 관계 $R_i^{\operatorname{op}}=\{(y,x)\colon(x,y)\in R_i\}$ 또한 $\mathcal R$ 에 속한다. 즉, $R_i^{\operatorname{op}} = R_j$ 인 $j$ 가 존재한다.
* ㉤ 임의의 $R_i, R_j, R_k \in \mathcal R$ 및 $(x,y)\in R_k$ 에 대하여, $\{z\in X\colon (x,z)\in R_i, (z,y)\in R_j\}$ 의 크기(원소 개수)는 $x, y$ 의 특정 선택에 의존하지 않고 $i, j, k$ 에만 의존하는 상수이다. 이 상수를 $p_{ij}^k$ 로 표기하며, 결합 도식의 구조 상수(structure constant^영어)라고 부른다.

여기서 $R_i \in \mathcal R$ 에 대하여, $(x,y) \in R_i$ 일 때 $x \sim_i y$ 로 표기하기도 한다. 두 점 $x, y$ 가 $(x,y) \in R_i$ 를 만족할 때, $x$ 와 $y$ 는 i번째 연관(i-th associate)이라고 한다.

결합 도식은 행렬을 이용하여 동등하게 정의할 수도 있다. 결합 도식 $(X,n,\mathcal A)$ 은 다음과 같은 데이터로 주어진다.
* 유한 집합 $X=\{0,1,\dotsc,q-1\}$ (여기서 $|X|=q$ )
* 자연수 $n$
* $n+1$ 개의, 모든 성분이 0 또는 1인 $q\times q$ 정사각 행렬들의 족 $\mathcal A=\{A_0,A_1,\dotsc,A_n\}$ . 각 행렬 $A_i$ 는 관계 $R_i$ 의 인접 행렬로 볼 수 있다.

이 데이터는 다음 조건들을 만족시켜야 한다.
* ㉠ $\textstyle\sum_{i=0}^n A_i = J$ 이다. 여기서 $J$ 는 모든 성분이 1인 $q\times q$ 정사각 행렬이다. 이는 $\mathcal R$ 이 $X \times X$ 의 분할이라는 조건에 해당한다.
* ㉡ $A_0 = I$ 이다. 여기서 $I$ 는 $q\times q$ 단위 행렬이다. 이는 $R_0$ 가 항등 관계라는 조건에 해당한다.
* ㉢ 모든 $A_i$ 는 영행렬이 아니다 ( $0_{q\times q}\not\in\mathcal A$ ). 이는 $R_i$ 가 공집합이 아니라는 조건에 해당한다.
* ㉣ 임의의 $A_i \in \mathcal A$ 에 대하여, 그것의 전치 행렬 $A_i^\top$ 또한 $\mathcal A$ 에 속한다. 즉, $A_i^\top = A_j$ 인 $j$ 가 존재한다. 이는 $R_i^{\operatorname{op}} \in \mathcal R$ 조건에 해당한다.
* ㉤ 임의의 $A_i, A_j \in \mathcal A$ 에 대하여, 그 곱 $A_i A_j$ 는 $\mathcal A$ 의 원소들의 선형 결합으로 표현된다. 즉, 각 $0\le i,j,k\le n$ 에 대하여, $\textstyle A_i A_j = \sum_{k=0}^n p^k_{ij} A_k$ 를 만족하는 음이 아닌 정수 $p^k_{ij}$ (구조 상수)가 존재한다. 이는 구조 상수 $p_{ij}^k$ 의 존재 조건에 해당한다.

이 두 정의(관계 기반 정의와 행렬 기반 정의)는 서로 동치이다. 이항 관계 $R_i$ 는 인접 행렬 $A_i$ 와 다음과 같이 일대일 대응된다.
: $(A_i)_{x,y} = \begin{cases} 1 & \text{if } (x,y) \in R_i \\ 0 & \text{if } (x,y) \notin R_i \end{cases} \qquad(x,y\in X)$

결합 도식이 모든 $i, j, k$ 에 대해 $p_{ij}^k = p_{ji}^k$ 를 만족하면 가환적(commutative)이라고 한다. 이는 행렬 정의에서 모든 $i, j$ 에 대해 행렬 곱이 가환적( $A_i A_j = A_j A_i$ )인 것과 동치이다.

결합 도식이 모든 $i$ 에 대해 $R_i = R_i^{\operatorname{op}}$ (즉, $A_i = A_i^\top)를 만족하면$ 대칭적(symmetric)이라고 한다. 이는 모든 관계 $R_i$ 가 대칭 관계임을 의미한다. 모든 대칭 결합 도식은 가환적이다.

2.2. 행렬을 통한 정의

결합 도식 $(X,n,\mathcal A)$ 은 다음과 같은 데이터로 주어진다.
* 유한 집합 $X=\{0,1,\dotsc,q-1\}$
* 자연수 $n$
* $n+1$ 개의, 모든 성분이 0 또는 1인 $q\times q$ 정사각 행렬들의 족 $\mathcal A=\{A_0,A_1,\dotsc,A_n\}$ .

이는 다음 조건들을 만족시켜야 한다.
* ㉠ $\textstyle\sum_{i=0}^nA_i = J$ (여기서 $J$ 는 모든 성분이 1인 $q\times q$ 정사각 행렬이다.)
* ㉡ $\textstyle I = \sum\mathcal A'$ 인 $\mathcal A'\subseteq \mathcal A$ 가 존재한다. (여기서 $I$ 는 $q\times q$ 항등 행렬이다.)
* ㉢ $0_{q\times q}\not\in\mathcal A$ . (여기서 $0_{q\times q}$ 는 영행렬이다.)
* ㉣ 임의의 $A\in\mathcal A$ 에 대하여, 그 전치 행렬 $A^\top$ 역시 $\mathcal A$ 에 속한다.
* ㉤ 임의의 $A_i,A_j\in\mathcal A$ 에 대하여, 그 곱 $A_iA_j$ 는 $\mathcal A$ 의 원소들의 자연수 계수 선형 결합이다. 즉, 각 $0\le i,j,k\le n$ 에 대하여, $\textstyle A_iA_j=\sum_{k=0}^np^k_{ij}A_k$ 인 자연수 $p^k_{ij}$ 가 존재한다. 이 $p^k_{ij}$ 를 결합 도식의 구조 상수(structure constant^영어)라고 한다.

이 정의는 관계를 통한 정의와 서로 동치이다. 두 정의 사이를 번역하려면, 각 이항 관계 $R_i$ 를 그 인접 행렬 $A_i$ 로 치환하면 된다. 즉, $A_i$ 의 $(x,y)$ 성분은 다음과 같이 정의된다.
: $(A_i)_{x,y} = \begin{cases} 1, & \mbox{if } (x,y) \in R_{i} \\ 0, & \mbox{otherwise} \end{cases}$

특히, 대칭 결합 도식 (각 관계 $R_i$ 가 대칭 관계인 경우, 즉 $A_i = A_i^\top$ 인 경우)의 정의는 $A_i$ 가 다음을 만족하는 $q \times q$ (0,1)-행렬임을 말하는 것과 동일하다.
:I. $A_i$ 는 대칭 행렬이다. ( $A_i = A_i^\top$ )
:II. $\sum_{i=0}^n A_i = J$ (모든 원소가 1인 행렬)
:III. $A_0 = I$ (항등 행렬)
:IV. $A_i A_j = \sum_{k=0}^n p^k_{ij}A_k = A_j A_i, \quad i,j=0,\ldots,n$

조건 (IV)의 좌변 $A_i A_j$ 의 $(x,y)$ -번째 항목은 $x$ 에서 $y$ 로 가는, 첫 번째 단계가 관계 $R_i$ 에 속하고 두 번째 단계가 관계 $R_j$ 에 속하는 길이 2의 경로의 수를 나타낸다. 또한, 각 행렬 $A_i$ 의 행(또는 열)의 합은 일정하며, 이를 $v_i$ (관계 $R_i$ 의 원자가)라고 하면 다음이 성립한다.
: $A_{i} J=J A_{i}=v_{i} J$

2.3. 기하학적 정의

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

결합 도식 $(X,D,\partial)$ 은 다음과 같은 데이터로 주어진다.
* 유한 집합 $X$
* 유한 집합 $D$
* 함수 $\partial\colon X\times X\to D$ . 이는 거리 함수(distance^영어)라고 한다.

이는 다음 조건들을 만족시켜야 한다.
* ㉡ 임의의 $x,y,z\in X$ 에 대하여, 만약 $\partial(x,x)=\partial(y,z)$ 라면, $y=z$ 이다. (모든 점의 자기 자신과의 거리는 동일하며, 이 거리는 서로 다른 두 점 사이의 거리와는 다르다.)
* ㉢ $\partial$ 은 전사 함수이다. (D에 있는 모든 가능한 거리가 실제로 X의 점 쌍 사이에서 나타난다.)
* ㉣ 임의의 $x,y,x',y'\in X$ 에 대하여, $\partial(x,y)=\partial(x',y')$ 라면 $\partial(y,x)=\partial(y',x')$ (두 점 사이의 거리가 같다면, 순서를 바꾼 점 사이의 거리도 같다. 즉, 거리 관계는 대칭적이다.)
* ㉤ 임의의 $x,y,x',y'\in X$ 에 대하여, 만약 $\partial(x,y)=\partial(x',y')$ 라면, $\forall z\in X\colon \partial(x,z)=\partial(x',f(z))$ 이자 $\forall z\in X\colon\partial(z,y)=\partial(f(z),y')$ 가 되는 전단사 함수 $f\colon X\to X$ 가 존재한다. (거리 구조가 일정하게 유지되는 변환이 존재한다.)

이 정의는 다른 정의 방식들과 서로 동치이다. 즉, 각 $\alpha\in D$ 에 대하여 이항 관계
: $x\sim_\alpha y\iff \partial(x,y)=\alpha$
를 대응시키면, 앞서 설명한 관계 $R_i$ 들을 이용한 정의와 같아진다.

특히 대칭 연관 도식은 각 관계 $R_i$ 가 대칭 관계인 경우를 말하며, 이는 기하학적으로 시각화하기 용이하다. 대칭 연관 도식은 레이블이 지정된 간선이 있는 완전 그래프로 생각할 수 있다.
* 그래프의 정점은 집합 $X$ 의 각 원소에 해당한다.
* 두 정점 $x$ 와 $y$ 가 $i$ 번째 관계( $(x,y) \in R_i$ )에 있다면, 두 정점을 연결하는 간선에 레이블 $i$ 를 붙인다. 대칭적이므로 $(y,x) \in R_i$ 도 성립한다.
* 모든 점 쌍은 정확히 하나의 $i$ 에 대해 $i$ 번째 관계에 있다.
* 각 점 $x$ 는 자기 자신과 0번째 관계( $(x,x) \in R_0$ )에 있으며, 이는 그래프에서 각 정점에 레이블 0인 루프(loop)가 있는 것으로 표현된다.
* 만약 두 점 $x$ 와 $y$ 가 $k$ 번째 관계에 있을 때 ( $k$ 레이블 간선으로 연결됨), $x$ 와는 $i$ 번째 관계에 있고( $i$ 레이블 간선), $y$ 와는 $j$ 번째 관계에 있는( $j$ 레이블 간선) 점 $z$ 의 개수는 상수 $p^k_{ij}$ 이다. 이는 그래프에서 밑변 간선의 레이블이 $k$ 이고 다른 두 변의 레이블이 각각 $i$ , $j$ 인 삼각형의 수가 $p^k_{ij}$ 로 일정하다는 의미이다. 이 값은 $i, j, k$ 에 따라 달라지지만, 구체적인 밑변 간선( $x, y$ 쌍)의 선택에는 의존하지 않는다.

2.4. 부분 결합 도식

같은 집합 $X$ 위의 두 결합 도식 $(X,\mathcal R)$ 및 $(X,\mathcal R')$ 에 대하여, 만약 $\mathcal R\subseteq\mathcal R'$ 이라면, $(X,\mathcal R)$ 를 $(X,\mathcal R')$ 의 부분 결합 도식(subscheme^영어)이라고 한다.

2.5. 결합 도식 준동형

다음 두 개의 결합 도식이 주어졌다고 가정하자.
* 유한 집합 $X$ 위의 결합 도식 $(X,\mathcal R)$
* 유한 집합 $X'$ 위의 결합 도식 $(X',\mathcal R')$

이때, 결합 도식 사상(morphism of association schemes^영어) $(f,g)\colon (X,\mathcal R)\to(X',\mathcal R')$ 은 다음 두 가지 요소로 구성된다.
* 함수 $f\colon X\to X'$
* 함수 $g\colon \mathcal R\to\mathcal R'$

이 두 함수는 다음 조건을 만족해야 한다.
: 임의의 $x,y\in X$ 와 $R\in\mathcal R$ 에 대해, 만약 $x$ 와 $y$ 가 관계 $R$ ( $x\sim_Ry$ )을 만족하면, $f(x)$ 와 $f(y)$ 는 관계 $g(R)$ ( $f(x)\sim_{g(R)}f(y)$ )을 만족해야 한다.

결합 도식 사상은 이항 관계가 주어진 구조 사이의 준동형의 특별한 경우로 볼 수 있다.

3. 종류

결합 도식 $X$ 에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 결합 도식을 대칭 결합 도식(對稱結合圖式, symmetric association scheme^영어)이라고 한다.
* 조합론적 정의 $(X,\mathcal R)$ 에서, $\mathcal R$ 의 모든 원소는 대칭 관계이다. 즉, 만약 $R\in\mathcal R$ 라면, $R=R^{\operatorname{op}}$ 이다.
* 행렬을 통한 정의 $(X,\mathcal A)$ 에서, 모든 $A\in\mathcal A$ 는 대칭 행렬이다.
* 기하학적 정의 $(X,\partial)$ 에서, 임의의 $x,y\in X$ 에 대하여 $\partial(x,y)=\partial(y,x)$ 이다.

결합 도식 $(X,\mathcal R)$ 에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 결합 도식을 가환 결합 도식(可換結合圖式,commutative association scheme^영어)이라고 한다.
* 그 보스-메스너 대수가 가환환이다.
* 조합론적 정의에서, 임의의 $R,R',R$ \in\mathcal R 및 $(x,y)\in R$ 에 대하여, $|\{z\in X\colon x\sim_{R'}z\sim_{R$ }y\}|=|\{z\in X\colon x\sim_{R''}z\sim_{R'}y\}|
* 행렬을 통한 정의 $(X,\mathcal A)$ 에서, 임의의 $A,B\in\mathcal A$ 에 대하여 $AB=BA$ 이다.
* 기하학적 정의 $(X,\partial)$ 에서, 임의의 $x,y\in X$ 에 대하여, $\forall z\in X\colon(\partial(x,z),\partial(z,y))=(\partial(y,f(z)),\partial(f(z),x))$ 가 되는 자기 전단사 함수 $f\colon X\to X$ 가 존재한다.

결합 도식 $(X,\mathcal R)$ 이 다음 조건을 만족시킨다면, 균등 결합 도식(均等結合圖式, homogeneous association scheme^영어)이라고 한다.
* 조합론적 정의 $(X,\mathcal R)$ 에서, $\{(x,x)\colon x\in X\}\in\mathcal R$ 이다.
* 행렬을 통한 정의 $(X,\mathcal A)$ 에서, $1_$

👆

좌우로 밀어서 보기

\in\mathcal A이다.
* 기하학적 정의

(X,\partial)

에서,

\forall x,y\in X\colon \partial(x,x)=\partial(y,y)

이다.

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

4. 성질

결합 도식 $X$ 에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 결합 도식을 대칭 결합 도식(對稱結合圖式, symmetric association scheme^영어)이라고 한다.
* 조합론적 정의 $(X,\mathcal R)$ 에서, $\mathcal R$ 의 모든 원소는 대칭 관계이다. 즉, 만약 $R\in\mathcal R$ 라면, $R=R^{\operatorname{op}}$ 이다.
* 행렬을 통한 정의 $(X,\mathcal A)$ 에서, 모든 $A\in\mathcal A$ 는 대칭 행렬이다.
* 기하학적 정의 $(X,\partial)$ 에서, 임의의 $x,y\in X$ 에 대하여 $\partial(x,y)=\partial(y,x)$ 이다.

결합 도식 $(X,\mathcal R)$ 에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 결합 도식을 가환 결합 도식(可換結合圖式, commutative association scheme^영어)이라고 한다.
* 그 보스-메스너 대수가 가환환이다.
* 조합론적 정의에서, 임의의 $R,R',R$ \in\mathcal R 및 $(x,y)\in R$ 에 대하여, $|\{z\in X\colon x\sim_{R'}z\sim_{R$ }y\}|=|\{z\in X\colon x\sim_{R''}z\sim_{R'}y\}|
* 행렬을 통한 정의 $(X,\mathcal A)$ 에서, 임의의 $A,B\in\mathcal A$ 에 대하여 $AB=BA$ 이다.
* 기하학적 정의 $(X,\partial)$ 에서, 임의의 $x,y\in X$ 에 대하여, $\forall z\in X\colon (\partial(x,z),\partial(z,y))=(\partial(y,f(z)),\partial(f(z),x))$ 가 되는 자기 전단사 함수 $f\colon X\to X$ 가 존재한다.

결합 도식 $(X,\mathcal R)$ 이 다음 조건을 만족시킨다면, 균등 결합 도식(均等結合圖式, homogeneous association scheme^영어)이라고 한다.
* 조합론적 정의 $(X,\mathcal R)$ 에서, $\{(x,x)\colon x\in X\}\in\mathcal R$ 이다.
* 행렬을 통한 정의 $(X,\mathcal A)$ 에서, $I_$

👆

좌우로 밀어서 보기

\in\mathcal A이다. (여기서

I

는 단위 행렬이다.)
* 기하학적 정의

(X,\partial)

에서,

\forall x,y\in X\colon \partial(x,x)=\partial(y,y)

이다.

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

4.1. 구조 상수

임의의 결합 도식 $X$ 의 구조 상수들 $(p_{ij}^k)_{1\le i,j,k\le n}$ 은 다음을 만족시킨다.
: $\sum_{i,j,k=0}^np_{ij}^k|R_k|=|X|^3$
만약
: $R_i^{\operatorname{op}}=R_{\bar\imath}$
: $R_j^{\operatorname{op}}=R_{\bar\jmath}$
: $R_k^{\operatorname{op}}=R_{\bar k}$
일 때, 다음이 성립한다.
: $p_{jk}^i=p_{\bar k\bar\jmath}^{\bar\imath}$

균등 결합 도식 $(X,\mathcal R)$ 의 구조 상수들 $(p_{ij}^k)_{1\le i,j,k\le n}$ 은 다음을 만족시킨다.
: $p_{0i}^j=p_{i0}^j=\delta_i^j$
: $p_{ij}^0=p_{\bar\jmath\bar\imath}^0=\delta_j^{\bar\imath}p_{i\bar\imath}^0$
: $\sum_{i,j=0}^np_{ij}^0=\sum_{i=0}^np_{i\bar\imath}^0=|X|$
(여기서 $\delta_i^j$ 는 크로네커 델타이다.)
* 숫자 $p_{ij}^k$ 는 도식의 매개변수(parameter)라고 불린다. 또한 구조 상수(structure constant)라고도 한다.

4.2. 대칭 결합 도식과 변 색칠

대칭 결합 도식 $(X,\mathcal R)$ 이 주어졌다고 하자. 이 도식의 정보를 이용해, $X$ 의 원소를 꼭짓점으로 하는 완전 그래프 $K_X$ 위에 특별한 변 색칠을 정의할 수 있다. 각 변 $(x,y)$ 에 대해, 만약 $(x,y)$ 가 관계 $R \in \mathcal R$ ( $R \ne R_0$ )에 속한다면, 그 변의 색을 $R$ 로 칠하는 것이다. 즉, 변 색칠 함수 $c\colon \operatorname E(K_X)\to \mathcal R\setminus\{R_0\}$ 는 다음과 같이 정의된다.
: $c\colon (x,y)\mapsto R\iff (x,y)\in R\qquad(R\in\mathcal R,\;R\ne R_0)$
이러한 관점에서, 대칭 결합 도식은 특정 규칙을 만족하는 변 색칠이 주어진 유한 완전 그래프로 이해할 수 있다.

대칭 결합 도식은 각 간선에 레이블이 붙은 완전 그래프로 시각화될 수 있다. 이 그래프는 $v$ 개의 정점을 가지며, 각 정점은 집합 $X$ 의 한 점에 해당한다. 두 정점 $x$ 와 $y$ 를 연결하는 간선은, 만약 $x$ 와 $y$ 가 $i$ 번째 관계 $R_i$ 에 속한다면 레이블 $i$ 를 갖는다. 대칭 결합 도식의 중요한 성질 중 하나는 삼각형과 관련된 것이다. 임의의 두 정점 $x, y$ 에 대해, 이들을 잇는 간선의 레이블이 $k$ 일 때, $x$ 와 어떤 정점 $z$ 를 잇는 간선의 레이블이 $i$ 이고, $y$ 와 $z$ 를 잇는 간선의 레이블이 $j$ 인 정점 $z$ 의 개수는 $p^k_{ij}$ 라는 상수로 일정하다. 이 값은 $i, j, k$ 에 따라 달라지지만, 밑변 $(x,y)$ 의 선택과는 무관하다. 특히, 각 정점에 연결된 레이블 $i$ 의 간선 수는 정확히 $p^0_{ii}=v_{i}$ 개인데, 이 $v_i$ 를 관계 $R_i$ 의 원자가라고 부른다. 또한, 각 정점 $x$ 에는 자기 자신으로 돌아오는 루프(loop)가 있으며, 이는 관계 $R_0$ 에 해당하고 레이블 $0$ 을 갖는다.

결합 도식의 관계들은 인접 행렬을 사용하여 표현할 수 있다. 각 관계 $R_i$ ( $i=0,\ldots,n$ )에 대해, $v \times v$ 크기의 행렬 $A_i$ 를 정의하는데, 이 행렬의 행과 열은 $X$ 의 점들로 인덱싱된다. $A_i$ 의 $(x,y)$ 성분은 다음과 같이 정의된다.
: $\left( A_i \right)_{x,y} = \begin{cases} 1, & \mbox{if } (x,y) \in R_{i},\\ 0, & \mbox{otherwise.} \end{cases}$

이 인접 행렬들을 사용하면, 대칭 결합 도식의 정의는 다음과 같은 조건을 만족하는 $v \times v$ (0,1)-행렬들의 집합 $\{A_0, A_1, \ldots, A_n\}$ 을 찾는 것과 동일하다.
:I. 모든 $A_i$ 는 대칭 행렬이다. 즉, $A_i = A_i^T$ 이다.
:II. 모든 인접 행렬의 합은 모든 성분이 1인 행렬 $J$ 이다. 즉, $\sum_{i=0}^n A_i = J$ 이다. 이는 모든 두 점의 쌍이 정확히 하나의 관계에 속한다는 것을 의미한다.
:III. $A_0$ 는 단위 행렬 $I$ 이다. 즉, $A_0 = I$ 이다. 이는 관계 $R_0$ 가 $(x,x)$ 형태의 쌍들로만 이루어져 있음을 의미한다.
:IV. 임의의 $i, j$ 에 대해, 행렬 곱 $A_i A_j$ 는 $A_k$ 들의 선형 결합으로 표현된다. 즉, $A_i A_j = \sum_{k=0}^n p^k_{ij}A_k$ 이다. 또한, 이 행렬들은 서로 교환 가능하다. 즉, $A_i A_j = A_j A_i$ 이다.

조건 (IV)에서 행렬 곱 $A_i A_j$ 의 $(x,y)$ -번째 성분은, 정점 $x$ 에서 시작하여 레이블 $i$ 인 간선을 따라 어떤 중간 정점 $z$ 로 가고, 다시 레이블 $j$ 인 간선을 따라 정점 $y$ 로 도착하는 길이 2인 경로의 수를 나타낸다. 또한, 각 행렬 $A_i$ 의 모든 행과 열의 합은 해당 관계의 원자가 $v_i$ 와 같다. 이는 다음 수식으로 표현된다.
: $A_{i} J=J A_{i}=v_{i} J.$

4.3. 보스-메스너 대수

결합 도식 $(X,\mathcal A)$ 이 주어졌을 때, $\mathcal A$ 의 선형 생성
: $\operatorname{Span}_{\mathbb Z}\mathcal A\subseteq\operatorname{Mat}(|X|,|X|;\mathbb Z)$
은 정수 계수 결합 대수를 이룬다. 이를 $X$ 에 대응하는 보스-메스너 대수(Bose–Mesner algebra)라고 한다. 흔히 정수 계수 대신 실수나 복소수 계수를 사용하기도 한다.

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

아르틴-웨더번 정리에 따라서, 복소수 계수 보스-메스너 대수는 다음과 같은 행렬 대수들의 곱으로 유일하게 표현될 수 있다.
: $\prod_{a=1}^k\operatorname{Mat}(m_a,m_a;\mathbb C)$
이 분해에 따라, 각 성분 대수에 대응하는 원시 멱등원(primitive idempotent) $E_a$ 들을 정의할 수 있다. 이들은 다음과 같은 성질을 만족한다.
: $E_a=(0,0,\dotsc,0,1_{m_a\times m_a},0,\dotsc,0)$
: $E_aE_b=\delta_{ab}E_a\qquad(a,b\in\{0,\dotsc,k\})$
여기서 $\delta_{ab}$ 는 크로네커 델타이다. 또한, 편의상 $E_0$ 를 다음과 같이 정의한다.
: $E_0=\frac1$

👆

좌우로 밀어서 보기

\mathsf J_

👆

좌우로 밀어서 보기

\mathsf J_

👆

좌우로 밀어서 보기

는 모든 성분이 1인

|X|\times|X|

정사각 행렬이며, 아다마르 곱의 항등원이다.

E_0

는 결합 도식의 공리에 따라 보스-메스너 대수의 원소이며, 0이 아닌 고윳값이 1개뿐인 멱등원이므로 위 분해에 항상 포함된다.

특히, 멱등원

E_a

를 결합 도식의 인접 행렬

D_i

들의 선형 결합으로 나타냈을 때의 계수를 이용하여 다음과 같이 표현할 수 있다.
:

|X|E_a=\sum_{i=0}^nQ_{ai}D_i

이 계수 행렬

Q = (Q_{ai})

를 제2 고유 행렬(second eigenmatrix) 또는 문자표(character table)라고 부르기도 한다.

결합 도식의 관계는 인접 행렬로 나타낼 수 있다.

i=0,\ldots,n

에 대해 관계

R_{i}

의 인접 행렬

A_i

는

X

의 원소들로 행과 열이 색인된 v × v 행렬이며, 다음과 같이 정의된다.
:

\left( A_i \right)_{x,y} = \begin{cases}1, & \mbox{if } (x,y) \in R_{i},\\0, & \mbox{otherwise.}  \end{cases}

특히 대칭 결합 도식의 경우, 인접 행렬

A_i

는 다음 조건을 만족하는 v × v (0,1)-행렬이다.
:I.

A_i

는 대칭 행렬이다 (

A_i = A_i^T

).
:II.

\sum_{i=0}^n A_i = J

(모든 성분이 1인 행렬).
:III.

A_0 = I

(단위 행렬).
:IV.

A_i A_j = \sum_{k=0}^n p^k_{ij}A_k = A_j A_i

for

i,j=0,\ldots,n

. 여기서

p^k_{ij}

는 결합 도식의 교차수(intersection number)이다. 이 조건은 행렬들이 서로 교환 가능함을 의미한다.

이 인접 행렬들

A_0, A_1, \ldots, A_n

은 행렬 곱과 점별 곱(아다마르 곱) 모두에 대해 가환적이고 결합적인 대수

\mathcal{A}

(보통 실수 또는 복소수 위에서 정의됨)를 생성한다. 이 대수

\mathcal{A}

가 바로 결합 도식의 보스-메스너 대수이다.

보스-메스너 대수

\mathcal{A}

의 행렬들은 대칭 행렬이고 서로 교환 가능하므로, 선형대수학의 정리에 따라 동시에 대각화될 수 있다. 이는

\mathcal{A}

가 반단순 대수임을 의미하며, 서로 직교하는 원시 멱등 행렬

E_{0},\ldots,E_{n}

(위에서 언급한

E_a

와 표기법이 다를 수 있음)들의 유일한 기저를 가진다는 것을 뜻한다.

보스-메스너 대수

\mathcal{A}

와 동형인

(n+1)\times(n+1)

행렬로 구성된 또 다른 대수가 존재하는데, 이를 이용하면 보스-메스너 대수의 구조를 더 쉽게 분석할 수 있는 경우가 많다.

4.4. 가환 결합 도식의 쌍대성

가환 결합 도식 $X$ 의 경우, 최소 멱등원의 수는 $|X|=n$ 와 같으며, 멱등원들 $(E_a)_{0\le a\le n}$ 은 보스-메스너 대수 $\mathcal A$ 의 기저를 이룬다. 이에 따라, 다음을 정의할 수 있다.
: $D_i=\sum_{a=0}^nP_{i,a}E_a$
또한, $D_i$ 들은 모두 아다마르 곱 $\bigcirc$ 에 대하여 닫혀 있으므로, $E_a$ 들의 아다마르 곱에 대한 구조 상수 $q_{ab}^c$ 를 다음과 같이 정의할 수 있다. (아다마르 곱은 교환 법칙을 따르므로 $q_{ab}^c=q_{ba}^c$ 이다.)
: $E_a\bigcirc E_b=q_{ab}^cE_c$

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

👆

좌우로 밀어서 보기

이항 연산	아다마르 곱 $\bigcirc$	행렬 곱
기저	$D_i$	$E_a$
기저의 직교성	$D_i\bigcirc D_j=\delta_{ij}D_i$	$E_aE_b=\delta_{ab}E_a$
멱등원 조건	$D_i$ 의 모든 성분은 0 또는 1 (아다마르 곱의 멱등원)	$E_a$ 의 모든 고윳값은 0 또는 1 (행렬 곱의 멱등원)
항등원	$D_0=1_{n\times n}$	E_0 = \mathsf J_{n\times n} />X\|
기저 원소의 쌍대성	$D_{\bar\imath} = D_i^\top$	$E_{\bar a} = E_a^\top = \bar E_a$ (각 성분의 복소켤레)
기저의 합	\textstyle\sum_iD_i=\mathsf J_{>X\|\times\|X\|}	\textstyle\sum_aE_a=1_{>X\|\times\|X\|}
차수	v_i=>\{y\in X\colon x\sim_iy\}\|\;(\forall x\in X)	$m_a=\dim_{\mathbb C}\operatorname{im}E_a$
차수의 합	\textstyle\sum_iv_i=>X\|	\textstyle\sum_am_a=>X\|
구조 상수	$D_iD_j=p_{ij}^kD_k$	>X\|E_a\bigcirc E_b=q_{ab}^cE_c (가환 결합 도식)
기저 변환	$\textstyle D_i=\sum_{a=0}^nP_{ia}E_a$ (가환 결합 도식)	$\textstyle E_a=\sum_{i=0}^nQ_{ai}D_i$

주석: 위 표에서 "가환 결합 도식"이라고 표시된 항목은 해당 조건에서만 정의된다.

이에 따라, 만약 두 결합 도식

X

Y

의 복소수 계수 보스-메스너 대수

\mathcal A_X

\mathcal A_Y

가 각각 다음 조건을 만족하는 반선형 변환antilinear map^영어

f

를 통해 연결될 수 있다면, 서로 쌍대dual^영어라고 한다.
:

f\colon \mathcal A_X\to\mathcal A_Y

f(\lambda M)=\bar\lambda f(M)\qquad(\lambda\in\mathbb C,\;M\in\mathcal A_X)

f(MN)=f(M)\bigcirc f(N)

f(M\bigcirc N)=f(M)f(N)

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

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

5. 연산

결합 도식 위에서는 여러 가지 연산을 정의할 수 있다. 대표적인 예로는 올( fibre^영어 )과 직접곱( direct product^영어 ) 등이 있다. 각 연산에 대한 자세한 내용은 하위 섹션을 참조하라.

5.1. 올

결합 도식 $(X,\partial)$ 이 주어졌을 때, $X$ 위에 다음과 같은 동치 관계를 정의할 수 있다.
: $x\approx y\iff \partial(x,x)=\partial(y,y)$
이 동치 관계에 대한 동치류를 $X$ 의 올(fibre^영어)이라고 한다. 올들로 구성된 집합의 분할을 $(X_\alpha)_{\alpha\in I}$ 로 표기할 때, 다음이 성립한다.
: $\forall R\in\mathcal R\exists \alpha,\beta\in I\colon R\subseteq X_\alpha\times X_\beta$

증명:
임의의 $x,y,y'\in X$ 가 주어졌으며, 귀류법을 사용하여
: $\partial(x,y)=\partial(x,y')$
: $\partial(y,y)\ne\partial(y',y')$
이라고 가정하자. 그렇다면,
: $\{z\in X\colon \partial(x,z)=\partial(x,y),\;\partial(z,y)=\partial(y,y)\} = \{y\}$
: $\{z\in X\colon \partial(x,z)=\partial(x,y),\;\partial(z,y')=\partial(y,y)\} = \varnothing$
이므로, 이는 결합 도식의 정의와 모순된다.

이에 따라, 결합 도식 $(X,\partial)$ 의 임의의 올 $X_i$ 이 주어졌을 때,
: $(X_i,\partial\restriction X_i^2)$
는 균등 결합 도식을 이룬다.

5.2. 직접곱

유한 개의 결합 도식
: $(X_i,\mathcal R_i)_{i\in I}$
: $|I|<\aleph_0$
이 주어졌다고 하자. 그렇다면, 곱집합
: $X=\prod_{i\in I}X_i$
위에 이항 관계
: $\mathcal R=\prod_{i\in I}\mathcal R_i$
: $(x_i)_{i\in I}\sim_{(R_i)_{i\in I}}(y_i)_{i\in I}\iff\forall i\in I\colon x_i\sim_{R_i}y_i$
를 줄 수 있다. 그렇다면, $(X,\mathcal R)$ 는 결합 도식을 이루며, 이를 $(X_i,\mathcal R_i)_{i\in I}$ 의 직접곱(直接곱, direct product^영어)이라고 한다.

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

6. 예

다음은 $n=3$ 인 대칭 결합 도식의 한 예이다. 여기서 $X=\{\mathsf A,\mathsf B,\mathsf C,\mathsf D,\mathsf E,\mathsf F\}$ 이다.

👆

좌우로 밀어서 보기

	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

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

1 = p_{00}^0 = p_{01}^1 = p_{02}^2 = p_{03}^3 = p_{11}^1 = p_{23}^1 = p_{33}^1 =  p_{22}^2 = p_{12}^3 = p_{13}^3

2 = p_{11}^0 = p_{33}^0 = p_{13}^2

여기서

p_{ij}^k

가 수록되었다면

p_{ji}^k

는 생략하였으며, 수록되지 않은 구조 상수는 모두 0이다.

거리 정규 그래프 G는 두 개의 정점을 그들의 거리가 i일 때 i 번째 연관 집합으로 정의하여 연관 도식을 형성한다.

다음은 집합 X = {1,2,3,4,5,6}에 대한 세 개의 연관 클래스를 가진 연관 도식 A(3)이다. ('i, j ) 항목은 요소 i와 j가 관계 Rs에 있는 경우 s''이다.

👆

좌우로 밀어서 보기

	1	2	3	4	5	6
1	0	1	1	2	3	3
2	1	0	1	3	2	3
3	1	1	0	3	3	2
4	2	3	3	0	1	1
5	3	2	3	1	0	1
6	3	3	2	1	1	0

6.1. 자명한 결합 도식

크기가 2 이상인 임의의 유한 집합 $X$ 위에 다음과 같이 관계를 정의한다.
: $R_0=\{(x,x)\colon x\in X\}$ (각 원소를 자기 자신과 연결하는 항등 관계)
: $R_1=X\times X\setminus R_0$ (서로 다른 두 원소를 연결하는 관계)
: $\mathcal R=\{R_0,R_1\}$ (위 두 관계의 집합)

이렇게 정의된 $(X,2,\mathcal R)$ 는 결합 도식을 이루며, 이를 자명한 결합 도식(trivial association scheme^영어)이라고 한다.

자명한 결합 도식의 구조 상수는 다음과 같다.
: $p_{00}^0=p_{01}^1=p_{10}^1=1$
: $p_{00}^1=p_{01}^0=p_{10}^0=0$
: $p_{11}^0=|X|-1$
: $p_{11}^1=|X|-2$

이는 $n=1$ 인 경우의 해밍 결합 도식과 동일하다.

6.2. 이산 결합 도식

임의의 유한 집합 $X$ 위에,
: $\mathcal R=\{\{(x,y)\}\colon x,y\in X\}$
를 정의하면, $(X,\mathcal R)$ 역시 결합 도식을 이룬다. 이를 이산 결합 도식(discrete association scheme^영어)이라고 한다.

그러나 집합 $X$ 의 원소 개수가 2개 이상일 경우( $|X|\ge2$ ), 이산 결합 도식은 균등 결합 도식이 아니다.

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

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

구체적인 예시로 해밍 도식(Hamming scheme), H(n, q)는 다음과 같이 정의된다. H(n, q)의 점(vertex)은 크기가 q인 집합에서 원소를 가져와 순서대로 나열한 n-튜플 $q^n$ 개이다. 두 개의 n-튜플 x, y는 정확히 i개의 좌표에서 값이 다를 경우 i 번째 연관 집합(i-th associate)이라고 한다. 예를 들어, x = (1,0,1,1), y = (1,1,1,1), z = (0,0,1,1)인 경우, H(4,2)에서 x와 y는 1번째 연관 집합이고(y는 x와 두 번째 좌표만 다르므로), x와 z는 1번째 연관 집합이며(z는 x와 첫 번째 좌표만 다르므로), y와 z는 2번째 연관 집합이다(z는 y와 첫 번째, 두 번째 좌표가 다르므로).

특히, $F=\{0,1\}$ 인 이진 벡터 공간에서, 주어진 해밍 무게(벡터에서 1의 개수)를 갖는 벡터들만을 대상으로 한 해밍 결합 도식의 부분 결합 도식을 존슨 결합 도식이라고 한다.

존슨 도식(Johnson scheme), J(v, k)는 다음과 같이 정의된다. S를 v개의 원소를 가진 집합이라고 하자. 도식 J(v, k)의 점은 S의 k개 원소를 가진 부분 집합 $\binom{v}{k}$ 개이다. S의 두 개의 k원소 부분 집합 A, B는 그들의 교집합의 크기가 k − i일 때 i 번째 연관 집합이다.

해밍 도식과 존슨 도식은 고전적인 부호 이론에서 매우 중요한 개념이다. 부호 이론에서 결합 도식 이론은 주로 부호의 해밍 거리를 분석하는 데 사용된다.

6.4. 정추이적 작용

유한군 $G$ 의, 유한 집합 $X$ 위의 왼쪽 정추이적 작용이 주어졌다고 가정하자. 이 경우 $|G|=|X|$ 가 성립한다. 이때,
: $n=|G|$
: $\mathcal R=\{\{(x,gx)\colon x\in X\}\colon g\in G\}$
로 정의하면, $(X,n,\mathcal R)$ 는 결합 도식을 이룬다. 이 결합 도식의 구조 상수는 다음과 같다.
: $p_{gh}^k=\begin{cases}1&gh=k\\0&gh\ne k\end{cases}\qquad(g,h,k\in G)$
이 구조에 대응하는 보스-메스너 대수는 군환 $\mathbb Z[G]$ 와 동형이다. 또한, 이 결합 도식이 가환 결합 도식일 필요 충분 조건은 군 $G$ 가 아벨 군인 것이다.

특히, 유한군 G는 자기 자신을 집합 $X=G$ 로 삼아 그 위에 작용함으로써 연관 도식을 생성할 수 있다. 각 군 원소 $g \in G$ 에 대해 관계 $R_g$ 를 다음과 같이 정의한다.
: $R_g = \{(x,y) \mid x=g*y\}$
여기서 $*$ 는 군의 연산이다. 군 항등원에 대응하는 관계는 R₀이다. 이렇게 정의된 연관 도식은 군 G가 아벨 군일 때에만 그리고 오직 그 때만 교환 가능하다.

6.5. 일반적 군 작용

유한군 $G$ 의, 유한 집합 $X$ 위의 왼쪽 작용이 주어졌다고 하자. 그렇다면, $G$ 는 $X^2=X\times X$ 위에 다음과 같이 작용한다.
: $g\cdot(x,y)=(g\cdot x,g\cdot y)\qquad(x,y\in X,\;g\in G)$
그렇다면, $G$ 의 작용에 대한 궤도들은 $X^2$ 의 분할 $X^2/G$ 을 정의한다.

이 경우, $(X,X^2/G)$ 는 결합 도식을 이룬다. 또한, 이 결합 도식이 각종 조건을 만족시킬 필요 충분 조건은 다음과 같다.

👆

좌우로 밀어서 보기

결합 도식	군의 작용
올	$X$ 위의 $G$ -작용의 궤도
균등 결합 도식	$G\to\operatorname{Sym}(X)$ 가 추이적 작용
대칭 결합 도식	임의의 $x,y\in X$ 에 대하여, $(g\cdot x,g\cdot y)=(y,x)$ 가 되는 $g\in G$ 가 존재
자명 결합 도식	$G\to\operatorname{Sym}(X)$ 가 2-추이적 작용
이산 결합 도식	$G\to\operatorname{Sym}(X)$ 가 자명한 작용 (즉, $g\cdot x=x\forall g\in G,\;x\in X$ )

7. 역사

'결합 도식'이라는 용어는 1952년에 처음 사용되었지만, 그 개념은 이미 1939년 라지 찬드라 보스와 K. R. 네어(K. R. Nair^영어)의 연구에서 나타났다. 이들은 통계학자들이 '부분 균형 불완전 블록 설계'(PBIBDs)라고 부르는 것을 연구하는 과정에서 관련 개념을 다루었다.

1952년, 라지 찬드라 보스와 T. 시마모토(T. Shimamoto^영어)는 블록 설계 이론에 대한 응용을 위해 '결합 도식'(association scheme^영어)이라는 용어를 공식적으로 도입했다. 당시 이 용어는 오늘날의 대칭 결합 대수를 의미했다.

1959년에는 라지 찬드라 보스와 데일 마시 메스너(Dale Marsh Mesner^영어)가 보스-메스너 대수를 도입하면서 결합 도식 이론은 대수학 분야에서도 중요한 연구 주제로 부상했다.

이후 1970년, 도널드 고든 히그먼(Donald Gordon Higman^영어, 1928~2006)은 군론에서의 응용을 목적으로 결합 도식과 동치인 개념을 '일관 구조'(coherent configuration^영어)라는 이름으로 소개했다.

결합 도식 이론 발전에 중요한 기여를 한 인물 중 한 명은 P. 델사르트(P. Delsarte^영어)이다. 그는 1973년 발표한 논문을 통해 결합 도식이 코딩 이론 및 설계 이론과 밀접한 관련이 있음을 밝혀내고 이를 이론적으로 활용하는 기반을 마련했다. 이후 D. G. 히그먼의 일관 구조 연구와 B. 바이스페일러의 거리 정규 그래프 연구 등을 통해 결합 도식 이론은 더욱 일반화되었다.

8. 활용

해밍 도식과 존슨 도식은 고전적인 부호 이론에서 매우 중요한 개념이다.

부호 이론에서 결합 도식 이론은 주로 부호의 해밍 거리와 관련된 문제를 다루는 데 활용된다. 선형 계획법은 결합 도식 이론을 이용하여 주어진 최소 해밍 거리를 갖는 부호의 크기에 대한 상한선을 구하거나, 주어진 강도를 갖는 T-설계의 크기에 대한 하한선을 구하는 데 사용된다. 특히, 결합 도식이 특정 다항식 속성을 만족할 때 가장 구체적인 결과를 얻을 수 있으며, 이는 직교 다항식 분야와 깊은 관련이 있다. 이러한 다항식 유형의 결합 도식을 통해 부호와 T-설계에 대한 몇 가지 보편적인 경계값을 유도할 수 있다.

고전적인 부호 이론에서는 해밍 도식의 부호를 분석하기 위해 맥윌리엄스 변환(MacWilliams transform)을 사용하는데, 이 변환은 크라프추크 다항식이라고 알려진 직교 다항식군과 관련이 있다. 이 크라프추크 다항식은 해밍 도식의 거리 관계 행렬의 고유값을 제공한다.