基本介紹
- 中文名:自正交拉丁方
- 外文名:self-orthogonal Latin square
- 所屬學科:數學
- 所屬領域:組合學(組合設計)
- 屬性:一類特殊的拉丁方
- 定義:與自身的轉置相正交的拉丁方
基本介紹,共軛正交拉丁方,相關性質定理,
基本介紹
自正交拉丁方(self-orthogonal Latin square)是一類特殊的拉丁方,指與自身的轉置相正交的拉丁方,亦即(2,1,3)共軛正交拉丁方。v階自正交拉丁方存在的充分必要條件是v≠2,3,6。自正交拉丁方可用來安排一種特殊形式的網球賽,即所謂配偶迴避的混合雙打循環賽,設n對夫婦進行一場混合雙打循環賽,要求:
1.配偶不出現在同一局比賽中,不論是作為伴對還是作為抗對;
2.性別相同的兩個參賽者將作為抗對恰在一局中相遇;
3.每一對非配偶的異性參賽者將作為伴對在一局比賽中相遇,且作為抗對在又一局比賽中相遇。
這類安排對應於一個拉丁方A=(aij)。設第i對夫婦為i先生及i太太,當i先生與j先生在某一局中相遇時,與i先生搭檔者設為aij太太,與j先生搭檔者設為aji太太。於是,由上述安排得到的冪等拉丁方是自正交的,反之,由一個冪等自正交拉丁方可得到相應的循環賽安排,這樣,配偶迴避的混合雙打循環賽安排等價於一個冪等自正交拉丁方,而後者的存在性又等價於自正交拉丁方的存在性。
共軛正交拉丁方
共軛正交拉丁方(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= (aij)為加法群Zn上的SOLS(n),若對任意
都有
![](/img/1/48a/wZ2NnLiVmY2EzMwkDOyYGNyADZhNTMhZmZ5EGZ3YmZlZGZ2AzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/9/6ce/wZ2NnLzEmMzMDMxkzYzEjYzM2Y2MmYwMzNhlDNkFGOmFzMjV2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
引理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)陣列記作DB。對每一個B∈A,都得到一個DB,將所有這些DB排成一行,再添上每個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)存在的充分必要條件為
。
![](/img/1/b15/wZ2NnLyM2MxY2YiVDO0MGMyMGZlJWMmZTZyYDN2kTOwYTN3gzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)