點線系統(tǒng)及其推廣

(玉溪師范學(xué)院 理學(xué)院,云南 玉溪 653100)

英國數(shù)學(xué)家James Joseph Sylvester(1814～1897)的貢獻(xiàn)主要在代數(shù)學(xué)領(lǐng)域.他和Tibor Gallai一起發(fā)展了行列式理論,開創(chuàng)了代數(shù)型理論知識,是代數(shù)不變量理論的基礎(chǔ),他在數(shù)論方面的成就也很突出,尤其是整數(shù)的分拆和丟番圖分析方面.此外，他還創(chuàng)新出了許多的數(shù)學(xué)專業(yè)術(shù)語，如判別式、不變式、雅可比行列式等.他畢生從事于數(shù)學(xué)研究領(lǐng)域,發(fā)表了幾百篇論文,其中最著名的是《橢圓函數(shù)專論》.Sylvester同時也是《美國數(shù)學(xué)雜志》的開拓者,為美國的數(shù)學(xué)研究領(lǐng)域做出了巨大的貢獻(xiàn),曾經(jīng)有許多著名大學(xué)都授予了他崇高的名譽學(xué)位，如牛津,劍橋等,而且他還獲得過英國皇家勛章和科普利獎?wù)?

Sylvester是討論與直線有關(guān)問題最主要的一個數(shù)學(xué)家.1893年,Sylvester在《教育時報》的數(shù)學(xué)問題專欄中提出了一個幾何問題,即:證明不存在不在同一條直線上的有限點集，使得任意一條經(jīng)過其中兩點的直線都經(jīng)過第三個點.也許,在有關(guān)直線構(gòu)圖的問題中最著名的就是這個問題.

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

對于這個問題的證明,當(dāng)時Sylvester有沒有給出我們已無從知曉,也許他給出了正確的證明,可是最后沒有能保存下來.直到1933年,Karamate與Erdos重新提出了這個問題,Tibor Gallai才成功地給出了一個正確的證明,但其推導(dǎo)過程相當(dāng)?shù)膹?fù)雜.于是,下面定理以Sylvester和Gallai共同來命名.后來,對這一問題又出現(xiàn)了許多不同的證明方法,而L.M.Kelly的證明可能是其中最好的一個.

定理1(Sylvester-Gallai)[1]由平面上不共線的n個點所確定的直線中存在一條恰好經(jīng)過其中的兩個點.

用Sylvester-Gallai定理可以證明以下著名的Erdos-de Bruijn定理.為了給出這個定理以及一些后續(xù)的結(jié)論,我們先定義平面上n個點構(gòu)成的兩個特殊圖形(即NPn圖和Kn圖)如下,這兩個圖形在后文中將經(jīng)常用到.

圖1 NPn圖 圖2 Kn圖

定理2(Erdos-de Bruijn)[2]令P為平面上不共線的n≥3個點構(gòu)成的集合,則由穿過至少兩個點的直線組成的集合L中至少有n條直線.L中直線數(shù)取到最小值n的充要條件是P=NPn.

2 點線系統(tǒng)中的直線計數(shù)問題

Erdos-de Bruijn定理對我們研究點線系統(tǒng)的計數(shù)問題具有重要的啟示作用.在這一節(jié)中,筆者主要研究平面上n個點確定的直線數(shù)量問題.需要說明的是,在討論中,我們排除所有點共線這一平凡情形.

定義1 令Pn為平面上不共線的n個點構(gòu)成的集合,由穿過Pn中至少兩個點的直線的集合記為L(Pn),序?qū)?Pn,L(Pn))稱為Pn上的點線系統(tǒng),通常也記為Pn,(Pn,L(Pn))中所含直線的數(shù)量記為l(Pn).

以下討論l(Pn)的取值問題.

定義2 設(shè)Pn為平面上的n個點構(gòu)成的點線系統(tǒng),L∈L(Pn),若l中含有Pn中的k個點,則稱l為k點線.

以下定理給出了l(Pn)比較方便的計算公式:

定理4 設(shè)Pn為平面上不共線的n個點組成的點線系統(tǒng),sk表示Pn中k點線的條數(shù),k=3,4,5,…,n-1,則

