幻方可以分解為兩個正交拉丁方的線性組合

董朦朦，劉興祥，田雨禾

(延安大學 數學與計算機科學學院， 陜西 延安 716000)

J.Dénes和A.D.kecdWell[1]在1988年的American Mathematical Monthly中發表了題為“A Conjecture Concerning Magic” 的文章,提出了問題： “任何幻方是否都能表示為兩個正交方陣之和，其中之一為行拉丁方，另一個為列拉丁方。”歷年來,關于矩陣的分解已有很多方法[2-7]，但對幻方的分解還尚未研究。本文應用幻方、行拉丁方、列拉丁方以及正交拉丁方的定義，結合矩陣分解知識對幻方進行分解。

1 預備知識

定義1[8]若矩陣A=(aij)m×m∈Fm×m滿足：

則稱矩陣A為數域F上的m階和幻方,并稱S為m階和幻方A的幻和;Sc為m階列和幻陣A的列幻和;Sr為m階行列和幻陣A的行幻和。

定義2[9]設矩陣A=(aij)m×m∈{a+1,a+2,…,a+m2}m×m,a∈Z,若矩陣A滿足

④ aij=akl(i≠k或j≠l, i, j, k, l=1,2,…,m)。

則稱矩陣A為數域F上的m階連元和幻方,并稱S為m階連元和幻方A的幻和。

定義3[9]設矩陣A=(aij)m×m∈{1,2,…,m2}m×m,若矩陣A滿足

④ aij=akl(i≠k或j≠l, i, j, k, l=1,2,…,m)。

則稱矩陣A為數域F上的m階始元和幻方，并稱S為m階始元和幻方A的幻和。

定義4[10]設矩陣A=(aij)n×n∈Sn×n,n∈N*,其中S={x1,x2,…,xn},對于?i,j∈{1,2,…,n},i≠j時有xi≠xj,滿足以下條件：

① 若?i,j,k∈{1,2,…,n},且j≠k有aij≠aik恒成立;

② 若?i,j,k∈{1,2,…,n},且i≠j有aik≠ajk恒成立。

則稱矩陣A=(aij)n×n為S上的n階拉丁方。

定義5[2]設矩陣A=(aij)n×n∈Sn×n,n∈N*,其中S={x1,x2,…,xn},對于?i,j∈{1,2,…,n},i≠j時，有xi≠xj,且?i,j,k∈{1,2,…,n},有j≠k時，aij≠aik恒成立,則稱矩陣A=(aij)n×n為S上的n階行拉丁方。

定義6[10]設矩陣A=(aij)n×n∈Sn×n,n∈N*,其中S={x1,x2,…,xn},對于?i,j∈{1,2,…,n},i≠j時，有xi≠xj,且?i,j,k∈{1,2,…,n},i≠j時，aik≠ajk恒成立,則稱矩陣A=(aij)n×n為S上的n階列拉丁方。

定義7 設矩陣A=(aij)n×n、B=(bij)n×n∈Sn×n是兩個n階拉丁方,若對于序偶陣C=?(aij,bij)」n×n中,對于?i,j∈{1,2,…,n},當i≠k或j≠l時,(aij,bij)≠(alk,blk)恒成立,則稱矩陣A和矩陣B正交,或稱矩陣A與B是互相正交的矩陣。

注：下文所用ei均為n維行向量。

2 主要結論

證明先證矩陣A滿足幻方的條件。

1) 當n=2k+1時,對由定理1構造出的矩陣

觀察知：矩陣B的各行的元素都是1,2，…，2k,2k+1的全排列,故稱矩陣B為n階行拉丁方。

2) 對由定理1構造出的矩陣

觀察知：矩陣C的各列的元素都是0,1,2,…,2k-1,2k的全排列,故稱矩陣C為n階列拉丁方。

下面證明矩陣A中的元素是{1,2,…,n2}的全排列。

4) 因為矩陣B中的元素滿足1≤bij≤n,矩陣C中的元素滿足0≤cij≤n-1,則矩陣nC中的元素滿足0≤ncij≤n2-n,所以矩陣A=nC+B中的元素滿足1≤aij≤n2且有?i,j,k,l∈{1,2,…,n2}，aij≠akl,則矩陣A中的元素是{1,2,…,n2}的全排列。綜上所述,矩陣A是一個n階始元幻方。

下面證明行拉丁方B和列拉丁方C是正交的。

