（运筹学与控制论专业论文）有关三维组合矩阵类的若干结论.pdf

摘要 摘要 二维( 0 ，1 ) 组合矩阵类a ( r ，s ) 这个概念由r i c h a r da b r u a l d i 教授2 0 0 6 年在( ( c o m b i n a t o r i a lm a t r i xc l a s s ) ) 一书中提出，并对此类矩阵的存在条件，基本 结构给出了详细的介绍与证明。 本文在二维( 0 ，1 ) 组合矩阵类的基础上，对其进行了推广，提出了三维 ( 0 ，1 ) 组合矩阵类a ( r ，s ，t ) 的概念，并针对此类矩阵存在的充分必要条件及 结构特点展开研究。 在证明矩阵类a ( r ，s ，t ) 存在定理时，采用了构造性的证明方法。首先引入 矩阵的优超关系，得到尺s 丁之间的相互联系的4 个引理，然后分别就尺s 丁为 m 阶非负整数方阵及尺s 为m p 阶r 为珑阶非负整数矩阵的情况构造出满足条 件的三维( 0 ，1 ) 组合矩阵类a ( r ，s ，t ) ，最后由这两种特殊情况推出a ( r ，s ，丁) 的存在定理。 本文从三个方面对矩阵类a ( r ，s ，t ) 的结构进行了讨论。首先构造得到三维 矩阵类中特殊的矩阵，这种构造方法使我们很容易地找到满足条件的矩阵。其次 我们讨论任意两个属于a ( r ，s ，t ) 的矩阵的关系，得到转换定理，使我们可以从 任意一个属于a ( r ，s ，t ) 的矩阵出发得到a ( r ，s ，t ) 中其它的矩阵。最后讨论了直 积运算，两个属于a ( r ，s ，t ) 的矩阵做直积运算后得到的矩阵仍属于a ( r ，s ，t ) 。 关键词组合矩阵；高维矩阵；( 0 ，1 ) 矩阵；直积 北京t 业大学婵学硕l 学位论文 a b s t r a c t t o w d i m e n s i o n a lc o m b i n a t o r i a lm a t r i xc l a s sw a sf o u n db yr i c h a r da b r u a l d i i nh i sb o o k i n2 0 0 6 i nt h i sb o o k ，h eg a v eu st h e d e f i n i t i o no ft h i sm a t r i x ，a n dp r o o fi t se x i s t e n tt h e o r y , a n da n a l y s i si t sc o n s t r u c t i o n i nt h i sp a p e r , w ed e f i n et h i r d d i m e n s i o n a lc o m b i n a t o r i a lm a t r i xc l a s s a ( r ，s ，t ) b a s i co ft o w d i m e n s i o n a lc o m b i n a t o r i a lm a t r i xc l a s s t h e nw ed i s c u s s t h ee x i s t e n c ea n dc o n s t r u c t i o no ft h i sm a t r i x w h e nw ep r o o ft h et h e o r e mo fe x i s t e n c e ，w eu s et h ew a yo fc o n s t r u c t i o n f i r s t l yw ed e f i n et h em a j o r i z a t i o no f m a t r i xt og e tf o u rl e m m a sa b o u tt h er e l a t i o n b e t w e e nrst s e c o n d l yw ep r o o ft h ee x i s t e n tt h e o r yf o ru n u s u a l l yc a s e ，o n ec a s ei s rsti sm o r d e rm a t r i x ，a n da n o t h e ri srsi sm o r d e rm a t r i x ，b u ttmb yp - o r d e rm a t r i x t h e nw eg e tt h ee x i s t e n tt h e o r yi ng e n e r a ld u et ot h es p e c i a lc a s e i nt h i sp a p e r , w ed i s c u s st h ec o n s t r u c t i o no ft h i sm a t r i xf r o mt h r e es i d e s f i r s ti s a s p e c i a lm a t r i xi na ( r ，s ，t ) u s i n gt h i sw a y w ec a ng e tm a t r i xi n a ( r ，s ，t ) e a s i l y s e c o n di st h ei n t e r c h a n g e s ，t h a ti sw eg e to n em a t r i xi na ( r ，s ，t ) f r o mt h eo t h e ro n e ，a sl o n ga s w eu s el i m i t e ds t e pi n t e r c h a n g e ，t h i sq u a n t i t yl e tu sg e ta n ym a t r i xi na ( r ，s ，t ) f r o mo n e m a t r i x t h i r di st h ed i r e c tm u l t i p l i c a t i o nb e t w e e nt w om a t r i xi n a ( r ，s ，t ) ，w eg e tt h e c o n c l u s i o ni st h en e wm a t r i xi sa l s ob e l o n gt oa ( r ，s ，丁) k e y w o r d s c o m b i n a t o r i a lm a t r i xc l a s s ；( o ，1 ) m a t r i x ；d i r e c tm u l t i p l i c a t i o n i l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 丽息；。 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密 签名： 应遵守此 导师签名日期：飞! i = 兰! i i 组合矩阵类简介 第1 章绪论 组合矩阵是一个近2 0 余年来兴起并发展迅速的一个数学分支，它用矩阵论 和线性代数来证明组合定理及对组合结构进行分析和描述，同时也把组合论的思 想和论证方法用于矩阵的精确分析及揭示阵列的内在组合性质。 组合矩阵这个概念是美国数学家h j r y s e r1 9 7 3 年1 月在题为“组合矩阵 论的讲演中第一次提出这个数学分支：1 9 8 3 年r a b r u a l d i 在美国数学会主 办的“矩阵理论和应用 上发表了题为t h em a n yf a c e t so fc o m b i n a t o r i a l m a t r i xt h e o r y 的演讲，此演讲论述了矩阵的组合意义、用矩阵论来证明一些 组合定理并说明这些定理中所蕴含的矩阵论意义、组合矩阵分析、组合矩阵代数。 此次演讲奠定了组合矩阵发展的基础。 2 0 世纪九十年代，r a b r u a l d i 与h j r y s e r 共同编写了组合矩阵论 ( c o m b i n a t o r i a lm a t r i xt h e o r y ) ，其中详细介绍论证了矩阵的组合性质、矩阵 和图的谱、矩阵方法和矩阵分析。此书为组合矩阵的发展提供了有利的理论依据。 1 9 9 6 年柳柏濂教授出版了组合矩阵论一书，是我国第一本介绍组合矩 阵论方面的专著，填补了我国在这方面的理论空白。虽然理论归功于r a b r u a l d i 与h j r y s e r 的演讲和著作，但同时介绍了今年来日趋活跃的组合矩阵课题，对 我国学者的工作给予了足够的关注。 2 0 0 6 年r a b r u a l d i 出版了c o m b i n a t o r i a lm a t r i xc l a s s ，第一次提出 了组合矩阵类的概念；给出了此类矩阵存在的充分必要条件；分析了结构特点， 如矩阵的秩，迹，所对应的行列式，积和式的值：论证了一些组合参数及线性代 数参数在矩阵类上的意义。同时还定义了实对称矩阵类及t o u r n a m e n t 矩阵类， 并对存在条件，基本结构，及特殊的矩阵作了详细的论述。 北京工业大学理学硕士论文 1 2 高维矩阵研究现状 早在两百多年前，j a c q u e sh a d a m a r d 发现1 2 维及2 0 维的( 一1 1 ) 矩阵具 有正交性，这类具有正交性的高维矩阵成为高维h a d a m a r d 矩阵。国际上对高维 h a d a m a r d 矩阵的研究比较深刻。 1 9 7 9 年p j s h l i c h t a 出版了h i g h e r d i m e n s i o n a lh a d a m a r dm a t r i c e s ， 此书激发了人们对高维h a d a m a r d 矩阵的研究。 m h a l l ，l b a u m e r t ，s g o l o m b 在过去的三十多年中一直致力于h a d a m a r d 矩阵应用的研究，他们利用3 2 维h a d a m a r d 矩阵设计了8 位正误密码。 在我国北京邮电大学的杨义先教授在此方面有很高的成就，2 0 0 6 年编写了 高维阿达码矩阵理论与应用( t h e o r y a n da p p l i c a t i o n so f h i g h e r - d i m e n s i o n a l h a d a m a r dm a t r i c e s ) 一书，此书推动了高维矩阵的发展，证明了高维哈达码矩阵 的存在性，对矩阵结构作了说明，并首次将高维哈达码矩阵用于密码体制设计和 高维快速正交换之中。 1 3 课题简介 本文在二维组合矩阵类的基础上提出三维组合矩阵类的概念，并力求证明此 类矩阵的存在性，分析此类矩阵的结构。 在证明矩阵类a ( r ，s ，丁) 存在定理时，拟采用了构造性的证明方法。首先引 入矩阵的优超关系，得到rs 丁之间的相互联系的4 个引理，然后就rs 丁为m 阶非负整数方阵及rs 为m p 阶丁为m 阶非负整数矩阵的情况构造出满足条件 的三维( 0 ，1 ) 组合矩阵类a ( r ，s ，t ) ，最后由这两种特殊情况推出存在定理。 本文计划就三个方面对矩阵类a ( r ，s ，z ) 的结构进行了讨论。首先构造得到 三维矩阵类中特殊的矩阵，这种构造方法使我们很容易地找到满足条件的矩阵。 其次我们讨论任意两个属于a ( r ，s ，t ) 的矩阵的关系，得到转换定理，使我们可 以从任意一个属于a ( r ，s ，t ) 的矩阵出发得到a ( r ，s ，t ) 中其它的矩阵。最后讨论 第1 章绪论 了直积运算，两个属于a ( r ，s ，t ) 的矩阵做直积运算后得到的矩阵仍属于 a ( r ，s ，r ) 。 第2 章二维( 0 ，1 ) 组合矩阵类 本章首先给出了二维组合矩阵类的定义，然后证明了二维组合矩阵存在的充 分必要条件，最后分析了二维组合矩阵类的结构。 2 1 二维( 0 ，1 ) 组合矩阵类定义 设a = a 。，】为m 刀阶矩阵，记 = a n + a 1 2 + + 口ma = 1 , 2 ，以) s - ，= a i + a 2 + + 口彬 ( j f = 1 , 2 ，拧) 分别为矩阵a = 口。】的行和与列和。并记 r = ( r l , r 2 ，册) s = 0 l ，s 2 ，s 。) 分别为矩阵么的行和向量与列和向量。 易知向量r 与s 满足等式方程： ，l + 吃+ + ，册= j l + j 2 + + s 。 ( 2 - 1 ) 记f = r ( a ) 为矩阵4 的所有元素之和。若r 、s 为非负向量，满足( 2 1 ) 式，和 为f 且不为0 ，nm x g 阶矩阵彳= ，其中嘞= 华( f = l ，2 ，硝j f = 1 ，2 ，刀) ， 是具有行和为尺，列和为s 的矩阵。 我们也可以按下列方式构造一个具有行和为r ，列和为s 的非负矩阵 a = 口。 。如果胁= 1 ，则a = p ，j 2 ，s 。】是唯一的满足条件的矩阵；如果玎= 1 ， 则a = r l , r 2 ，】7 是唯一的满足条件的矩阵。现在假设m 1 ，n 1 。我们选取 a l l = r a i n r , ，j l ，不妨假设口1 1 = 厂l 。令a 1 2 = = a l 。= 0 ，并定义r = ( r 2 ，) s = ( s l 一，s 2 ，s n ) ，则，2 + + ，胴= s i - r , + j 2 + + s 。，由归纳假设，则一定 存在一个( 肌一1 ) n 阶矩阵么具有行和为r ，列和为s ，这样矩阵 譬一 第2 章二维( o ，1 ) 组合矩阵类 是一个非负的具有行和为r ，列和为s 的矩阵。由这种方式得到的矩阵最多有 朋+ 力一1 个正元素。 我们记 n ( r ，彤 为行和向量为r ，列和向量为s 的所有非负矩阵集合。 定理2 1 1 设r = ( 1 ，r 2 ，o ) ，s = ( s 1 ) s 2 ，s 。) 为非负向量，则n ( r ，$ 非空的 充要条件为等式( 2 1 ) 成立。 如果我们对于矩阵4 附加其他一些要求，则等式1 1 就不再是矩阵4 存在的 充分条件。例如，不存在行和向量为r = ( 3 ，3 ，2 ，1 ) ，列和向量为s = ( 4 ，4 ，1 ) ，且元 素只能为0 或l 的4 3 阶矩阵。 定义2 1 1 设向量r = ( ，i ，1 2 ，) ，s = ( s l ，s 2 ，s 。) ，若m n 阶( 0 ，1 ) 矩阵 a = 【a 满足行和向量为r ，列和向量为s ，则a = a 。】的全体所构成的集合称 ( o ，1 ) 矩阵类 1 】，记为a ( r ，s ) 。 2 2 二维( 0 ，1 ) 组合矩阵类的存在定理 g a l e l 2 和r y s e r 3 1 分别独立地证明了具有行和向量为r 列和向量为s 的( 0 ， 1 ) 矩阵类存在的充要条件。r y s e r 利用的是归纳和直接组合性质；g a l e 利用的 是网络流理论。下面我们给出简单的归纳证明。 2 2 1优超关系 设x = ( x 。，x ：，x 。) ，y = ( y l ，y 2 ，y 。) 是两个n 维非增实数向量，即 若部分和满足 x l x 2 x 月，y 1 y 2 y 在k = 珂取等号；等价地 七七 e x 。e y ，( 1 sk 玎) f i lj i l x ，y ，( o k n - 1 ) 北京工业大学理学硕士论文 在七= 0 取等号，则称向量】，优超于x ，记为j 】，。 记r = ：。t = ：。y ，优超关系是一种建立在，z 维非增实数向量上或者说 具有相同向量和f 的部分关系。n 维( 司i ( r n ，刀，r n ) 是满足优超关系的元素 最小的向量；( r ，o ，o ) 是元素最大的向量。 若向量x ，y 维数不同，我们可以添加一些o 元素使它们元素个数相同，然 后再确定优超关系；若向量x ，】，不是非增的，则可以重新排列元素的顺序得到 非增的向量x7 ，j ，若x p 则称x _ 。 向量r 的共轭也可以表示为下面的图形的形式。考虑一个具有m 行的序列， 其中第f ( 扛1 , 2 ，聊) 行的前个元素为l ，则r 的共轭尺为此序列的列和向量。 例如，r = ( 5 , 4 ，2 ，1 ，1 ) ，刀= 5 ，利用序歹0 l1l11 11l l 1l 1 1 我们得到r = ( 5 ，3 ，2 ，2 ，1 ) 。由此种序列构成的矩阵我们成为具有行和向量r 的极 左矩阵。 对于共轭与优超关系我们有下面的定理。 定理2 2 1 设x = ( x l ，x 2 ，x 。) ，y = ( y l ，y 2 ，y 。) 是两个刀维非增、非负整数向 第2 章二维( o ，1 ) 组合矩阵类 量，若x 一 】，则】， x 。 证明：因为x p 的最大脚标，则 p 疗n i = r a i n x , ，办= x - p + l = lj = l i k + l k p + y f i - k + l m i n y 。，p ) = 2 y ； t = k + l l l l 所以】， x 。 定理2 2 2 设x = ( x 1x 2 ，矗) ，y = ( y i ，y 2 ，y 。) 是两个n 维非增、非负整数向 量，且x 】，取x 为把x 的第i t , f 2 ，f 。个位置的元素减1 ，y 7 为把y 的第 ，2 ，_ ，p 个位置的元素减1 ，如果f i t ，i 2 - j 2 ，f p ，则x y 。 证明见【1 1 。 2 2 3 二维( 0 ，1 ) 矩阵类存在定理 定理2 2 3 设r = ( r l , r 2 ，卅) ，s = ( s 1j 2 ，s 。) 是递减的非负整数向量，则 a ( r ，s ) 非空的充要条件是s r 。 证明：必要性 设所玎阶矩阵a a ( r ，s ) ，则有1 + ，2 + + = s l + j 2 + + s 。我们把彳 划分成下面的形式： 陋，j 垦j其中b ，是肌，阶矩阵 则曰。中前，列的1 的个数不会超过彳的极左矩阵前，列的1 的个数，即 即s r 。 充分性 、， 1 1一聍 一 一o ，埘 一 s ， 北京工业大学理学硕士论文 我们利用反证法。设m + 门为满足条件的最小的数值，即m ，n 为满足s r ， 但a ( r ，s ) 为空的最小值，_ i i m + n 也满足f = 1 + r 2 + + 最小。 分情况讨论： ， 1 ) 若j ，= ( 1 j n - 1 ) ，取 r l = ( t ，；，) = ( m i n l ， ) ，m i n l ，胛 ) ，s l = ( s l ，s 2 ，s ，) 贝i j 我仃 易知有s l r l 。 而对于向量 r 2 = ( 吒一r l r , 一，；，厶一) ，s 2 = ( s i + ij 2 ，s n ) 也有s 2 0 ，并记r = ( ，厂2 ，) 为r 的共轭，则r 为非增向量。a ( r ，r ) 中存在唯一的矩阵a ( r ，刀) ，它的第f 行 的前各元素为l 。又因为r 为非增的，a ( r ，z ) 的每- - 歹u o e 的1 都分布在前面。 下面我们就从彳( r ，z ) 出发构造一个矩阵彳a ( r ，s ) 。 1 ) 令彳。= a ( r ，行) 为mx 以阶矩阵，互为朋o 阶空矩阵。 2 ) 当k = 刀，刀一1 ，l 时，把4 的位置靠前的s 。行中位于最后位置1 转移到 第k 列，则我们得到矩阵 k 艮川】 这里4 一。有k 一1 列。 3 ) 最后有矩阵j = z 。 对于得到的矩阵彳，有下面的定理。 定理2 3 1 如果s - r ，则上述过程可以实现，并且a a ( r ，s ) 。 证明：当刀= l ，a = a l = a ( r ，1 ) ，因为s 1 ，s 尺，意味着 s l + j 2 + + j 。一l ，l 。+ ，2 + + t l s l + s 2 + + s 月21 + 厂2 + + 厶 且s 。同时s l 1 ，s l j 。，所以s 。，因此上述过程的第一步可以实现。 由构造方法可知，a 川有非增的行和向量设为u = ( “。，“：，“。) ，非增的列和为 u 的共轭u = ( “：，“：，“：一。) ，所以a “= a ( u ，万一1 ) ，下面我们证明 ( s l ，j 2 ，s 州) u 首先我们观察到 北京工业大学理学硕士论文 s l + j 2 + + s n - 1 = u l + 1 4 2 + + u h l 设k ( 1 k 刀一1 ) 为一整数，则 “? = m i n u ，j i ) = 芝m i n ( i - 1 ，七 t = li = l i , - i + r a i n r , ，七) f = j h + 1 分两种情况讨论。 1 ) r l l s 。，既然r 是非增的，对于f 三1 ，2 ，s 。有k + 1 ，因此 所以 和 因此 j 2 m i n r , - 1 ，七) = k = m i n r 。，七 f = l kn l ii “? = r a i n r , ，七) = ，j s 。 t = l i = 1t - it - i 2 ) t 。 + 。一s 。：芝一 f = lj = l f = l 一s 。 t = l k ys ， 一 i - i ( s _ r ) v s 山) 又由j l + s 2 + + s 州= “：+ “2 + + “：一l ，所以( s l ，j 2 ，s 川) 一 0 的最大下标，即 s ：s ；s ：一l s 二，s ：+ l s ：一l s ：s ： j ? s ；s ：一l j ：s ：+ l s ：一l j ：j ： 讨论：1 ) 当s 二一s 二s ：一s ： 0 时，令 s a = ( j f n ，s 0 ) ，j = ( s ：，s ；，j ：一，s ：一( j ：一s ：) ，s ：+ ，s ：一。，5 ：，s ：) 2 ) 当j ：一s ： 一s ： 0 时，令 s o ) - ( s f l ) ，s 乳一，s = ( j ：，s ：，占：一l ，s ：，s ：+ l ，j ：一l ，s ：+ ( s ：一s ：) ，j ：) 把s ( 1 与s ，s 。作比较可得 s 。 s ( 1 ) s 7 但s ( 1 与s ”之相同分量的个数比s 与s ”之相同分量的个数至少多一个。于是依 上述过程，由s ( 1 可作s ( 2 、，使有性质 s s ( 2 ) s ( 1 ) 并且s ( 2 与s ”的对应相同分量的个数又至少增加一个。此过程继续有限次( 至多 刀次) 后必停止。于是有 s = s ( 七) s ( 一1 ) s ( 2 ) s ( 1 ) s ( o ) ：s 7 我们称上述形式为由向量s 到s ”的全链。特别地。当七= 0 时，s = s 。 对于向量s ，s 。我们可以定义一个数值函数形为 形c s ，s 7 ，= l m l i l ( s ：乏三羔：一j ：， 第2 章二维( 0 ，1 ) 组合矩阵类 定理2 3 4 ( 魏万迪【4 1 )在上述假设下，若s 尺，不妨设s 是单调非增，则 a ( r ，s ) l 兀w ( s ，s o ) 1 0 s l ! ：七一l 其中s ( 是从r 到s 的全链中除去s ( ) = s 以外的全部向量。 从下面的例子，我们考察如何运用定理2 3 4 求i a ( r ，s ) i 的下界。 例2 3 4 易得 r = ( 7 ，5 ，5 ，4 ，4 ，3 ，2 ，2 ，1 ) s = ( 7 ，6 ，4 ，4 ，4 ，4 ，4 ) r = ( 9 , 8 ，6 ，5 ，3 ，i ，i ) 易检验 s j + l ，七= o ，l ，1 一，p 一1 ) | 例如：尺：脯主 f1 21 n 一3 。1 2 。0 卜 f2 l 三2 三。严 同理我们还可以得到万( 聊，s ，p ) 及才( 肌，i ，丁) 。 k = 0 , 1 ，p 一1 j = 0 , 1 ，以一1 i = 0 , 1 ，m 一1 = 0 , 1 ，玎一1 11 31 20 1o 北京工业大掌理掌坝士论又 类似于向量的优超关系，我们引入两个矩阵优超的关系。 设两个m 行阶非负实矩阵s 及季，若它们行向量j ，瓦( i = 0 , 1 ，m - 1 ) 具有 优超关系，即墨 瓦，则称矩阵歹行优于s ，或者说s 行劣于蜃，记为 s _ - s 若它们列向量f ，t j ( j = o ，i ，1 ，刀一1 ) 具有优超关系，即， l ，则称矩阵歹列优于 s ，或者说s 列劣于豆，记为 s1 4 歹 o r 季州s 引理1 ：设尺= ( 1 ，) ，s = ( j i ，一，s 。) 为非负整数向量，若s r 。，则尺一 s 。 证明：s _ 尺+ ，3 a a ( r ，s ) ，r 一 s 引理2 ：设r = ( 1 ，厶) ，s = ( s l 一，s 。) 为非负整数向量，且s 一 r ，任取( o ，1 ) 列向量口，此列的元素之和为s 。，第九( 七= 1 , 2 ，屯) 个元素为1 ，取 r = ( 1 ，) = 2 。；三幺c ，= ，2 ，肌，s 7 = 。z ，) ，则s 7 r ”。 证明：s r ，3 a a ( r ，s ) ，取口为a 的第0 列，设矩阵a 为a 去掉第0 列 所形成的矩阵，则a 的行和向量为r ，列和向量为s ，即a a ( r ，s ) ，所以 s - 4r ”。 引理3 ：设r = ( n ，乙) ，s = ( s l 一，s 。) 为非负整数向量，且s r ，任取( 0 ，1 ) 行向量口，此行的元素之和为n ，第缸( 七= 1 , 2 ，n ) 个元素为1 ，取 s = ( s ；) s ：= s 歹二1 ；三乏( ，= t ，2 ，玎) ，r = ( 吃，) ，则s r r 。 ( 证明同引理2 ) 引理4 ：设r = ( 1 ，) ，s = ( s l ，一，s 。) 为非负整数向量，rs _ r ，任取( 0 ，1 ) 列向量口，此列的元素之和为s ，第( 七= 1 , 2 ，s 1 ) 个元素为1 ；任取( o ，1 ) 行向量，此行的元素之和为1 ，第i k ( 七= 1 , 2 ，1 ) 个元素为1 ，设 尺= c ，)2t 2 。：三二：o = ，2 ，m ，s = c s z ，s 一， s 。= c s ；， s ；= s 于三。乡三乏c 一，= 2 ，玎，r 。= c 呓，二， 第三章三维( o ，1 ) 组合矩阵类 贝0s 。 r ”。 ( 可由引理2 ，3 直接推出) 下面我们来就特殊情况讨论三维( o ，1 ) 矩阵类a ( r ，s ，丁) 的存在性。 定理3 2 2 ：设历是正整数，r = ( ) m 。脚，s = ( ) 。，t = ( 勺) 。辨是非负整数方阵， 且m ，s 暂m ，t ml = o ，1 ，m 一1j f = o ，l ，m 一1 七= o ，1 ，m 一1 ，) ， 则 a ( r ，s ，丁) 非空的充分必要条件是 s r r r 丁s r 于 其中r 表示行和矩阵为r 的极左矩阵2 ( g ，m ，m ) 的列和矩阵，r 于r 分别表示纵 和矩阵为丁的极左矩阵2 ( m ，m ，t ) 的行和矩阵及列和矩阵。 证明：必要性 若a ( r ，s ，丁) 非空，即存在a = a ( i ，歹，k ) a 。显然，彳在z 轴方向的矩阵 a ( i ，c ) c = 0 ，1 ，2 ，m 一1 的前，j f = o ，l ，m - 1 列元素之和不大于4 的极左矩 阵2 ( r ，m ，朋) 在z 轴方向矩阵2 ( i ，c ) ( c = o ，m 一1 ) 的前列元素之和，即j 的 行向量优超于s 的行向量，所以sir + 。 同理，可证r r 丁s r 于。 充分性( 我们做一个构造性的证明) 已知s r ，尺r 丁，s r 于，即 毛 ，形 ，s ： 五 f = 1 ，m _ ，= 1 ，m k = 1 ，m 取向量 ，j l ，因为s l 厂l ，由二维矩阵类存在条件，存在朋m 阶( 0 ，1 ) 矩阵 a 。a ( 1 ，j 。) 。设此矩阵的第列为口，则此列的元素之和为s 。，且此列中第 _ ，t ，2 ，j o ，个元素为1 ；并设此矩阵的第f 行为瓦，则此行的元素之和为，且 此行中第i if 2 ，f 个元素为1 。 取向量f ：，j ：，设口= ，因为s ：一 0 ，由引理2 则( s ：) ( 一) ，由二维矩阵 类存在条件，存在m ( m 一1 ) 阶( o ，1 ) 矩阵b ：a ( ( f m ( s ：) ) ，设b 。= qb ：) ， 则b 。a ( f ：，s ：) 。设此矩阵的第k 列为履，则此列的元素之和为屯。，且此列中第 k i 后2 ，k 跏个元素为1 ；并设此矩阵的第f 行为万，则此行的元素之和为，o ，且 北京工业大学理学坝士论文 此行中第i if 2 ，t ，。个元素为l a 取向量f 。，吖，设口= 瓦，p = 磊，引理2 则( t o ” ( f 。) ，由二维矩阵类存在 条件，存在( 所1 ) 咖- 1 ) 阶( o ，1 ) 矩阵c ：a ( 瓴n ( 们。设c 1 = ( ?孙 其中a 。为矩阵么。第一个元素；口7 ，p 7 分别为向量口，p 去掉第一个元素口。构成 的向量，则c 。a ( ，：，怕。设此矩阵的第k 列为以，则此列的元素之和为。，且 此列中第k i 尼：，k 咯。个元素为1 ；并设此矩阵的第行为乃，则此行的元素之 和为，。，且此行中第 ，：，九。个元素为l 。 重复此过程，直至我们取遍r 的所有行。 此时我们构造了m 个m xm 阶( 0 ，1 ) 矩阵么l ，a 2 ，4 3 ，a 朋，其中第 k ( k = 1 , 2 ，m ) 个矩阵a a ( r k ，) 。同时我们还构造了m 一1 个mxm 阶( o ，1 ) 矩阵b l ，b 2 ，b 3 ，b 及m 一1 个m m 阶( 0 ，1 ) 矩阵c l ，c 2 ，c 3 ，c 埘一1 分别属于 a ( ，：，j ：) ，a ( ，) ( = 1 , 2 ，m 一1 f = 1 , 2 ，m 一1 ) 。 取4 l ，a 2 ，么3 ，a 。的最后- - y , j ，以此川列为列，我们可以构造一mxm 阶( 0 ， 1 ) 矩阵，记为召。，则b ，a ( f ：，s ：) 。因为b 。的列和向量为s ：，而前m - 1 行 分别为矩阵c i ，c 2 ，c 3 ，c 小- l 的最后一行，此掰- 1 行的行为t o m - i , f l 川，。一2 川， 因为s | ：， 乙，所以b 。的最后一行元素之和必为f 剃m - l ，即b m a ( f 二，s 二) 。因此 我们也构造了m 个m m 阶( 0 ，1 ) 矩阵蜀，垦，岛，吃小吃，其中第 k ( k = 1 , 2 ，m ) 个矩阵b 。a ( t ：，s ：) 。 同理，取么l ，a 2 ，4 3 ，a 。的最后一行，以此m 行为行构造m xm 阶( 0 ，1 ) 矩阵，记为c 。，则c 。a ( t 。，) 。即我们也构造了m 个m xm 阶( 0 ，1 ) 矩阵 c l ，c 2 ，c 3 ，c m - l ，c 肼，其中第k ( k = 1 , 2 ，m ) 个矩阵c a ( t t ，) 。 综上，定理成立。 定理3 2 3 ：设m ，p ( m p ) 是正整数，尺= ( ) ，。，s = ( ) p 。，t = ( ) ，。是非 负整数矩阵，且 p ，s 灯sp ，t 。m f = o ，1 ，m 一1j = 0 ，l ，所一1k = 0 ，1 ，p l 第三牵三维( 0 ，1 ) 组合矩阵类 则a ( r ，s ，丁) 非空的充分必要条件是 s r r r 丁+s r 于 其中r 表示行和矩阵为r 的极左矩阵2 ( r ，m ，p ) 的列和矩阵，丁于1 分别表示纵 和矩阵为丁的极左矩阵a ( m ，m ，t ) 的行和矩阵及列和矩阵。 证明：必要性同定理2 。 充分性( 我们做一个构造性的证明) 构造过程同定理2 重复定理2 过程，直至我们取遍s 的所有行 此时我们构造了m 个m m 阶( 0 ，1 ) 矩阵a 。，a 2 ，彳3 ，a ，其中第 k ( k = 1 , 2 ，m ) 个矩阵a i a ( r k ，s ) 。同时我们还构造了m 个m p 阶( 0 ，1 ) 矩阵且，b 2 ，b 3 ，b 所及m 一1 个m x m 阶( o ，1 ) 矩阵c 1