点线系统及其推广

(玉溪师范学院 理学院,云南 玉溪 653100)

英国数学家James Joseph Sylvester(1814～1897)的贡献主要在代数学领域.他和Tibor Gallai一起发展了行列式理论,开创了代数型理论知识,是代数不变量理论的基础,他在数论方面的成就也很突出,尤其是整数的分拆和丢番图分析方面.此外，他还创新出了许多的数学专业术语，如判别式、不变式、雅可比行列式等.他毕生从事于数学研究领域,发表了几百篇论文,其中最著名的是《椭圆函数专论》.Sylvester同时也是《美国数学杂志》的开拓者,为美国的数学研究领域做出了巨大的贡献,曾经有许多著名大学都授予了他崇高的名誉学位，如牛津,剑桥等,而且他还获得过英国皇家勋章和科普利奖章.

Sylvester是讨论与直线有关问题最主要的一个数学家.1893年,Sylvester在《教育时报》的数学问题专栏中提出了一个几何问题,即:证明不存在不在同一条直线上的有限点集，使得任意一条经过其中两点的直线都经过第三个点.也许,在有关直线构图的问题中最著名的就是这个问题.

1 Sylvester-Gallai定理与Erdos-de Bruijn定理

对于这个问题的证明,当时Sylvester有没有给出我们已无从知晓,也许他给出了正确的证明,可是最后没有能保存下来.直到1933年,Karamate与Erdos重新提出了这个问题,Tibor Gallai才成功地给出了一个正确的证明,但其推导过程相当的复杂.于是,下面定理以Sylvester和Gallai共同来命名.后来,对这一问题又出现了许多不同的证明方法,而L.M.Kelly的证明可能是其中最好的一个.

定理1(Sylvester-Gallai)[1]由平面上不共线的n个点所确定的直线中存在一条恰好经过其中的两个点.

用Sylvester-Gallai定理可以证明以下著名的Erdos-de Bruijn定理.为了给出这个定理以及一些后续的结论,我们先定义平面上n个点构成的两个特殊图形(即NPn图和Kn图)如下,这两个图形在后文中将经常用到.

图1 NPn图 图2 Kn图

定理2(Erdos-de Bruijn)[2]令P为平面上不共线的n≥3个点构成的集合,则由穿过至少两个点的直线组成的集合L中至少有n条直线.L中直线数取到最小值n的充要条件是P=NPn.

2 点线系统中的直线计数问题

Erdos-de Bruijn定理对我们研究点线系统的计数问题具有重要的启示作用.在这一节中,笔者主要研究平面上n个点确定的直线数量问题.需要说明的是,在讨论中,我们排除所有点共线这一平凡情形.

定义1 令Pn为平面上不共线的n个点构成的集合,由穿过Pn中至少两个点的直线的集合记为L(Pn),序对(Pn,L(Pn))称为Pn上的点线系统,通常也记为Pn,(Pn,L(Pn))中所含直线的数量记为l(Pn).

以下讨论l(Pn)的取值问题.

定义2 设Pn为平面上的n个点构成的点线系统,L∈L(Pn),若l中含有Pn中的k个点,则称l为k点线.

以下定理给出了l(Pn)比较方便的计算公式:

定理4 设Pn为平面上不共线的n个点组成的点线系统,sk表示Pn中k点线的条数,k=3,4,5,…,n-1,则

设a是一个数,X是一个数集,我们用a-X表示集合{a-x|x∈X}.则由以上推论得:

这个推论可使我们计算Ln的过程大大简化.

证明由定理4知:

(5)其他情形,l(Pn)>5.

设m,n为整数,m≤n,用[m,n]表示大于等于m小于等于n的整数组成的集合.则由定理5可知：

可是当n=7时,出现了反例,此时8∉L7!通过计算,我们有

可见随着n的增大,这种反例越来越多.因此,对于一般的正整数n,如何确定Ln还是一个没有解决的问题.

3 广义点线系统与区组设计

以下我们对点线系统进行推广.

定义3 假设Pn为一个有n个元素的集合,L(Pn)={B1,…,Bm}是Pn的真子集组成的集合,其中Pn的每对元素刚好出现在一个Bi中.Pn中的元素称为点,L(Pn)中的元素称为线,序对(Pn,L(Pn))称为Pn上的广义点线系统,通常也记为Pn,(Pn,L(Pn))中所含线的数量记为l(Pn).

图3 Fano平面

因为在欧氏几何中,任意两点决定一条直线.所以以上定义的广义点线系统确实是点线系统的推广.这种推广是一个真推广.事实上有许多广义点线都不是点线系统.例如,著名的Fano平面就是一个例子.Fano平面是一个有7个点的广义点线系统,其中点集P={1,2,3,4,5,6,7}(见图3),线集

L(P)={{1,2,6},{1,3,5},{1,4,7},{2,3,4},{2,5,7},{3,6,7},{4,5,6}}.

易见,Fano平面是一个广义点线系统,但不是点线系统,因为它不满足Sylvester-Gallai定理.

为了说明点线系统与区组设计的关系,我们以下对广义点线系统进行再推广.

定义4 假设Pn为一个有n个元素的集合,L(Pn={B1,Bm})是Pn的真子集组成的集合,其中Pn的每对元素刚好出现在λ个Bi中.Pn中的元素称为点,L(Pn)中的元素称为线,序对(Pn,L(Pn))称为Pn上的λ-广义点线系统,通常也记为Pn,Pn中所含线的数量记为l(Pn).

由定义可知,广义点线系统就是此处的1-广义点线系统.

以下给出均衡不完全的区组设计(Balanced Incomplete Block Design,缩写是BIBD)的定义和一些基本性质.