5) 構造序偶陣D=?(bij,cij)」n×n。假設矩陣B與C不是正交的,則存在數對(bij,cij)=(bkl,ckl),則必有ncij+bij=nckl+bkl,即有n(cij-ckl)=bkl-bij。又因為矩陣B、C中元素滿足1≤bij≤n,0≤cij≤n-1,所以有|cij-ckl|≤n-1,|bkl-bij|≤n-1。若ckl-cij≠0,則必有bij-bkl>n,這與|bkl-bij|≤n-1矛盾，故cij=ckl,bij=bkl。此時,若i=k,則有bij=bkl,這與矩陣B是行拉丁方矛盾；若j=l,則有cij=ckl,這與矩陣C是列拉丁方矛盾；若i≠k且j≠l,則有aij=akl,這與矩陣A是幻方矛盾。

故假設不成立,矩陣B與C正交。

證明先證矩陣A滿足幻方的條件。

1) 當n=4k時，對由定理2構造出的矩陣

觀察知：矩陣B的各行的元素都是1,2，…，4k-1,4k的全排列,故稱矩陣B為n階行拉丁方。

2) 對由定理2構造出的矩陣

觀察知：矩陣C的各列的元素都是0，1,2,…,4k-2,4k-1的全排列,故稱矩陣C為n階列拉丁方。

4) 因為矩陣B中的元素滿足1≤bij≤n,矩陣C中的元素滿足0≤cij≤n-1,則矩陣nC中的元素滿足0≤ncij≤n2-n,所以矩陣A=nC+B中的元素滿足1≤aij≤n2且 ?i,j,k,l∈{1,2,…,n2}，aij≠akl,則矩陣A中的元素是{1,2,…,n2}的全排列。綜上所述,矩陣A是一個n階始元幻方。

下面證明行拉丁方B和列拉丁方C是正交的。

5) 構造序偶陣D=?(bij,cij)」n×n。假設矩陣B與C不是正交的,則存在數對(bij,cij)=(bkl,ckl),則必有ncij+bij=nckl+bkl,即有n(cij-ckl)=bkl-bij。又因為矩陣B、C中元素滿足1≤bij≤n,0≤cij≤n-1,所以有|cij-ckl|≤n-1,|bkl-bij|≤n-1。若ckl-cij≠0,則必有bij-bkl>n,這與|bkl-bij|≤n-1矛盾。故cij=ckl,bij=bkl。

此時,若i=k,則有bij=bkl,這與矩陣B是行拉丁方矛盾；若j=l,則有cij=ckl,這與矩陣C是列拉丁方矛盾；若i≠k且j≠l,則有aij=akl,這與矩陣A是幻方矛盾。

故假設不成立,矩陣B與C正交。

證明先證矩陣A滿足幻方的條件。

1) 當n=4k+2時,對由定理3構造出的矩陣

觀察知：矩陣B的各行的元素都是1,2，…，4k+1,4k+2的全排列,故稱矩陣B為n階行拉丁方。

2) 對由定理3構造出的矩陣

觀察知：矩陣C的各列的元素都是0，1,2,…,4k,4k+1的全排列,故稱矩陣C為n階列拉丁方。

4) 因為矩陣B中的元素滿足1≤bij≤n,矩陣C中的元素滿足0≤cij≤n-1,則矩陣nC中的元素滿足0≤ncij≤n2-n,所以矩陣A=nC+B中的元素滿足1≤aij≤n2且有?i,j,k,l∈{1,2,…,n2}，aij≠akl,則矩陣A中的元素是{1,2,…,n2}的全排列。綜上所述，矩陣A是一個n階始元幻方。

下面證明行拉丁方B和列拉丁方C是正交的。

5) 構造序偶陣D=(bij,cij)」n×n。假設矩陣B與C不是正交的,則存在數對(bij,cij)=(bkl,ckl),則必有ncij+bij=nckl+bkl,即有n(cij-ckl)=bkl-bij。又因為矩陣B、C中元素滿足1≤bij≤n,0≤cij≤n-1,所以有|cij-ckl|≤n-1,|bkl-bij|≤n-1。若ckl-cij≠0,則必有bij-bkl>n,這與|bkl-bij|≤n-1矛盾。故cij=ckl,bij=bkl。此時,若i=k,則有bij=bkl,這與矩陣B是行拉丁方矛盾;若j=l,則有cij=ckl,這與矩陣C是列拉丁方矛盾;若i≠k且j≠l,則有aij=akl,這與矩陣A是幻方矛盾。

故假設不成立,矩陣B與C正交。

定理4 幻方可以分解為兩個正交拉丁方之和，其中之一為行拉丁方，另一個為列拉丁方 (這里行拉丁方指定理中的矩陣B,列拉丁方指矩陣D=nC)。

證明當n=2k+1時,定理1已證；當n=4k+1時,定理2已證；當n=4k+2時,定理3已證。

3 結束語

本文主要研究了始元幻方和連元幻方可以分解為兩個正交拉丁方的線性組合，類自然數幻方是否可以作此分解有待進一步研究。