（基础数学专业论文）线图的基数及最小公倍数幂矩阵的可逆性.pdf

全文由两部分组成。 摘要 第一部分讨论了线图的基数。假设g 是一个图，任给图g 的圈空 间的一组基，如果g 中每条边至多在这组基的h 个圈中出现，那么称 这组基是h 重的。把使g 的圈空间有h 重基的最小非负整数h 称为g 的基数，用b ( g ) 表示。在这一部分中，我们求出了一些特殊图类的线 图的基数，同时证明了对于一般的图而言，b ( l ( g ) ) b ( g ) f 3 。 第二部分讨论了最小公倍数幂矩阵的可逆性。设s = f x 。，x ：，x 。 是互异的正整数集合。m 是一个正实数，将1 2 n 阶矩阵 s = ( c x 。，x j 。) 称为集s 上的最小公倍数幂矩阵，其中e x 。x 表示x 和x ，的最小公倍 数。当m = l 时，关于最小公倍数矩阵 s 的可逆性的讨论已经比较充 分了。在这一部分中，我们证明了当m 2 且n 9 时，最大公因子封 闭集合s 上的最小公倍数幂矩阵 s i 是可逆的。 关键词：圈空间，基数，线图； 最大公因子封闭集合，最小公倍数幂矩阵，可逆性。 a b s t r c t t h ep a p e ri sm a d eu po ft w op a r t s i nt h ef i r s tp a r t ，w ed i s c u s st h eb a s i sn u m b e ro ft h el i n e g r a p ho fag r a p h 。ab a s i so ft h ec y c l es p a c e 中( g ) o fag r a p h gi sh f 0 1 di fe a c he d g eo fgo c c u r si na tm o s thc y c l e so ft h e b a s i s 。t h eb a s i sn u m b e rb ( g ) o fgi st h el e a s t i n t e g e rhs u c h t h a to ( g ) h a sa nh f o l db a s i s i nt h i sp a r tw eg e tt h eb a s i s n u m b e ro fli n eg r a p hl ( g ) o fs o m e s p e c i a lg r a p h s e n dw es h o w t h a tl e tgb eag r a p h ，b ( l ( g ) ) b ( g ) + 3 i nt h es e c o n dp a r t ，w ed i s c u s st h e i n v e r t i b i l i t yo fl c m p o w e rm a t r i c e s l e ts = x 【，x 2 ，x 。 b eas e to fd i s t i n c tp o s i t i r e i n t e g e r s a n dmb e p o s i t i v e r e a ln u m b e r t h enxnm a t r i x s = ( x i ，x ， 。) i sc a l l e dt h el c mp o w e rm a t r i xo ns ，w h e r e x i ，x j i st h el e a s tc o m m o nm u l t i p l eo fx 。a n dx j f o rr e = l , t h ed e t e r m i n a n t a n di n v e r t i b i l i t yo fl c mm a t r i xi s a r ed i s c u s s e de x t e n s i v e l y t h em a i nr e s u l to ft h i sp a r ti st os h o wt h a tw h e nm 2a n dn 9 ，t h e l c m p o w e r m a t r i c e si s o nag c d c l o s e ds e ti s i n v e r t i b l e k e yw o r d s ：c y c l es p a c e ，t h eb a s i sm u m b e r ，l i n eg r a p h ： g c d c l o s e ds e t ，l c mp o w e rm a t r i x ，i n v e r t i b i l i t y f f 第一章线图的基数 1 1 引言及综述 对图的几何结构和代数特征的研究，已经有了悠久的历史。现 在我们利用图的圈空间的性质，得到一种研究图的代数特征的方法。 假设g 是一个简单、无向的有限图，分别用集合v = v 。，v ：， v ，) 和e = e - ，e z ，e 。) 表示g 的顶点集和边集。对于e 的任何子集s ， 我们可以用一个( o ，1 ) 向量( a 。a 。，a q ) ( z ：) 4 来表示。若e 。s ， 则a i 一1 ；否则a i - o 。于是g 中每一个圈都对应了一个( 0 ，1 ) 向量，把 由g 中每个圈对应的向量生成的向量空问称为g 的圈空间，记作由 ( g ) 。易见由( g ) 是( z 。) 4 的一个子空问。通常我们说士( g ) 的元素是g 中的圈，而不再说是某个圈所对应的向量。 我们已经知道如果g 是连通图，那么由( g ) 的维数是q p + 1 ，其 中p 和q 分别是g 的顶点数和边数。事实上我们可以很自然的构造 g 的圈空间的一组基。因为对于g 的一棵生成树t ，可以添加一条边 e ( e 诺t ) 得到子图t + e ，易知t + e 恰包含g 的一个圈c 。，于是所有这 些圈的全体 c 。ie 蓝t ) 构成了由( g ) 的一组基，将它称为相应于生成树 t 的基本基。不难发现，不在t 上的每条边在这组基中恰好出现一 次，而t 上的每条边在这组基中出现若干次。这一事实使我们对于 g 的每条边在由( g ) 的一组基中的几个圈中出现的研究变得有意义， 从而得到了研究图的代数特征的一个重要方向。 设b 是由( g ) 的任意一组基，h 是一个非负整数。如果g 中每条 边至多在b 中的h 个圈中出现，那么称b 是h 重的。进一步，把使 由( g ) 有h 重基的最小非负整数h 称为g 的基数，记作b ( g ) 。 关于图的基数的讨论最早开始于1 9 3 7 年。m a c l a n e 在 4 中证 明了平面图的充要条件是b ( g ) 2 。这给出了图的平面性的一个重 要代数特征。 在随后的研究中( 5 卜 1 5 ) ，越来越多的具有特殊结构的图的 基数被人们确定下来。 1 9 8 1 年s c h m e i c h e l 在 5 中证明了当n 3 时，完全图k 的基 数b ( k 。) 3 ；以及当n 、m 5 时，完全二部图l ( - ，。的基数b ( i 【i 。) 4 ， 除了l ( 6 。、l ( 5 。和艮。( 其中n = 5 、6 、7 、8 ) 。直到2 0 0 3 年a 卜s a r d a r y 和a l i 在 7 中才完成了对i ( 5 ，。和i ( 6 。的讨论，证明了 b ( 1 ( 5 。) = b ( 1 ( d ) = 3 ( 其中n = 5 、6 。7 、8 ) ，同时还求出了当r = 5 、6 、7 、 8 时，r 一笼图的基数。 1 9 8 2 年b a n k s 和s c h m e i c h e l 在 6 中证明了当n 7 时，i 1 维方 体瓯的基数b ( q n ) = 4 。因为q n 可以看成二阶完全图k 2 的幂图， a i - s a r d a r y 开始研究完全图幂图的基数，他在 1 3 】中证明了当n 2 且d l 时，b ( 科) 9 。 从1 9 8 9 年开始，在以a l l 为代表的研究学者们的共同努力下， 一大批有关图的基数的成果涌现出来。在 9 中他证明了当m 3 时， 完全多部图l 【的基数b ( 1 ( 如，) 9 ，以及完全三部图k 、，。的基数 b ( k 。) 4 。此外还求出了在一些特殊图类之间进行笛卡尔积运算 后的基数。更重要的是在 1 1 中他和m a r o u q i 证明了下面这个结论： 引理1 1 设g 和h 是两个连通图，则： b ( g xh ) 1 时，完全二部图k ，。的线图基数不大于5 证明：我们已知：l ( i ( - ，。) = k k ，而且b ( 1 ( i ) = b ( k 。) 3 。完全 图有h a m i t o n 路，选出l 【和k n 的h a m i t o n 路l l 和l 。，作为各自的 生成树，于是( l 。) = ( l ：) = 2 。 由引理1 1 得：b ( l ( 1 ( - 。) ) = b ( 1 【- k ) m a x b ( 1 ( i ) + a ( l 。) ， b ( k 。) + a ( l 1 ) ) 3 + 2 = 5 。口 引理i 4 完全图的线图中每个无弦4 一圈或5 一圈都可以在模2 的前提下表示成一些3 - m 的和 证明：任取l ( k 。) 的一个无弦4 一圈 i ，j ) i ，k ) ( k ，1 ) j ，1 ( i ，j ) ， 利用第5 个点f j jk ，我们可以得到： i ，j i ，k k ，1 j ，1 ) i ，j 一 i ，j ) ( j ，1 ) j ，k ) f i ，j ) + ( i ，j i ，k ) j ，k ) i ，j ) + j ，k ( k ，1 ) j ，1 ) j ，k ) + i ，k ) j ，k ) k ，1 ) i ，k ( m o d2 ) 。 任取l ( k 。) 的一个无弦5 一圈( i ，j i ，x ) f x ，1 ) k ，1 ) j ，k ( i ，j ， 利用两个点( i ，k ) 和 k ，x ，我们可以得到： i ，j i ，x ) f x ，1 ) k ，1 ) j ，k ) i ，j ) 暮 i ，j ) i ，x ) i ，k ) i ，j ) + i ，j ) i ，k ) j ，k ) i ，j ) + j ，k ) ( i ，k ) k ，x ) k ，j ) + i ，k ) i ，x ) k ，x ) i ，k ) + j ，k ) k ，x ) k ，1 ) k ，j ) + x ，k ) k ，1 ) l ，x ) x ，k ) + x ，k i ，x ) f x ，1 ) f x ，k )( m o d2 ) 。 于是完成了引理1 4 的证明。 口 为了得到引理1 5 ，我们先来做一些准备工作。 任给整数i = 0 、1 、n 1 ，用j ；表示由点集“i ，a ) l a z 。且 a i ) 生成的l ( k ) 的子图。易见j ；与i ( n 一。同构。已知b ( j i ) = b ( 1 ( 口一。) 4 3 ，选出每个j ；的一个三重基d 。，构造酣”一- - u n 。- i d t 。同时，构造： & 2 ) _ “a ，b ) b ，c ) c ，a f a ，b ) ia + b + c - - - - 0 、l 、或2 ( m o dn ) 。作 b n b 。”u b 。( 2 ) o 将形如 i ，a ) i ，b ) ( i ，c i ，a ) 的3 一圈称为一型3 一圈；将形如 f a ，b ) b ，c ) a ，c ) a ，b ) 的3 一圈称为二型3 一圈。对于x 、y z 。，如 果jx y l 兰l 或n l ( m o dn ) ，那么称x 与y 是相邻的。 引理1 5 当n 4 时，在l ( i ) 中任意二型3 一圈都可以用b n 中 的3 一圈表示 证明：任意取出l 憾) 中的一个二型3 一圈：c = a ，b ) b ，c c ，a ( a ，b ) 。不妨假设a b c 并且a + b + c - - r ( m o dn ) ，则1 r n 一1 ， 下面我们对r 使用数学归纳法。 当r = 0 、1 、2 时，易见c e b 。； 假设c = a 7 ，b b ，c7 ) c ，a 7 ) a ，b7 ) 其中a + b + c7 兰k ( m o dn ) ( 0 k o ，则f s - 】均可逆 这个猜想具有相当的概括性和深刻性，弓l 起了研究者的广泛兴 ；趣。当平r 对。疟就是猜想：2 1 ，! 已经知道它是不成立的：当m 1 时，有关猜想2 2 的讨论还在进行中。在这一部分里，我们完成了 它的一小部分证瞻，即证明了：当m 2 且n 9 时，最大公因子封 闭集合s 上的最小公倍数幂矩阵 s 。 都是可逆的。但是，有关猜想 2 2 的正确性的研究远没有结束，值得我们进行更深入细致的探讨。 2 2 预备定理 将定义在正整数集上的复值函数称为算术函数，记作f ( x ) 。将 n n 阶矩阵( s f ) = ( a ) 称为最大公因子函数矩阵，其中a = f ( ( x t ，x ，) ) 。当r f ( x ) = x 时，有( s ，) = ( s ) ，即前面提到的最大公因子 矩阵( g c 矽矩阵) ；当f ( x ) = 吉时，有x ( s r ) x = s ，即前面提到的最 小公倍数幂矩阵，1 这里x = d 呈8 9 ( x 。，x z - ，x 。) 。 注设s ：k ，x ：，x 。 是最大公因子封闭集合且x 。 x ： x 。 1 。x 。f x ；( 1 i n 一1 ) ，d e t s = x 。”d e t s 。- ，其中s l = 丑，量，鱼，1 ) 。于是我们仅研究包含元素l 的最大公因子封 x -x nx “ ：闭集合。 在以下的讨论中我仃j 假设f ( x ) = 去且m l 。 王 引理2 1 ( 1 7 】) 设s = f x 。，x 。，x 。) 是最大公因子封闭集合且 x 。 x 。 x 。，则d e t s i = n 一x i “口( x 。) ，其中口( x ；) = f ( x i ) 一 f ( ( x ；，x 。) ，( x “x ；+ ：) ，( x 。，x n ) ) ( 1 i n ) ，f ( y 。，y 2 ，y k ) 是由f ( x ) 递归定义出的多元扩张函数，即f ( 乳，y z ，y t ) = 裂( - 1 ) “1 嘲q 。嘲。，( 以，托，乩) ( k 1 ) 。 引理2 2 ( 【1 7 】) 设y ，、y ：、y k ( k 2 ) 都是正整数，则 f ( y l ，y 2 ，y k ) = f ( y 。，y 。，y t t ) + f ( y k ) 一( ( y ，y k ) ，( y2 ，y 。) ，( y k 一。，y 。) ) 。 引理2 3 ( 1 7 】) 设y 。、y 。、y 。( k 2 ) 都是正整数，若存在 i k ，使得y 。y ；，贝0f ( y ，y 。，y 。) = f ( y ，y z ，y 。一。) 。 特另4 的，f ( y ，y ；，y 。) = f ( y 。) ， f ( y i ，y 2 ，y k 1 ) = f ( y ，y 2 ，y k ) 。 引理2 4 设y 。、y ：是两个正整数，而且满足y 。不整除y ：且y ： 不整除y ，更4f ( y t ，y 2 ) o 。 证明：对m 使用数学归纳法。 当m = l 时，由 1 7 知f ( y ，y 。) 0 ； 当m 2 时，假设对于f ( x ) = 七，有f ( y ，y z ) 志+ 志。 对m 的情形有f ( y 。，y 。) = f ( y 。) + f ( y ：) 一f ( ( y 。，y 2 ) ) 。嘉+ 嘉一瓦 嘉+ 专一c 志+ 志，y l ”y 2 “( y 1 ，y 2 ) 。_ ) ，l 。y 2 ”y 1 册- 1 ( y i ，y 2 ) ，2 伊1 瓴，y 2 ) 2 寿c 击一击卜寿c 击一南， - n 不整除y 2 且y ：不整除y 。f ( y 。，y z ) 2 ) 都是不小于2 的正整数，如 果它们两两互素，那么f ( y 。，y 2 ，y j o 证明：对k 使用数学归纳法。 当k = 2 时，( y i ，y 。) = l ，由引理2 4 有f ( y t ，y z ) 0 。 假设k 一1 时结论成立，即f ( y ：，) r z ，y “) 0 。 对k 的情形：f ( y ，y z ，y t ) = f 0 。，y 2 ，y 。，) + f ( y t ) 一f ( ( y t ，y x ) ，( y 孙y * ) ，( y t t ，y t ) ) 二y t 、y 2 、y k 两两互素，( y ；，y 。) = 1 ( 其中i j ) 。 f ( y i ，y 2 ，y k ) = f ( y - ，y 。，y - 一- ) + f ( y t ) 一f ( 1 ，1 ，1 ) = f ( y 。，y 。，y k - 。) + f ( y t ) 一f ( 1 ) 。 f ( n ) 一f ( 1 ) o 且f ( y 。y ：，y h ) x ， l ，则除了二十个集合以外，其它的 s 都是可逆的。 2 3 主要结论 在以下的讨论中我们总是假设f ( x ) = 且m 2 。 x 定理2 8 设s = ( x ，x n ) 是最大公因子封闭的互异正整数集 合，当n x 。 工， l ，。射【s - 是可逆的 证明：反设存在一个满足条件的集合s ，使得 s - 不可逆。由引 理2 1 ：和定理2 8 ，有： 弘( x 。) = f ( x 。) 一f ( ( x 。，】【：) ，( 】【。，】【。) ，( x l ，x ，) ，1 ) ：o 。s 是最大 公因子封闭集合，j 。由引理2 3 存在y ，、y ：、y ，e s ，( 1 p 6 ， 2 y t x 。i 而且当i j 时，y 。不整除) r j ) ，使得： 口( x 。) = f ( x ；) 一f ( y ；，y ：，y ，) = o ( 2 一1 ) 1 ( 1 ) 当p = 1 时，y l x - ，口( x - ) = f ( x t ) 一f ( y i ) = 七一之 o ，与( 2 1 ) 矛盾。 ( 4 ) 当p = 5 时，设s = f x - ，y z ，y ：，y 。，t 。1 ) 。易见当i j 时， ( y ；，y j ) = t t 亘览l 。由弓怔匪2 2 有f ( y 。，y 2 ，y 。) = f ( y 。，y 。，y 。) + f ( y ；) 一f ( a s ) ，这里a 5 = t 。或1 ，并且a 5 y 。如此继续下去，我们得到 f ( n ，y z ，y s ) = f ( y 。，y 。) + f ( y 。) 一f ( a 3 ) + f ( ) r 。) 一f ( a 4 ) + f ( y ；) 一 f ( a 5 ) ，这里a 。 t 。， 我们分三种情况来讨论。 若( y 。，y ，y 。，y 。) = t 。，则当i j 时，有( y ，y ) = t 。，则 ( 丝，笠) = l 。由引理2 5 有( y ，) r 。，y 。) = f ( 旦，丝，丝，丛) o ，与( 2 1 ) 矛盾。 若( y l y 。，y 。) = t ：，则当i j 时，有( ) r ；，y j ) = t 。或t 。 - ( y l ，y ：，y a ，y ，) j ( y 。，y ) ，t 。h ，存在b ；= t 或t 2 ，并且b 。 y 。，使 得f ( y 。，y ：，y s ，y 。) = f ( y 。，) r ：，y 。) + f ( y 。) 一f ( b 。) 。类似的，存在b 。 y 3 满足f ( y “y z ，y 3 y ，) = f ( 。，y z ) + f ( y ；) 一f ( b 。) + f ( y 。) 一f ( b 0 o ，与( 2 1 ) 矛盾。 若( y ，y 。，y 。，y 。) = 1 ，则一定存在某个y 。例如y 满足：t 。不整除 y 。因此存在c = t z 且c 。 y 4 ，使得f ( y i ，y 。，y 3 ，3 r 4 ) = f ( y 1 ，y 2 ，y 。) + f ( y 。) 一f ( c ) 。不失一般性，我们假设( y 。，y 。) ( y 。，y 。) ( y 。，y 。) ，于是 ( y l y 。) = ( y z ，y 。) 或者( y ：，y 。) = 1 。这时存在c 3 一t ，或t ：或1 ，而且c 。 y 。，满足f ( y ，y 。y 3 y ；) = f ( y 。，y z ) + f ( y 。) 一f ( c 。) + f ( y 。) 一f ( c ) o ，与( 2 1 ) 矛盾。 ( 6 ) 当p = 3 时，设s = x 。，y l y 。，y 3 ，t 。，t ：，t 3 l 。如果存在某个t ； 例如t 。，使得( y ，y ：，y 。) = t 。，则一定存在y 。和y 。，使得( y 。，y j ) = t - ， 得到了f ( y t ，y z ，y 。) = f ( y 。，y z ) + f ( y 。) _ 土f 工2 工。 1 ，则 s 】是可逆的 证明：反设存在一个满足条件的集合s ，使得 s 不可逆。由引 理2 1 、和定理2 9 有： a ( x ，) = f ( x ，) 一f ( ( x ，x ：) ，( x j ，x 。) ，( x ，x 。) ，1 ) = o 。s 是最大 公因子封闭集合，由引理2 3 存在y 。、y ：、t 、y ，s ，( 1 p 7 ， 2 j r ； x 。，丽且当i j 时，y ；不整除y j ) ，使得 口( x 。) = f ( x 。) 一f ( y 。，y 2 ，y 。) = o( 2 2 ) ( 1 ) 当p = 1 田于，：y t x - ，口( x t ) = f ( x t ) 一f ( y t ) = ；一每 0 ，与( 2 2 ) 矛盾。 ( 4 ) 当p = 6 时，设s = x 。，y 。，y 。，y 。，t 。，1 ) 。易见当i j 时， ( y ；，y j ) = t 。或l 。由引理2 2 有f ( y i ，y 2 ，一，y 。) = f ( y 。，) r z ，y ；) + f ( y s ) f ( c 。7 ) + f ( y s ) 一f ( c s ) o ，与( 2 2 ) 矛盾。 ( 6 ) 当p = 4 时，设s = x ，y l ，y ：，y 。，y 4 t ，t ：，t3 ，1 ) 。不妨设t 。 t 。 t 。，下面我们分四种情况加以讨论： 若( y 。，y 2 ，y 。，y 。) = t 。，则当i j 时，( y ；，y ，) = t 。容易验证口( x 。) 0 ，与( 2 2 ) 矛盾。 若( y i y 。，y 。，y 。) = t 。，则t 。i t 。不难发现，存在d 。 y ，( i = 3 、 4 ) ，；使得f ( y - ，y z ，y 3 ，y 。) = f ( y - ，y z ) + f ( y 。) f ( d 。) + f ( y 。) f ( d 。) o ，与( 2 2 ) 矛盾。 若( y 。，y ：，y 。，y ，) = t 3 ，则t 。it 。且t 。i t 。 若( t 。，t 。) = t ：，则存在d 。 y 。( i = 3 、4 ) ，使得f