定义5[3]设Pn={x1,x2,…,xn}为实验对象的集合,n为实验对象的数目.所谓参数为(m,n,r,k,λ)的均衡不完全的区组设计指的是由Pn中的真子集构成区组的集合L(Pn)={B1,…,Bm},其中m为区组的数目,每个区组中有Pn的k个元素,并满足以下条件:

(1)Pn中的每一个元素在m组中正好出现r次;

(2)任意一对属于Pn的元素在m组中正好同时出现λ次.

满足以上条件的均衡不完全的区组设计通常记为(m,n,r,k,λ)-设计.

附例Pn={x1,x2,x3，x4,…,x9},

B1:x1,x2,x3;B2:x4,x5,x6;B3:x7,x8,x9;B4:x1,x4,x7;

B5:x2,x5,x8;B6:x3,x6,x9;B7:x1,x5,x9;B8:x2,x6,x7;

B9:x3,x4,x8;B10:x1,x6,x8;B11:x2,x4,x9;B12:x3,x5,x7.

于是m=12,k=3,r=4,λ=1,n=9,此设计为(12,9,4,3,1)-设计.

定义6[3]设(Pn,L(Pn))是一个区组设计,其中Pn={x1,x2,…,xn},L(Pn)={B1,…,Bm}.则此区组设计的区组矩阵A=(aij)n×m定义为

如附例的区组矩阵为:

定理6[3](m,n,r,k,λ)-设计满足以下条件:

(1)mk=nr;

(2)r(k-1)=λ(n-1).

定理7[3]对于(m,n,r,k,λ)-设计,以下等式成立:

AAT=(r-λ)I+λJ,

其中是I的单位矩阵,J是所有元素均为1的n×n矩阵.

定理8[3]在(m,n,r,k,λ)-设计中,m≥n恒成立.

由区组设计的定义可知,(m,n,r,k,λ)-设计是一种特殊的λ-广义点线系统.因此,定理6,7,8应该可以在λ-广义点线系统中进行推广.以下我们对此进行研究.首先给出定理6的推广.

定理9 设(Pn,L(Pn))是一个λ-广义点线系统,其中Pn={x1,x2,…,xn},L(Pn)={B1,…,Bm}.用ri表示包含点xi的线的条数.则:

证明(1)此等式左边是点线系统中每条线上的点数之和.在这个计数过程中,点xi被重复计数了ri次,i=1,2,…,n.因此等式成立.

(2)设xi∈B,则|B-1|表示B中所含的除了xi以外的其他点的个数.因此,此等式左边计数的是包含xi的所有线上除了xi以外的其他点的总数.由λ-广义点线系统的定义,对于任意xj≠xi,同时包含xi与xj的线共有λ条,因此,包含xi的所有线上除了xi以外的其他点的总数为λ(n-1).即等式成立.

以下定理推广了定理7.

定理10 沿用定理9的记号,则有:

AAT=diag(r1-λ,r2-λ,…,rn-λ)+λJ,

其中矩阵A的定义类似于区组矩阵(见定义6),diag(r1-λ,r2-λ,…,rn-λ)是以向量(r1-λ,r2-λ,…,rn-λ)为对角线的对角矩阵,J是所有元素均为1的n×n矩阵.

证明对于任意i,j=1,2,…,n,若i=j,则包含xi的线共有ri条,因此,(AAT)ii=ri;若i≠j,则同时包含xi与xj的线共有λ条,因此有(AAT)ij=λ.所以,

以下定理是Erdos-de Brujin定理的推广,也是定理8的推广.

定理11 设(Pn,L(Pn))是一个λ-广义点线系统,n≥3,m=|L(Pn)|.则m≥n.

证明沿用定理10的记号,则有

AAT=diag(r1-λ,r2-λ,…,rn-λ)+λJ.

由λ-广义点线系统的定义有ri>λ,i=1,2,…,n.因为矩阵diag(r1-λ,r2-λ,…,rn-λ)只有正的特征值,所以它是正定矩阵.而矩阵λJ的特征值是n和0,所以它是半正定矩阵.所以AAT是正定的,从而它是可逆的.于是r(AAT)=n.从而矩阵r(A)≥n.又由于秩不会超过矩阵A的列数m,故m≥n.

关于点线系统的定理4及其推论与定理5都可以推广到λ-广义点线系统中,且证明类似,我们在此就不详细讨论了.

定义7 两个点线系统(或λ-广义点线系统)(Pn,L(Pn))和(Qn,L(Qn))称为同构的,若存在从Pn到Qn上的双射φ满足:对于任意B∈L(Pn),φ(B)∈L(Qn).

显然,同构的点线系统具有相同的点数和线数.但是,具有相同点数和线数的点线系统却不一定同构.例如,点数n=6,线数m=11的点线系统就有两个不同构的类型,见图4.

图4 点数n=6,线数m=11的点线系统

随着点、线数的增加,这种例子将会越来越多.对于一般的n和m,点数为n线数为m的点线系统共有多少个互不同构的类型?这个问题远未解决,应该也是一个很难的问题.

事实上,同构的点线系统不仅具有相同的点数和线数,对于任意正整数k,它们还具有相同数量的k点线.但是,反过来,这些指标完全相同的点线系统也不一定同构.如何有效判定两个点线系统同构?对于任意正整数k,所有k点线数量完全相同的点线系统共有多少同构类?这些问题也都没有解决.

[1]Aigner,M.,Ziegler,G.M.数学天书中的证明:第3版[M].冯荣权,宋春伟,宗传明,译.北京:高等教育出版社，2009:21-33.

[2]De Bruijn-Erdös theorem (incidence geometry)[EB/OL].http://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(incidence_geometry).

[3]卢开澄.卢华明.组合数学：第3版[M].北京:清华大学出版社，2002:45-62.