正交拉丁方

兩個n階拉丁方在同一位置上的數依次配置成對時,如果這兩個有序數對恰好各不相同(一般處理方法為把當中某些行或列對調)(這種相同即經過有限次鏇轉和鏡像對稱後不重合)。下面是兩個互為正交的4階拉丁方。

簡介

兩個n階拉丁方在同一位置上的數依次配置成對時,如果這兩個有序數對恰好各不相同(一般處理方法為把當中某些行或列對調)(這種相同即經過有限次鏇轉和鏡像對稱後不重合)。下面是兩個互為正交的4階拉丁方

(4.1)(3.3)(2.4)(1.2)

(2.2)(1.4)(4.3)(3.1)

(1.3)(2.1)(3.2)(4.4)

(3.4)(4.2)(1.1)(2.3)

已經證明,除2、6階外,其他階拉丁方都存在正交拉丁方。6階的正交拉丁方源自於歐拉提出的三十六軍官問題.

解法

拉丁方與正交拉丁方組 1. 定義: (拉丁方)

A 為 n 乘 n 矩陣, 若 A 的每行,每列都恰好是 (1, 2, ..., n) 的一個置換,則稱 A 是 n 階拉丁方.

2. 定義: (正交拉丁方)

設 N={1,2,...,n}. 若 A=(a_{i,j}}, B=(b_{i,j}) 都是 n 階拉丁方, 且滿足:

{(a_{i,j}, b_{i,j}) : i=1..n, j=1..n} = N^2

則稱 A, B 是正交拉丁方.

3. 定義: (正交拉丁方組)

{A_1, ..., A_k} 是 k 個 n 階拉丁方, 若它們兩兩正交,則稱它們是一個正交拉丁方組.

4. 定理: 若 A=(a_{i,j}), B 是正交 n 階拉丁方. f 是 {1, 2, ..., n} 到自身的一個置換. 設 C={c_{i,j}} 使得:

c_{i,j}=f(a_{i,j}),

則 C, 仍是拉丁方,且 C, B 是正交拉丁方. 我們把 C 記為 f(A).

5. 設 S 是 n 階正交拉丁方組, 則 |S|< n.

6. 定義: (飽和正交拉丁方組)

設 S 是 n 階正交拉丁方組,若 |S|=n-1,則稱 S 是飽和的.

7. 定理: 若 n 是素數方冪, 則存在飽和的 n 階正交拉丁方組.

8. 定理: 設 {A_1,..., A_k} 是一個 n 階正交拉丁方組,而 {B_1,..., B_k} 是一個 m 階正交拉丁方組. 則在此基礎上,可以構造出 mn 階正交拉丁方組 {C_1,..., C_k}.

9. 設 n 有典範分解

p_1^{a_1} ... p_s^{a_s},

而 r = min {p_j^{a_j} : j=1..s}, 則存在 r 個正交的 n 階拉丁方.

相關詞條

相關搜尋

熱門詞條

聯絡我們