3.2 广义全等和拉丁方构成![]()
定义二:由
n个1,2,3....n组成的n×n方阵,若任一行任一列及所有泛对角线上的各数都是由1,2,3...n组成的一种排列,无重复数出现,其和均相等San(n+1)/2,则称该方阵为纯拉丁方,记为L(i,j)。若任一行任一列及所有泛对角线允许出现重复数,但其和仍相等,则称该方阵为n阶广义全等和拉丁方,记为L(I,J),或称全等和幻基方。如图15,图16所示。|
1 |
2 |
3 |
4 |
5 |
| 4 | 5 | 1 | 2 | 3 |
| 2 |
3 |
4 |
5 |
1 |
| 5 |
1 |
2 |
3 |
4 |
| 3 |
4 |
5 |
1 |
2 |
1
4
1
4
2 3 2 3 4 1
4
1
3 2
3
2
图15 L(i,j) 图16 L(I,J)
定义三:设
n阶广义全等和拉丁方,若将其第一列,第二列...第n列作为新方阵的第一行,第二行...第n行,则称新方阵LT(J,I)为L(I,J)方阵的转置方阵。见17。|
1 |
4 |
1 |
4 |
|
1 |
2 |
4 |
3 |
|
2 |
3 |
2 |
3 |
4 |
3 |
1 |
2 |
|
|
4 |
1 |
4 |
1 |
1 |
2 |
4 |
3 |
|
|
3 |
2 |
3 |
2 |
4 |
3 |
1 |
2 |
L(I,J) a LT(J,I) b
图17定义四:设
L1(I,J),L2(I,J)为同阶广义全等和拉丁方,若把L1(I,J)重叠到L2(I,J)上,若叠加后所有的序对均不相同,则称L1(I,J),L2(I,J)为正交广义全等和拉丁方。如图17(a)与图17(b)重叠,其所有序对如下:(1,1) (4,2) (1,4) (4,3) (2,4) (3,3) (2,1) (3,2) (4,1) (1,2) (4,4) (1,3) (3,4) (2,3) (3,1) (2,2)
3.2.1 n阶广义全等和拉丁方构成方法 n阶广义全等和拉丁方,可由n个相同的n=p1×P2长方基砖组合而成,方法如下: (1),将P2个长方基砖向上重叠,每砌一层向外伸出一列,见图 18 a.
(2),以最上一层长方基砖为基准取齐,成竖立长方块。见图 18 b.
(3),由p1个竖立长方块并排组合成广义全等和拉丁方L(I,J)。见图 18 c 例 n=2×4长方基砖组合成广义全等和拉丁方。如下:
|
1 |
2 |
7 |
8 |
|
|
|
|
1 |
2 |
7 |
8 |
|
1 |
2 |
7 |
8 |
1 |
2 |
7 |
8 |
|
3 |
4 |
5 |
6 |
|
|
|
3 |
4 |
5 |
6 |
3 |
4 |
5 |
6 |
3 |
4 |
5 |
6 |
||
|
|
1 |
2 |
7 |
8 |
|
|
8 |
1 |
2 |
7 |
8 |
1 |
2 |
7 |
8 |
1 |
2 |
7 |
||
|
|
3 |
4 |
5 |
6 |
|
|
6 |
3 |
4 |
5 |
6 |
3 |
4 |
5 |
6 |
3 |
4 |
5 |
||
|
|
|
1 |
2 |
7 |
8 |
|
7 |
8 |
1 |
2 |
7 |
8 |
1 |
2 |
7 |
8 |
1 |
2 |
||
|
|
|
3 |
4 |
5 |
6 |
|
5 |
6 |
3 |
4 |
5 |
6 |
3 |
4 |
5 |
6 |
3 |
4 |
||
|
|
|
|
1 |
2 |
7 |
8 |
2 |
7 |
8 |
1 |
2 |
7 |
8 |
1 |
2 |
7 |
8 |
1 |
||
|
|
|
|
3 |
4 |
5 |
6 |
4 |
5 |
6 |
3 |
4 |
5 |
6 |
3 |
4 |
5 |
6 |
3 |
a
b c图18
图`18(c)为广义全等和拉丁方。其特点: 1,任一行各数和均相等到,S=n×(n+1)/2,且任一行每个数重复出现p1次。 2,任一列各数是由1,2,3...n组成的一种排列,各数和S=n×(n+1)/2。 3,所有的左右泛对角线上各数均是由1,2,3...n组成的一种排列,各数和S=n×(n+1)/2。 4,该方阵与其转置方阵为正交方阵。即将该方阵J列,作为新方阵的I行。记为LT(I,J). 定理一:由n个长方基砖n=p1×P2组合而成的n阶方阵,若 : K1=K2×P2/(p1-1) K1= P2×(p1-K2)/(p1+1) 其中:K1=0,1,2...(P2-1),K2=0,1,2...( p1-1) K1,K2无同时为零的整数解,即P2与(p1+1),(p1-1)无公因子,则该方阵为广义全等和拉丁方(全等和幻基方)。 证明:(1)根据长方基砖定义,任一行各数和均相等,所以由长方基砖组合而成的n阶方阵任一行各数和均等于S=n×(n+1)/2。 (2)长方基砖组合的n阶方阵,任一列都是由1,2,3...n的一种排列,所以任一列各数和均相等。 S=n ×(n+1)/2。
(3)
现证明n阶方阵左,右泛对角线上的各数均是由1,2,3...n的一种排列。无重复数出现。 证明如下: 在n阶方阵左上角长方基砖内任取一数L(I1,J1),则该数在n阶方阵内共有n个。 其位置为L(I1+K1×p1 , J1+K1+ K2×P2)。与L(I1,J1)同在左泛对角线位置上的各数为: L(I1+L,J1+L)与L(I1,J1)同在右泛对角线位置上的各数为L(I1+L,J1+n-L)。 (注:从上 而下,从右至左的泛对角线为右泛对角线。从上而下,从左至右的泛对角线为左泛对角线。)(
i)若L(I1,J1)在左泛对角线上存在重复数,则有: L(I1+ K1×p1 , J1+K1+ K2×P2)=L(I1+L , J1+L) I1+ K1×p1=I1+L,J1+K1+ K2×P2=J1+L 解得:K1= K2×P2/(p1-1) ……(3.1) 其中K1=0,1,2...(P2-1),K2=0,1,2...( p1-1)(ii)
若L(I1,J1)在右泛对角线上存在重复数,则有: L(I1+ K1×p1,J1+K1+ K2×P2)=L(I1+L,J1+n-L) I1+ K1×p1=I1+L,J1+K1+ K2×P2=J1+ n-L 解得:K1=P2(p1-K2)/(p1+1) ...(3.2) 其中K1=0,1,2,3...( P2-1), K2=0,1,2…(p1-1) 若方程(3.1),(3,2)中K1 ,K2无同时为零的整数解,则说明与L(I1,J1)相同的其它数 L(I1+ K1×p1, J1+K1+ K2×P2), 都不在L(I1,J1)的左右对角线L(I1+L,J1+L), L(I1+l, J1+n-L)上。即在L(I1, J1) 的左,右泛对角线上无重复数出现。是由1,2,3…n的一种排列。其和S=n×(n+1)/2。 证毕。推论
1:n为奇数,由n=p1×P2长方基砖组合而成的n阶方阵, 当p1小于或等于P2中的最小素数,P2与(p1+1),(p1-1)无公约数,则K1,K2无同时为零的整数解,该方阵为n阶广义全等和拉丁方。 证明:(i)K1= K2×P2/(p1-1) (左泛对角线) K1=0,1,2…(P2-1), K2=0,1,2…(p1-1) 当K2=0 K1=0 当K2=p1-1时,K1=P2 与K1=0,1,2…(P2-1) 相矛盾,当K2<p1-1时,K2/(p1-1)<1,因p1小于或等于P2中最小素数,P2与(p1-1)无公约数。所以K1与K2 无不同时为零的整数解。则方阵左泛对角线上各数,不存在重复数。ii)K1=P2×(p1-K2)/(p1+1) (右泛对角线) K1=0,1,2…(P2-1), K2=0、1、2……(p1一1)。当取K2=p1-1时,K1=P2/(p1+1),因P2为奇数,(p1+1)为偶数,所以K1无整数解。 当取K2<p1-1时,(p1-K2)/(p1+1)<1为分数,且p1小于或等于P2中最小素数p1≠2, P2与(p1+1)不存在公约数。所以K1无整数解。即方阵右泛对角线上各数,不存在重复数,为1,2,3…n的一种排列。 由此看出当p1小于或等于P2中最小素数时,左右泛对角线上不存在重复数。该长方基砖组成的n 阶方阵为广义全等和拉丁方。 例:由n=3×5长方基砖组合的15阶方阵,其中:p1=3 , P2=5。 (i) 左泛对角线 K1=P2×K2/(p1-1)=5×K2/2, 其中:K1=0,1…(P2-1)=0,1,2,3,4 K2=0,1,2…(p1-1)=0,1,2 当取K2=0 ,则 K1=0 。 当取K2=1时 则 K1=5×K2/2=5/2 , 当取K2=2时 则K1=5 , 与K1=0,1,2,3,4矛盾。
(ii)右泛对角线 K1=P2×(p1-K2)/(p1+1)=5×(3-K2)/4。 当取K2=0 则 k1=15/4,当取K2=1时 ,则 K1=5×(3-1)/4=5/2, 当取K2=2时 ,则 K1=5×(3-2)/4=5/4。 以上得出K1, K2无同时为零的整数解。 推论2 当n为双偶数,由n=2×(2×P0)=2×P2,且P2不含3的因子时的长方基砖组成的n阶方阵为广义全等和拉丁方。 证明:(i)左泛对角线 K1= K2×P2/(p1-1)., 因p1=2 K1= K2×P2/(2-1)= K2×P2,其中K1=0,1,2…(P2-1),K2=0,1,2…(p1-1)=0, 1, 当取K2=0时,K1=0,当取K2=1时,K1=P2 与K1≤P2-1矛盾。
(ii)右泛对角线 K1=P2×(p1-K2)/(p1+1),其中K1=0,1,2…(P2-1), K2=0,1,2…(p1-1)=0,1。 已知 p1=2 K1=P2×(p1-K2)/(p1+1)=P2×(2-K2)/3, 当K2=0时, K1=2×P2/3。 当K2=1时, K1=P2×(2-1)/3=P2/3,已知P2不含3的因子,所以K1无整数解。 证毕。
3.2.2
由长方基砖组成的广义全等和拉丁方与其转置方阵成正交。n个长方基砖n=p1×P2组合的n阶方阵,若为广义全等和拉丁方,且P2与(p1+1),(p1-1)无公因子时,则该方阵与其转置方阵互为正交方阵。 证明:已知L(I,J)为广义全等和拉丁方,其转置方阵LT(J,I),仍然是广义全等和 拉丁方。 在原方阵L(I,J)的左上角n=p1×P2长方基砖内,任取一数L(I1,J1)。则与 L(I1,J1)n个相同数在L(I,J)方阵中位置分布为L(I1+ K1×p1, J1+K1+ K2×P2)。在其转置方阵内的位置分布为: LT(J1+K1+ K2×P2,I1+ K1×p1)。 将方阵L(I,J)与LT(J,I)叠加。若LT(J1+K1+ K2×P2,I1+ K1×p1) 与L(J1+K1+ K2×P2,I1+ K1×p1)一一对应。 若L(J1+K1+ K2×P2,I1+ K1×p1)上所有数都不相同。则认为L(I,J)与LT(J,I)重叠后,所有序对都不相同,则L(I,J)与LT(J,I)为正交方阵。 现证明原方阵L(I,J)在L(J1+K1+ K2×P2, I1+ K1×p1)上的所有数都不相同。 根据定理一,L(I,J)是由n个n=p1×P2长方基砖组合的广义全等和拉丁方。任一列上各数均是由1,2,3…n的一组排列,无重复数。因此当K1为一定时,不论K2取任何数, L(J1+K1+ K2×P2,I1+ K1×p1)在I1+K1×p1同一列上的数均不相同。 现证明当I1+ K1×p1互不相同,即不同列时,令K10≠K11时,L1(J1+K10+K2P2,I1+K10p1)与 L2(J1+K11+ K2×P2,I1+K11p1)所有数都不相同。 已知:L1(J1+K10+ K2×P2,I1+K10p1)与其相同的数在L(I,J)方阵中的位置为: L1[(J1+K10+ K2×P2)+K1′p1,(I1+K10p1)+K1′+K2′P2] 若L1[(J1+K10+ K2×P2)+K1′p1,(I1+K10p1)+K1′+K2′p2]中的所有数与 L2(J1+K11+ K2×P2,I1+K11p1)存在相同的数,则有: (J1+K10+ K2×P2)+K1′p1=J1+K11+ K2×P2 …(3.5) (I1+K10p1)+K1′+K2′P2=I1+K11p1 …(3.6) 其中K1′=0,1,2…(P2-1) K2′=0,1,2…(p1-1) 解得:K1′=K2′×P2/((p1+1)×(p1-1))。 已知 P2与(p1+1),(p1-1)无公因子,所以K1′与K2′无同时为零的整数解。 以上说明当K10≠K11即在不同列时,L1(J1+K10+ K2×P2,I1+K10p1)与 L2(J1+K11+ K2×P2,I1+K11P1)不存在相同的数。从而得出L(I,J)与LT(J,I)互为正 交 方 阵。定理二:由
推论3:由推论1,推论2所构成的广义全等和拉丁方与其转置方阵成正交方阵。