自正交拉丁方

自正交拉丁方(self-orthogonal Latin square)是一類特殊的拉丁方，指與自身的轉置相正交的拉丁方，亦即(2，1，3)共軛正交拉丁方。v階自正交拉丁方存在的充分必要條件是v≠2，3，6。

基本介紹

• 中文名：自正交拉丁方
• 外文名：self-orthogonal Latin square
• 所屬學科：數學
• 所屬領域：組合學(組合設計)
• 屬性：一類特殊的拉丁方
• 定義：與自身的轉置相正交的拉丁方

基本介紹

自正交拉丁方(self-orthogonal Latin square)是一類特殊的拉丁方，指與自身的轉置相正交的拉丁方，亦即(2，1，3)共軛正交拉丁方。v階自正交拉丁方存在的充分必要條件是v≠2，3，6。自正交拉丁方可用來安排一種特殊形式的網球賽，即所謂配偶迴避的混合雙打循環賽，設n對夫婦進行一場混合雙打循環賽，要求：

1.配偶不出現在同一局比賽中，不論是作為伴對還是作為抗對；

2.性別相同的兩個參賽者將作為抗對恰在一局中相遇；

3.每一對非配偶的異性參賽者將作為伴對在一局比賽中相遇，且作為抗對在又一局比賽中相遇。

這類安排對應於一個拉丁方A=(a_ij)。設第i對夫婦為i先生及i太太，當i先生與j先生在某一局中相遇時，與i先生搭檔者設為a_ij太太，與j先生搭檔者設為a_ji太太。於是，由上述安排得到的冪等拉丁方是自正交的，反之，由一個冪等自正交拉丁方可得到相應的循環賽安排，這樣，配偶迴避的混合雙打循環賽安排等價於一個冪等自正交拉丁方，而後者的存在性又等價於自正交拉丁方的存在性。

共軛正交拉丁方

共軛正交拉丁方(conjugate orthogonal Latin squares)是一類特殊的拉丁方，若(Q，⊙)為一擬群，則在集Q上可定義5個新的二元運算⊙(i，j，k)如下：當a⊙b=c時，a⊙(1，3，2)c=b，b⊙(2，1，3)a=c，b⊙(2，3，1)c=a，c⊙(3，1，2)a=b，c⊙(3，2，1)b=a，由此得5個擬群(Q，⊙(i，j，k))，稱為擬群(Q，⊙)的(i，j，k)共軛擬群，若擬群(Q，⊙)的乘法表所定義的拉丁方為L，則其(i，j，k)共軛擬群的乘法表所定義的拉丁方稱為L的(i，j，k)共軛拉丁方，若拉丁方L與它的(i，j，k)共軛拉丁方正交，則稱L為(i，j，k)共軛正交拉丁方，簡記為(i，j，k)-COLS(v)，其中v為階數。一個(2，1，3)共軛正交拉丁方通常稱為自正交拉丁方。(3，2，1)-COLS(v)的存在性等價於(1，3，2)-COLS(v)的存在性，(3，1，2)-COLS(v)與(2，3，1)-COLS(v)也是同時存在或同時不存在的。共軛正交拉丁方的存在性問題已經解決，若且唯若v≠2，3，6時，存在(2，1，3)-COLS(v)，若且唯若v≠2，6時，存在(3，1，2)-COLS(v)及(3，2，1)-COLS(v)。

相關性質定理

一個拉丁方如若與其轉置陣正交，則稱為自正交拉丁方(self-orthogonalLatinsquare)。n階自正交拉方記作SOLS(n)，下面主要關於自正交拉丁方的構作方法（詳細證明過程可參考相應書籍）。

定義1設A= (a_ij)為加法群Z_n上的SOLS(n)，若對任意 都有

則稱A為一個循環SOLS(n)。

引理1 循環SOLS(12)與循環SOLS(15)都存在。

證：對n= 12,15,我們給出循環SOLS(n)的初始行如下:

(i)n=12，初始行: (1 8 3 6 2 9 11 1 10 5 7 4)；

(i)n=15，初始行: (0 2 11 6 10 13 5 14 4 7 12 1 9 8 3)。

下面是關於N.S.Mendelsohn關於自正交拉丁方的直接構作法。

定理1若(n,6)= 1，則存在循環SOLS(n)。

定理2 設q為素數冪，q≥4，則存在SOLS(q)。

引理2 若A是自正交拉丁方，則A的主對角線是截線。

下面關於自正交拉丁方的遞歸構造方法，令

S= {n|存在SOLS(n)}.

定理3S是一個PBD閉集。

證明： 要證S是PBD閉集，也就是要證下述結論: 若存在B(K,1;v)使對任意k∈K都有SOLS(k)存在，則SOLS(v)也必存在。

設(X,A)為一個B(K,1;v).設B∈A,|B|=k∈K，可在B上構作一個SOLS (k)。由引理1，每一個自正交拉丁方的主對角線都是截線。因此經對B中元素作適當置換後，總可設所得到的SOLS(k)是冪等的，從而在由此所得到的正交陣列OA(k,1;4)中，對每一個元素a∈B,(a,a,a,a)都是此OA(k,1;4)中的一列，將所有k個這樣的列去掉，剩下的4x(k-k)陣列記作D_B。對每一個B∈A，都得到一個D_B，將所有這些D_B排成一行，再添上每個a∈X得到的列(a,a,a,a)，由此得到一個陣列D，則D是個OA(v,1;4)，且由D的第3行與第4行得到的兩個v階拉丁方互為轉置，由此即得到一個SOLS(v)，即v∈S，從而S為PBD閉集。

引理3設n= 10或14，則SOLS(n)存在。

引理4設n∈{18,26,30}，則SOLS(n)存在。

引理5 設n∈{38,42}，則SOLS(n)存在。

引理6設N(m) > 3，0≤t≤m，若SOLS(m)與SOLS(t)都存在，則SOLS(4m+t)也存在。

有了以上準備，現在可以給出自正交拉丁方存在性問題的完整解決，即證明下述著名的Brayton-Coppersmith-Hoffman (BCH)定理。

定理4設n為正整數，則SOLS(n)存在的充分必要條件為 。