ⅰ-1矩阵的积和式极值与非负整数矩阵的积和式新上界

《ⅰ-1矩阵的积和式极值与非负整数矩阵的积和式新上界》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、硕士学位论文MASTER’STHESIS(0，1)矩阵，(0，一1，1)矩阵在代数、组合计数及图论中均有重要应用．例如，对于简单图G而言，其邻接矩阵A(G)、关联矩阵B(c)均为(0，1)矩阵，详见[1】．对于定向图G盯而言，其邻接矩阵D(V∥)为(o，--1，1)矩阵，详见[3】．H．Minc等人在[5】中讨论了扎×n阶非负矩阵的积和式问题．然而遗憾的是，甚至对于形式上很简单的(0，1)矩阵，其积和式尚不能全部求解．事实上，L．G．Valiant予1979年已经证明；计算(o，1)矩阵的积和式问题是一个带P完备问题，详见[10，11】．S．Song，S．G．Hwa

2、ng，S．Rim，G．Cheon等人在【7】中给出了具有z个0元的佗×n阶(0，1)矩阵的积和式的极值问题．L．M．Bregman在[9]中也得出(0，1)矩阵的积和式的另一个新上界．而对于具有非负整数元的完全不可分解矩阵，H．Minc，S．Song等人在[4，8]中也得出不同形式的积和式的上界．基于上面的工作，本文将首先给出具有一定条件的S(m×n，f)、F(m×佗，k)上的积和式的极值，然后讨论具有特殊条件下G(m×礼，k，2)上的积和式的极值，最后将L．M．Bregman，H．Minc，S．Song等人关于积和式的上界作出更进一步的推广．为此我们先给出相关概念

3、及需用到的已知结果．记In】：=．[1，2，⋯，凡)．对于矩阵A=(％)m×n，m≤n，称Per(A)=∑口1，矿0)a2,a(2)⋯‰咖)为矩阵A的积和式，其中求和符号跑遍所有从[m】到M的单射．如果m>n，则定义Per(A)=Per(Ar)．令rM为陋】中r元子集序列叫=(u1，忱，⋯，坼)，其中1≤咄≤仃，z=1，2，⋯，7．．令QM={(叫1，0d2，⋯，坼)11≤u1

4、义A(QIp)为将矩阵A中划去子矩阵A[a捌中的元所在的行、列后剩下的元素构成的(m—h)×(佗一k)阶子矩阵．特别地，对于u∈Qm，n，记A[△lu】为A中由u所确定的的列构成的m×m阶子矩阵．令Jm×n=(％)m×n，其中aij=l，i∈[仇】，J∈fnJ．对于矩阵A，B而言，如果存在置换矩阵P，Q使得B=PAQ或B=PATQ，则称JE7组合等价于A显然，若A组合等价于B，则Per(A)=Per(B)．1对于n×n阶矩阵A而言，若存在整数k，其中l≤k≤礼一1，使得A中含有一个k×(n—k)阶0子矩阵，则称矩阵A为部分可分解矩阵．不是部分可分解的矩阵称为完全不可

5、分解矩阵．对于矩阵A=(％)仇×n，B=(％)mxn，若％≤b对任意的i∈[m】，歹∈M成立，则称A≤B．如果矩阵中某些元素位于同行(列)时，我们称它们在一条线上．所有元素为0或1的矩阵称为(0，1)矩阵；所有元素为O或一1的矩阵称为(0，-1)矩阵；所有元素为一1或1的矩阵称为(一1，1)矩阵；所有元素为0或一1或1的矩阵称为(0，一1，1)矩阵．所有元素绝对值不大于1的整数矩阵称为厶1．矩阵．显然，上述(0，1)矩阵，(0，一1)矩阵，(一1，1)矩阵，(o，-1，1)矩阵均为，．1．矩阵．记v(m×佗，z)为恰有z个O元的m×n阶(O，1)矩阵构成的集合；S(

6、m×佗，2)为恰有f个0元的m×礼阶(0，-1)矩阵构成的集合；F(m×n，k)为恰有k个一1元的m×他阶(一1，1)矩阵构成的集合；G(m×n，惫，f)为恰有f个0元、k个一l元的m×礼阶(0，-1，1)矩阵构成的集合．利用上述定义，有如下关于矩阵积和式的结论；定理1．1([4】)．若A=(口玎)m×n，其中i∈【m]，J∈In]，m≤他，则●～(1)Per(今=Per(AT)j(2)若2≤m≤r$，o／∈Q，，m，则Per(A)=∑Per(A[alul)Per(A(alw))．．u∈％“。fl特别地，对于任意的i，1≤i≤m，Per(A)=∑砚，tPer(A(i

7、lt))．t=1对于(0，1)矩阵，S．G．Hwang等人得出了其积和式的如下极值：定理1．2(【7])．若2≤z≤m，令Per(A1)，Per(A2)分别为u(mxn，z)中矩阵的积和式的最大值，第二大值，则Per(A1)=Per(A2)=(1．1)(仇n-一：)(⋯)l，(1．2)且当(1．1)，(1：2)中等号成立时，矩阵分别组合等价于如下的矩阵Al，A272讥扒∥一m几-二V，，～，●X吃．Z．^‘．_I●一一、、，佗m≈o∥V一寡9几＼／＼f一【D一m∑言∑!iA1=A2=其中未括出的元素均为1．f，‘-___—、_I__O0f一1，‘__·--—-_