設(shè)a是一個數(shù),X是一個數(shù)集,我們用a-X表示集合{a-x|x∈X}.則由以上推論得:

這個推論可使我們計算Ln的過程大大簡化.

證明由定理4知:

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

設(shè)m,n為整數(shù),m≤n,用[m,n]表示大于等于m小于等于n的整數(shù)組成的集合.則由定理5可知：

可是當(dāng)n=7時,出現(xiàn)了反例,此時8?L7!通過計算,我們有

可見隨著n的增大,這種反例越來越多.因此,對于一般的正整數(shù)n,如何確定Ln還是一個沒有解決的問題.

3 廣義點線系統(tǒng)與區(qū)組設(shè)計

以下我們對點線系統(tǒng)進(jìn)行推廣.

定義3 假設(shè)Pn為一個有n個元素的集合,L(Pn)={B1,…,Bm}是Pn的真子集組成的集合,其中Pn的每對元素剛好出現(xiàn)在一個Bi中.Pn中的元素稱為點,L(Pn)中的元素稱為線,序?qū)?Pn,L(Pn))稱為Pn上的廣義點線系統(tǒng),通常也記為Pn,(Pn,L(Pn))中所含線的數(shù)量記為l(Pn).

圖3 Fano平面

因為在歐氏幾何中,任意兩點決定一條直線.所以以上定義的廣義點線系統(tǒng)確實是點線系統(tǒng)的推廣.這種推廣是一個真推廣.事實上有許多廣義點線都不是點線系統(tǒng).例如,著名的Fano平面就是一個例子.Fano平面是一個有7個點的廣義點線系統(tǒng),其中點集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平面是一個廣義點線系統(tǒng),但不是點線系統(tǒng),因為它不滿足Sylvester-Gallai定理.

為了說明點線系統(tǒng)與區(qū)組設(shè)計的關(guān)系,我們以下對廣義點線系統(tǒng)進(jìn)行再推廣.

定義4 假設(shè)Pn為一個有n個元素的集合,L(Pn={B1,Bm})是Pn的真子集組成的集合,其中Pn的每對元素剛好出現(xiàn)在λ個Bi中.Pn中的元素稱為點,L(Pn)中的元素稱為線,序?qū)?Pn,L(Pn))稱為Pn上的λ-廣義點線系統(tǒng),通常也記為Pn,Pn中所含線的數(shù)量記為l(Pn).

由定義可知,廣義點線系統(tǒng)就是此處的1-廣義點線系統(tǒng).

以下給出均衡不完全的區(qū)組設(shè)計(Balanced Incomplete Block Design,縮寫是BIBD)的定義和一些基本性質(zhì).

定義5[3]設(shè)Pn={x1,x2,…,xn}為實驗對象的集合,n為實驗對象的數(shù)目.所謂參數(shù)為(m,n,r,k,λ)的均衡不完全的區(qū)組設(shè)計指的是由Pn中的真子集構(gòu)成區(qū)組的集合L(Pn)={B1,…,Bm},其中m為區(qū)組的數(shù)目,每個區(qū)組中有Pn的k個元素,并滿足以下條件:

(1)Pn中的每一個元素在m組中正好出現(xiàn)r次;

(2)任意一對屬于Pn的元素在m組中正好同時出現(xiàn)λ次.

滿足以上條件的均衡不完全的區(qū)組設(shè)計通常記為(m,n,r,k,λ)-設(shè)計.

附例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,此設(shè)計為(12,9,4,3,1)-設(shè)計.

定義6[3]設(shè)(Pn,L(Pn))是一個區(qū)組設(shè)計,其中Pn={x1,x2,…,xn},L(Pn)={B1,…,Bm}.則此區(qū)組設(shè)計的區(qū)組矩陣A=(aij)n×m定義為

如附例的區(qū)組矩陣為:

定理6[3](m,n,r,k,λ)-設(shè)計滿足以下條件:

(1)mk=nr;

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

定理7[3]對于(m,n,r,k,λ)-設(shè)計,以下等式成立:

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

其中是I的單位矩陣,J是所有元素均為1的n×n矩陣.

定理8[3]在(m,n,r,k,λ)-設(shè)計中,m≥n恒成立.

