직교 배열

조합론에서 **직교 배열**(直交配列, orthogonal array)은 좌표들의 부분 집합으로 제한하였을 때 모든 가능한 벡터들이 균등하게 분포되어 있는, 주어진 유한 집합 위의 벡터들의 유한 집합이다.언어=en
# 정의
자연수 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\le i\le t\colon x_i=b_{f(i)}\\}|\in\mathbb N는 f 및 x의 선택에 의존하지 않는다. 이는 해밍 결합 도식 \operatorname H(n,\Sigma) 속의 블록 설계의 개념과 같다.언어=en 여기서, t를 직교 배열의 **강도**(強度, strength)라고 하며, \lambda_t를 t-직교 배열의 **지수**(指數, index)라고 한다.
# 성질
상수 \lambda_t에 대한 t-직교 배열 (\Sigma,B\subseteq\Sigma^n)가 주어졌다고 하자. 그렇다면, * 임의의 자연수 t'\le t * 임의의 단사 함수 f\colon\\{1,2,\dotsc,t'\\}\to\\{1,2,\dotsc,n\\} * 임의의 x\in\Sigma^{t'} 에 대하여, 다음이 성립한다. :|\\{b\in B\colon \forall 1\le i\le t'\colon x_i=b_{f(i)}\\}|=\lambda_{t'}=\lambda_t|\Sigma|^{t-t'} 즉, :\lambda_0=\lambda_t|\Sigma|^t 를 정의하면, 임의의 t-직교 배열은 임의의 t'\le 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 라틴 방진 :{| 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-직교 배열의 예
알파벳 :\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-직교 배열을 이룬다. :{| class=wikitable | 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-직교 배열을 이룬다.언어=en :{| class=wikitable | 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년에 칼리암푸디 라다크리슈나 라오가 도입하였다.언어=en