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

董朦朦，劉興祥，田雨禾

(延安大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 陜西 延安 716000)

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

1 預(yù)備知識

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

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

定義2[9]設(shè)矩陣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為數(shù)域F上的m階連元和幻方,并稱S為m階連元和幻方A的幻和。

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

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

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

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

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

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

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

2 主要結(jié)論

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

1) 當(dāng)n=2k+1時(shí),對由定理1構(gòu)造出的矩陣

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

2) 對由定理1構(gòu)造出的矩陣

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

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

4) 因?yàn)榫仃嘊中的元素滿足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是一個(gè)n階始元幻方。

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

5) 構(gòu)造序偶陣D=?(bij,cij)」n×n。假設(shè)矩陣B與C不是正交的,則存在數(shù)對(bij,cij)=(bkl,ckl),則必有ncij+bij=nckl+bkl,即有n(cij-ckl)=bkl-bij。又因?yàn)榫仃嘊、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。此時(shí),若i=k,則有bij=bkl,這與矩陣B是行拉丁方矛盾；若j=l,則有cij=ckl,這與矩陣C是列拉丁方矛盾；若i≠k且j≠l,則有aij=akl,這與矩陣A是幻方矛盾。

故假設(shè)不成立,矩陣B與C正交。

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

1) 當(dāng)n=4k時(shí)，對由定理2構(gòu)造出的矩陣

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

2) 對由定理2構(gòu)造出的矩陣

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

4) 因?yàn)榫仃嘊中的元素滿足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是一個(gè)n階始元幻方。

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

5) 構(gòu)造序偶陣D=?(bij,cij)」n×n。假設(shè)矩陣B與C不是正交的,則存在數(shù)對(bij,cij)=(bkl,ckl),則必有ncij+bij=nckl+bkl,即有n(cij-ckl)=bkl-bij。又因?yàn)榫仃嘊、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。

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

故假設(shè)不成立,矩陣B與C正交。

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

1) 當(dāng)n=4k+2時(shí),對由定理3構(gòu)造出的矩陣

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

2) 對由定理3構(gòu)造出的矩陣

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

4) 因?yàn)榫仃嘊中的元素滿足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是一個(gè)n階始元幻方。

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

5) 構(gòu)造序偶陣D=(bij,cij)」n×n。假設(shè)矩陣B與C不是正交的,則存在數(shù)對(bij,cij)=(bkl,ckl),則必有ncij+bij=nckl+bkl,即有n(cij-ckl)=bkl-bij。又因?yàn)榫仃嘊、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。此時(shí),若i=k,則有bij=bkl,這與矩陣B是行拉丁方矛盾;若j=l,則有cij=ckl,這與矩陣C是列拉丁方矛盾;若i≠k且j≠l,則有aij=akl,這與矩陣A是幻方矛盾。

故假設(shè)不成立,矩陣B與C正交。

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

證明當(dāng)n=2k+1時(shí),定理1已證；當(dāng)n=4k+1時(shí),定理2已證；當(dāng)n=4k+2時(shí),定理3已證。

3 結(jié)束語

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