직교 배열 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''직교 배열'''(直交配列, {{llang|en|orthogonal array}})은 좌표들의 부분 집합으로 제한하였을 때 모든 가능한 벡터들이 균등하게 분포되어 있는, 주어진 [[유한 집합]] 위의 벡터들의 [[유한 집합]]이다.<ref>{{서적 인용|제목=Orthogonal arrays: theory and applications|출판사=Springer-Verlag|이름1=Abdos Samad |성1=Hedayat|이름2=Neil James Alexander|성2=Sloane |이름3=John|성3=Stufken|doi= 10.1007/978-1-4612-1478-6|총서=Springer Series in Statistics|issn=0172-7397|날짜=1999|isbn=978-0-387-98766-8|url=http://neilsloane.com/doc/OA.html|zbl=0935.05001|언어=en}}</ref>

== 정의 ==
자연수 <math>t\in\mathbb N</math>가 주어졌다고 하자.

<math>t</math>-'''직교 배열''' <math>(\Sigma, B)</math>은 다음과 같은 데이터로 주어진다.
* [[집합의 크기|크기]] <math>q</math>의 [[유한 집합]] <math>\Sigma</math>. 이를 '''알파벳'''이라고 하며, 그 원소를 '''수준'''(水準, {{llang|en|level}})이라고 한다.
* [[자연수]] <math>n\in\mathbb N</math>. 이를 '''인자수'''(因子數, {{llang|en|number of factors}})라고 한다.
* [[부분 집합]] <math>B\subseteq \Sigma^n</math>. 그 원소를 '''실험 실행'''(實驗實行, {{llang|en|experimental run}})라고 한다.
이는 다음 조건을 만족시켜야 한다.
* <math>\Sigma^n</math>의 <math>n</math>개의 좌표 가운데 임의의 <math>t</math>개를 골랐을 때, 수준의 모든 <math>t</math>-[[순서쌍]]들은 (선택한 레벨 및 좌표에 상관없이) 같은 수 <math>\lambda_t</math>번 만큼 등장한다. 즉, 임의의 [[단사 함수]] <math>f\colon\{1,2,\dots,t\}\to\{1,\dotsc,n\}</math> 및 임의의 <math>x\in\Sigma^t</math>에 대하여, 자연수 <math>\lambda_t=|\{ b\in B\colon\forall 1\le i\le t\colon  x_i=b_{f(i)}\}|\in\mathbb N</math>는 <math>f</math> 및 <math>x</math>의 선택에 의존하지 않는다.

이는 [[해밍 결합 도식]] <math>\operatorname H(n,\Sigma)</math> 속의 [[블록 설계]]의 개념과 같다.<ref>{{저널 인용|성=Delsarte|이름=Philippe|성2=Levenshtein|이름2=Vladimir Iosifovich|저자링크2=블라디미르 레벤시테인|날짜=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|언어=en}}</ref>

여기서, <math>t</math>를 직교 배열의 '''강도'''(強度, {{llang|en|strength}})라고 하며, <math>\lambda_t</math>를 <math>t</math>-직교 배열의 '''지수'''(指數, {{llang|en|index}})라고 한다.

== 성질 ==
상수 <math>\lambda_t</math>에 대한 <math>t</math>-직교 배열 <math>(\Sigma,B\subseteq\Sigma^n)</math>가 주어졌다고 하자. 그렇다면,
* 임의의 자연수 <math>t'\le t</math>
* 임의의 [[단사 함수]] <math>f\colon\{1,2,\dotsc,t'\}\to\{1,2,\dotsc,n\}</math>
* 임의의 <math>x\in\Sigma^{t'}</math>
에 대하여, 다음이 성립한다.
:<math>|\{b\in B\colon \forall 1\le i\le t'\colon x_i=b_{f(i)}\}|=\lambda_{t'}=\lambda_t|\Sigma|^{t-t'}</math>
즉,
:<math>\lambda_0=\lambda_t|\Sigma|^t</math>
를 정의하면, 임의의 <math>t</math>-직교 배열은 임의의 <math>t'\le t</math>에 대하여 <math>t'</math>-직교 배열을 이루며, 그 상수는 <math>\lambda_{t'}=\lambda_0|\Sigma|^{-t'}</math>이다. 여기서, <math>\lambda_0</math>는 물론 <math>B</math>의 [[집합의 크기|크기]]와 같다.

이에 따라, 임의의 <math>\Sigma^n</math> 속에서 다음과 같은 포함 관계가 성립한다.
:<math>\operatorname{Pow}(\Sigma^n)</math> = 0-직교 배열 ⊇ 1-직교 배열 ⊇ 2-직교 배열 ⊇ … ⊇ <math>n</math>-직교 배열 = <math>\{\varnothing,\Sigma^n\}</math>

== 예 ==
=== 자명한 직교 배열 ===
임의의 [[유한 집합]] <math>\Sigma</math>에 대하여, <math>\Sigma^n</math> 속의 유일한 <math>n</math>-직교 배열은 <math>B=\varnothing</math> 및 <math>B=\Sigma^n</math>이며, 이 경우 각각 <math>\lambda_n=0</math> 및 <math>\lambda_n=1</math>이다.

반대로, <math>\Sigma^n</math>의 임의의 [[부분 집합]]은 0-직교 배열을 이룬다.

=== 라틴 방진 ===
{{본문|라틴 방진}}
<math>q\times q</math> [[라틴 방진]] <math>M</math>은
:<math>(\lambda_2,\lambda_1,\lambda_0)=(1,q,q^2)</math>
인 2-직교 배열
:<math>\Sigma=\{1,2,\dotsc,q\}</math>
:<math>B\subseteq\Sigma^3</math>
:<math>|B|=\lambda_0=q^2</math>
에 해당한다.

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

예를 들어, 3×3 [[라틴 방진]]
:{| class=wikitable
| 1 || 2 || 3
|-
| 2 || 3 || 1
|-
| 3 || 1 || 2
|}
은 다음과 같은 표의 9개 행들로 구성되는 2-직교 배열을 이룬다.
:{| class=wikitable
| 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-직교 배열의 예 ===
알파벳
:<math>\Sigma=\{\mathsf A,\mathsf B,\mathsf C,\mathsf D\}</math>
위에서, 다음 표의 16개 행들로 구성된 부분 집합
:<math>B\subsetneq\Sigma^5</math>
:<math>|B|=\lambda_0=16</math>
은 지수
:<math>(\lambda_2,\lambda_1,\lambda_0)=(1,4,16)</math>
을 갖는 2-직교 배열을 이룬다.
:{| class=wikitable style="text-align: center"
| 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
|}

알파벳
:<math>\Sigma=\{\mathsf A,\mathsf B,\mathsf C\}</math>
위에서, 다음 표의 27개 행들로 구성된 부분 집합
:<math>B\subsetneq\Sigma^5</math>
:<math>|B|=\lambda_0=27</math>
은 지수
:<math>(\lambda_2,\lambda_1,\lambda_0)=(3,9,27)</math>
을 갖는 2-직교 배열을 이룬다.<ref>{{서적 인용|이름1=A. Donald|성1=Keedwell|이름2=József|성2=Denes|제목=Latin squares and applications|판=2|doi=10.1016/B978-0-444-63555-6.50016-7|출판사=North-Holland|날짜=2015|zbl=1318.05001|언어=en}}</ref>

:{| class=wikitable style="text-align: center"
| 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년에 [[칼리암푸디 라다크리슈나 라오]]가 도입하였다.<ref>{{저널 인용|성=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|언어=en}}</ref>

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Orthogonal array}}
* {{매스월드|id=OrthogonalArray|title=Orthogonal array}}

{{전거 통제}}

[[분류:조합론]]
[[분류:실험 설계]]