직교 배열: 두 판 사이의 차이

내용 삭제됨 내용 추가됨

인라인

2017년 6월 10일 (토) 08:51 판

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

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

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

크기 $q$ 의 유한 집합 $\Sigma$ . 이를 알파벳이라고 하며, 그 원소를 레벨(영어: level)이라고 한다.
부분 집합 $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} (\Sigma ,n)$ 속의 블록 설계의 개념과 같다.^[1]

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

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

|\{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'}$ 이다.

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

0-직교 배열

\supseteq

1-직교 배열

\supseteq

2-직교 배열

\supseteq

…

만약 $B=\Sigma ^{n}$ 일 경우, $(\Sigma ,B)$ 는 자명하게 $n$ -직교 배열을 이루며, 이 경우 $\lambda _{t}=1$ 이다.

$q\times q$ 라틴 방진 $M$ 은 $\lambda _{2}=1$ 인 2-직교 배열

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

B\subseteq \Sigma ^{3}

에 해당한다.

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

집합

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

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

B\subsetneq \Sigma ^{5}

|B|=16

은 상수 $\lambda _{t}=1$ 을 갖는 2-직교 배열을 이룬다.

1947년에 칼리암푸디 라다크리슈나 라오(칸나다어: ಕಲ್ಯಂಪೂಡಿ ರಾಧಾಕೃಷ್ಣ ರಾವ್, 영어: Calyampudi Radhakrishna Rao)가 도입하였다.^[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.
↑ Rao, C. R. (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.

Hedayat, A. S.; 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.

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