正交陣列

正交陣列(orthogonal array)是一類組合設計，設A是v元集X上的v×k矩陣，若對任意d(2≤d≤k)列所構成的子矩陣，X上的每一個d元排列作為子矩陣的行各出現λ次，則稱A為大小N，約束數k，水平數v，強度d和指數λ的正交陣列，在試驗設計中稱正交表，記為OA(N，k，v，d)，由定義有N=λv^d，強度2的正交陣列記為OA(v，k;λ)，當λ=1時簡記為OA(v，k).OA(v，k;λ)的存在性等價於橫截設計TDλ[k;v]的存在性，OA(v，k)的存在性則等價於k-2個v階相互正交拉丁方的存在性。

基本介紹

• 中文名：正交陣列
• 外文名：orthogonal array
• 所屬學科：數學
• 所屬問題：組合學（組合設計理論）
• 簡介：一類組合設計

基本介紹

定義1 設n≥1，k≥2，A為n元集S上的一個k×n²矩陣：

若對任意1≤i<j≤k，A的第i行與第j行都正交，即

則稱A是集合S上一個約束數(constraint)為k的n階正交陣列(orthogonal array)。記作OA(n，1；k)。

正交陣列與正交拉丁方的關係

關於正交陣列與正交拉丁方之間的關係。我們有下述引理：

引理1 OA(n，1；k)的存在性等價於(k-2)-MOLS(n)的存在性。

證 若(k-2)-MOLS(n)存在,不失一般性,可設A₁,A₂,…,A_k-2為集合S=Z_n上k-2個兩兩正交的n階拉丁方：

其中1≤i≤k-2，設s=k-2，在集合S上構作如下k×n²陣列A：

由引理1及A₁,A₂,…,A_k-2的正交性可知A是S上的一個OA(n,1；k)。

反之。設A是S上的一個OA(n，1；k)，由於交換A中任意兩列後仍得到一個OA(n，1；k)。故不妨設A的前兩行即為式(4)中陣列的前兩行。由它們分別給出R_n與C_n，然後對1≤i≤k-2。由A的第i+2行相應作出n×n矩陣A_i．由OA(n，1；k)中各行的正交性可知A₁,A₂,…,A_k-2即為一組(k-2)-MOLS(n)。

正交陣列與橫截設計的關係

下面討論正交陣列與橫截設計之間的關係。

引理2 存在OA(n，1；k)的充分必要條件為存在TD(k，1；n).

證 設X={0，1，2，…，n-1)。K={1，2，…，n]，V=K×X，(V，G，A)為一個TD(k，1；n)，不失一般性，可設

G={{i}×X|i∈K}．

今由(V，G，A)構作X上的一個k×n²陣列A如下：

若{(1，a₁)，(2，a₂)，…，(k，a_k)}為A中的一個區組。則以(a₁，a₂，…，a_k)^T作為A中的一列，由於一個TD(k，1；n)共包含n²個區組。因此A是X上一個k×n²陣列，下面證明A是一個OA(n，1；k)。

設1≤i<j≤k，對任意x,y ∈X。由於(i,x)與(i,y)屬於G中兩個不同的組，故必有A中唯一的區組{(1，a₁)，(2，a₂)，…，(k，a_k)}使a_i=x,a_j=y,從而x與y在A中位於同一列,於是得到陣列A中第i行與第j行的正交性,故A為一個OA(n,1；n)。

反之。設A為X上的一個OA(n，1；k)，在V=K×X上構作關聯結構D=((V，G，A)，其中，

G={{i}×X|1≤i≤k}.

使對應於A中任意一列(a₁，a₂，…，a_k)^T，在A中有一個區組{(1，a₁)，(2，a₂)，…，(k，a_k)}。如此共得n²個區組，由A中各行之間的正交性可知V中任意一對不同組的元素恰在A的唯一的一個區組中相遇，因此D確實是一個TD(k,1；n)。即得結論。

引理3 TD(k，1；n)的存在性等價於RTD(k-1，1；n)的存在性。

綜合引理1-3。便得下述定理。

定理1 設k與n為給定的正整數，k≥3，則下述命題彼此等價：

(i)存在k-2個兩兩正交的n階拉丁方；

(ii)存在正交陣列OA(n，1；k)；

(iii)存在橫截設計TD(k，1；n)；

(iv)存在可分解橫截設計RTD(k-1，1；n)。