직교 배열

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

정의

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

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

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

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

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

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

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

성질

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

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

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

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

즉,

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

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

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

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

예

자명한 직교 배열

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

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

라틴 방진

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

${\displaystyle q\times q}$ 라틴 방진 ${\displaystyle M}$은

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

인 2-직교 배열

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

${\displaystyle B\subseteq \Sigma ^{3}}$

${\displaystyle |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-직교 배열의 예

알파벳

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

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

${\displaystyle B\subsetneq \Sigma ^{5}}$

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

은 지수

${\displaystyle (\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

알파벳

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

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

${\displaystyle B\subsetneq \Sigma ^{5}}$

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

은 지수

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

을 갖는 2-직교 배열을 이룬다.^[3]

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년에 칼리암푸디 라다크리슈나 라오가 도입하였다.^[4]

각주

1. Hedayat, Abdos Samad; Sloane, Neil James Alexander; Stufken, John (1999). 《Orthogonal arrays: theory and applications》. Springer Series in Statistics (영어). Springer-Verlag. doi:10.1007/978-1-4612-1478-6. ISBN 978-0-387-98766-8. ISSN 0172-7397. Zbl 0935.05001. 
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. doi:10.1109/18.720545. ISSN 0018-9448. 
3. Keedwell, A. Donald; Denes, József (2015). 《Latin squares and applications》 (영어) 2판. North-Holland. doi:10.1016/B978-0-444-63555-6.50016-7. Zbl 1318.05001. 
4. Rao, Calyampudi Radhakrishna (1947). “Factorial experiments derivable from combinatorial arrangements of arrays”. 《Supplement to the Journal of the Royal Statistical Society》 (영어) 9 (1): 128–139. doi:10.2307/2983576. JSTOR 2983576. 

외부 링크

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