직교 배열

조합론에서 직교 배열(直交配列, 영어: orthogonal array)은 좌표들의 부분 집합으로 제한하였을 때 모든 가능한 벡터들이 균등하게 분포되어 있는, 주어진 유한 집합 위의 벡터들의 유한 집합이다.

정의

자연수 $t\in \mathbb {N}$가 주어졌다고 하자.

$t$-직교 배열 $(\Sigma ,B)$은 다음과 같은 데이터로 주어진다.

• 크기 $q$의 유한 집합 $\Sigma$. 이를 알파벳이라고 하며, 그 원소를 수준(水準, 영어: level)이라고 한다.
• 자연수 $n\in \mathbb {N}$. 이를 인자수(因子數, 영어: number of factors)라고 한다.
• 부분 집합 $B\subseteq \Sigma ^{n}$. 그 원소를 실험 실행(實驗實行, 영어: experimental run)라고 한다.

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

• $\Sigma ^{n}$의 $n$개의 좌표 가운데 임의의 $t$개를 골랐을 때, 수준의 모든 $t$-순서쌍들은 (선택한 레벨 및 좌표에 상관없이) 같은 수 $\lambda _{t}$번 만큼 등장한다. 즉, 임의의 단사 함수 $f\colon \{1,2,\dots ,t\}\to \{1,\dotsc ,n\}$ 및 임의의 $x\in \Sigma ^{t}$에 대하여, 자연수 $\lambda _{t}=|\{b\in B\colon \forall 1\leq i\leq t\colon x_{i}=b_{f(i)}\}|\in \mathbb {N}$는 $f$ 및 $x$의 선택에 의존하지 않는다.

이는 해밍 결합 도식 $\operatorname {H} (n,\Sigma )$ 속의 블록 설계의 개념과 같다.

여기서, $t$를 직교 배열의 강도(強度, 영어: strength)라고 하며, $\lambda _{t}$를 $t$-직교 배열의 지수(指數, 영어: index)라고 한다.

성질

상수 $\lambda _{t}$에 대한 $t$-직교 배열 $(\Sigma ,B\subseteq \Sigma ^{n})$가 주어졌다고 하자. 그렇다면,

• 임의의 자연수 $t'\leq t$
• 임의의 단사 함수 $f\colon \{1,2,\dotsc ,t'\}\to \{1,2,\dotsc ,n\}$
• 임의의 $x\in \Sigma ^{t'}$

에 대하여, 다음이 성립한다.

$|\{b\in B\colon \forall 1\leq i\leq t'\colon x_{i}=b_{f(i)}\}|=\lambda _{t'}=\lambda _{t}|\Sigma |^{t-t'}$

즉,

$\lambda _{0}=\lambda _{t}|\Sigma |^{t}$

를 정의하면, 임의의 $t$-직교 배열은 임의의 $t'\leq t$에 대하여 $t'$-직교 배열을 이루며, 그 상수는 $\lambda _{t'}=\lambda _{0}|\Sigma |^{-t'}$이다. 여기서, $\lambda _{0}$는 물론 $B$의 크기와 같다.

이에 따라, 임의의 $\Sigma ^{n}$ 속에서 다음과 같은 포함 관계가 성립한다.

$\operatorname {Pow} (\Sigma ^{n})$ = 0-직교 배열 ⊇ 1-직교 배열 ⊇ 2-직교 배열 ⊇ … ⊇ $n$-직교 배열 = $\{\varnothing ,\Sigma ^{n}\}$

예

자명한 직교 배열

임의의 유한 집합 $\Sigma$에 대하여, $\Sigma ^{n}$ 속의 유일한 $n$-직교 배열은 $B=\varnothing$ 및 $B=\Sigma ^{n}$이며, 이 경우 각각 $\lambda _{n}=0$ 및 $\lambda _{n}=1$이다.

반대로, $\Sigma ^{n}$의 임의의 부분 집합은 0-직교 배열을 이룬다.

라틴 방진

 이 부분의 본문은 라틴 방진입니다.

$q\times q$ 라틴 방진 $M$은

$(\lambda _{2},\lambda _{1},\lambda _{0})=(1,q,q^{2})$

인 2-직교 배열

$\Sigma =\{1,2,\dotsc ,q\}$

$B\subseteq \Sigma ^{3}$

$|B|=\lambda _{0}=q^{2}$

에 해당한다.

(즉, 2-직교 배열과 라틴 방진 사이의 관계는 2-블록 설계와 2-슈타이너 계 사이의 관계와 같다.)

예를 들어, 3×3 라틴 방진

1	2	3
2	3	1
3	1	2

은 다음과 같은 표의 9개 행들로 구성되는 2-직교 배열을 이룬다.

1	1	1
1	2	2
1	3	3
2	1	2
2	2	3
2	3	1
3	1	3
3	2	1
3	3	2

2-직교 배열의 예

알파벳

$\Sigma =\{{\mathsf {A}},{\mathsf {B}},{\mathsf {C}},{\mathsf {D}}\}$

위에서, 다음 표의 16개 행들로 구성된 부분 집합

$B\subsetneq \Sigma ^{5}$

$|B|=\lambda _{0}=16$

은 지수

$(\lambda _{2},\lambda _{1},\lambda _{0})=(1,4,16)$

을 갖는 2-직교 배열을 이룬다.

A	A	A	A	A
A	B	B	B	B
A	C	C	C	C
A	D	D	D	D
B	A	D	B	C
B	B	C	A	D
B	C	B	D	A
B	D	A	C	B
C	A	B	C	D
C	B	A	D	C
C	C	D	A	B
C	D	C	B	A
D	A	C	D	B
D	B	D	C	A
D	C	A	B	D
D	D	B	A	C

알파벳

$\Sigma =\{{\mathsf {A}},{\mathsf {B}},{\mathsf {C}}\}$

위에서, 다음 표의 27개 행들로 구성된 부분 집합

$B\subsetneq \Sigma ^{5}$

$|B|=\lambda _{0}=27$

은 지수

$(\lambda _{2},\lambda _{1},\lambda _{0})=(3,9,27)$

을 갖는 2-직교 배열을 이룬다.

A	A	A	A	A
A	A	B	A	B
A	A	C	A	C
A	B	A	B	B
A	B	B	B	C
A	B	C	B	A
A	C	A	C	C
A	C	B	C	A
A	C	C	C	B
B	A	A	C	A
B	A	B	C	B
B	A	C	C	C
B	B	A	A	B
B	B	B	A	C
B	B	C	A	A
B	C	A	B	C
B	C	B	B	A
B	C	C	B	B
C	A	A	B	A
C	A	B	B	B
C	A	C	B	C
C	B	A	C	B
C	B	B	C	C
C	B	C	C	A
C	C	A	A	C
C	C	B	A	A
C	C	C	A	B

역사

1947년에 칼리암푸디 라다크리슈나 라오가 도입하였다.

외부 링크

• “Orthogonal array”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Orthogonal array”. 《Wolfram MathWorld》 (영어). Wolfram Research.