由區(qū)組設(shè)計的定義可知,(m,n,r,k,λ)-設(shè)計是一種特殊的λ-廣義點線系統(tǒng).因此,定理6,7,8應(yīng)該可以在λ-廣義點線系統(tǒng)中進(jìn)行推廣.以下我們對此進(jìn)行研究.首先給出定理6的推廣.

定理9 設(shè)(Pn,L(Pn))是一個λ-廣義點線系統(tǒng),其中Pn={x1,x2,…,xn},L(Pn)={B1,…,Bm}.用ri表示包含點xi的線的條數(shù).則:

證明(1)此等式左邊是點線系統(tǒng)中每條線上的點數(shù)之和.在這個計數(shù)過程中,點xi被重復(fù)計數(shù)了ri次,i=1,2,…,n.因此等式成立.

(2)設(shè)xi∈B,則|B-1|表示B中所含的除了xi以外的其他點的個數(shù).因此,此等式左邊計數(shù)的是包含xi的所有線上除了xi以外的其他點的總數(shù).由λ-廣義點線系統(tǒng)的定義,對于任意xj≠xi,同時包含xi與xj的線共有λ條,因此,包含xi的所有線上除了xi以外的其他點的總數(shù)為λ(n-1).即等式成立.

以下定理推廣了定理7.

定理10 沿用定理9的記號,則有:

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

其中矩陣A的定義類似于區(qū)組矩陣(見定義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 設(shè)(Pn,L(Pn))是一個λ-廣義點線系統(tǒng),n≥3,m=|L(Pn)|.則m≥n.

證明沿用定理10的記號,則有

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

由λ-廣義點線系統(tǒng)的定義有ri>λ,i=1,2,…,n.因為矩陣diag(r1-λ,r2-λ,…,rn-λ)只有正的特征值,所以它是正定矩陣.而矩陣λJ的特征值是n和0,所以它是半正定矩陣.所以AAT是正定的,從而它是可逆的.于是r(AAT)=n.從而矩陣r(A)≥n.又由于秩不會超過矩陣A的列數(shù)m,故m≥n.

關(guān)于點線系統(tǒng)的定理4及其推論與定理5都可以推廣到λ-廣義點線系統(tǒng)中,且證明類似,我們在此就不詳細(xì)討論了.

定義7 兩個點線系統(tǒng)(或λ-廣義點線系統(tǒng))(Pn,L(Pn))和(Qn,L(Qn))稱為同構(gòu)的,若存在從Pn到Qn上的雙射φ滿足:對于任意B∈L(Pn),φ(B)∈L(Qn).

顯然,同構(gòu)的點線系統(tǒng)具有相同的點數(shù)和線數(shù).但是,具有相同點數(shù)和線數(shù)的點線系統(tǒng)卻不一定同構(gòu).例如,點數(shù)n=6,線數(shù)m=11的點線系統(tǒng)就有兩個不同構(gòu)的類型,見圖4.

圖4 點數(shù)n=6,線數(shù)m=11的點線系統(tǒng)

隨著點、線數(shù)的增加,這種例子將會越來越多.對于一般的n和m,點數(shù)為n線數(shù)為m的點線系統(tǒng)共有多少個互不同構(gòu)的類型?這個問題遠(yuǎn)未解決,應(yīng)該也是一個很難的問題.

事實上,同構(gòu)的點線系統(tǒng)不僅具有相同的點數(shù)和線數(shù),對于任意正整數(shù)k,它們還具有相同數(shù)量的k點線.但是,反過來,這些指標(biāo)完全相同的點線系統(tǒng)也不一定同構(gòu).如何有效判定兩個點線系統(tǒng)同構(gòu)?對于任意正整數(shù)k,所有k點線數(shù)量完全相同的點線系統(tǒng)共有多少同構(gòu)類?這些問題也都沒有解決.

[1]Aigner,M.,Ziegler,G.M.數(shù)學(xué)天書中的證明:第3版[M].馮榮權(quán),宋春偉,宗傳明,譯.北京:高等教育出版社，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]盧開澄.盧華明.組合數(shù)學(xué)：第3版[M].北京:清華大學(xué)出版社，2002:45-62.