點線系統及其推廣

(玉溪師范學院 理學院,云南 玉溪 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.