（应用数学专业论文）分配格上矩阵的特征向量.pdf

摘要 本文主要研究了分配格上矩阵特征向量的代数结构和求解方法，由于分配格 已广泛应用于计算机领域，所以这是对模糊矩阵相关问题的一种必要推广。同时， 不再局限于标准特征向量的讨论，进而研究特征值为一般格值的情况。 文中首先讨论了格矩阵a 的标准特征向量。对任意给定的分配格上的方阵a 。 定义4 = 彳v a “1 v v a “一，其中一为a 的幂序列，证明了a ( o 的极限一 定存在，且l i m a ( o = 爿，以此为基础，证明了彳的全部标准特征向量为a 0 ) 列 f 帅 向量的全部“线性”组合。这一结果给出了分配格上矩阵标准特征向量的代数结 构和求解方法。文中还给出了计算彳w 的简便方法。 进一步的，讨论了非标准特征向量，即特征值为一般的格值时，特征向量的 求法。证明了向量元素小于等于特征值时的特征向量仍然可以全部利用a 0 ) 表 示。从而任给特征值名，我们都可以方便地找出对应于力的部分非0 特征向量， 并证明了在某一个充要条件下，全部特征向量都可以利用爿扣j 来表示。文中在一 个具体的格上给出了一个计算实例。 本文的创新性主要表现在：一方面把模糊矩阵推广到分配格上去分析，进而 描述了格矩阵特征向量的代数结构。另一方面，把对标准特征向量的研究推广到 特征值取普通格值时所对应的特征向量上，分析了其中的一些子结构，为进一步 研究特征向量提供了重要的理论基础，同时也为分析离散动力系统等实际应用提 供了新的解决途径。 关键词：特征向量；特征值；分配格；模糊矩阵；幂。 北京工业大学理学硕l 学位论文 a b s t r a c t t h em a i np u r p o s eo ft h i sp a p e ri st os t u d yt h ee i g e n v e c t o ra l g e b r a s t r u c t u r eo fm a t r i c e so v e rd i s t r i b u t i v el a t t i c e sa n dt h ec a l c u l a t i o no f t h e s ee i g e n v e c t o r s w i t ht h ed i s t r i b u t i v el a t t i c e sb e i n ge x t e n s i v e l yu s e d i nc o m p u t e rf i e l d ，t h em a i nr e s u l t so b t a i n e di nt h ep a p e rg e n e r a li z et h e r e l a t i v er e s u l t so nf u z z ym a t r i c e sn e c e s s a r i l y h e a n t i m e ，i t sn o t r e s t r a i n e do nt h ed i s c u s s i o no f s t a n d a r de i g e n v e c t o rb u ta l s ot h e e i g e n v e c t o rw h i c hi so v e rl a t t i c e si sd i s c u s s e d f i r s to fa l l ，w ed i s c h s st h es t a n d a r de i g e n v e c t o ro fm a t r i xao v e r d i s t r i b u t i v el a t t i c e s f o rt h eab e i n gg i v e no v e rd i s t r i b u t i v el a t t i c e s ， w ed e f i n et h a t4 ) = a v v a “”。1 ，k l ，w h e r ea i st h ep o w e r so f m a t r i xa i t sp r o v e dt h a tt h el i m i t a t i o no f 彳m u s te x i s t a n d l i m a ( ) = 彳( b a s i n go ni t i ti sc a nb ev e r i f i e dt h a tt h ew h o l es t a n d a r d f e i g e n v e c t o r so faa r el i n e a rc o m b i n a t i o n so fc o l u m nv e c t o ro f 4 s ot h e e i g e n v e c t o ra l g e b r as t r u c t u r eo fm a t r i c e so v e rd i s t r i b u t i v el a t t i c e sa n d t h ec a l c u l a t i o no ft h e s ee i g e n v e c t o r sc a nb es o l v e db yt h i sr e s u l t i n t h i sp a p e r as i m p l em e t h o di sg i v e nf o rt h ec a l c u l a t i o no f 彳 f u r t h e r ，t h ec a l c u l a t i o no fn o n s t a n d a r de i g e n v e c t o rw h e ne i g e n v a l u e i so v e rl a t t i c e si sc o n s i d e r e d i ti st e s t i f i e dt h a ta l lt h ee i g e n v e c t o r s w h o s ee l e m e n t sl e s st h a no re q u a lt oe i g e n v a l u ec a nb ed e n o t e db y4 t h e nf o ra n ye i g e n v a l u e ，w ec a ne a s i l yf i n do u tp a r to ft h ea s s o c i a t e d e i g e n v e c t o rw h i c hi sn o n z e r o a n d i tc a nb ep r o v e dt h a tt h ew h o l e e i g e n v e c t o r sc a nb ed e n o t e db y 爿如) u n d e rs o m es u f f i c i e n ta n de s s e n t i a l c o n d i t i o n t h i sp a p e r g i v e sa ne x a m p l e t os h o wt h ec a l c u l a t i o no f e i g e n v e c t o ro v e rac e r t a i nl a t t i c e t h eo r i g i n a l i t yo ft h i sp a p e ri st h a t ：o nt h eo n eh a n d ，t oa n a l y z et h e m a t r i xo v e rt h el a t t i c e sw h i c hi st h eg e n e r a t i o no ff u z z ym a t r i x ，a n dt h e n u a b s t r a c t t od e s c r i b et h ea l g e b r as t r u c t u r eo fe i g e n v e c t o r s o nt h eo t h e rh a n d ，w e g e ts o m eu s e f u lc o n c l u s i o n sb ye x p a n d i n gt h er e s e a r c h o fs t a n d a r d e i g e n v e c t o rt on o n s t a n d a r de i g e n v e c t o ra n da n a l y z es o m es u b s t r u c t u r eo f t h e m t h er e s u l t so ft h i sp a p e rp r o v i d et h ef o u n d a t i o no ff u r t h e r t h e o r e t i c a lr e s e a r c ha n dan e wt r a i no ft h o u g h tt oc a l c u l a t ep r a c t i c a l l y i nt h ed i s c r e t ed y n a m i cs y s t e m k e y w o r d ：e i g e n v e c t o r s ：e i g e n v a l u e s ： d i s t r i b u t i v el a t t i c e s ： f u z z y m a t r i c e s ：p o w e r m 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：虚盈e t i # i ：虹：! ：2 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：压堡 导师签名： e t i # i ：丑q 第1 章绪论 第1 章绪论 1 1 课题背景 在人类发展的历史上，人们对自然现象和社会现象的描述，通常首先是定性 的描述。而这些定性的描述一般较为“笼统”或不精确，概念与概念之问往往没 有明确的界定，这种现象我们称之为模糊。模糊概念在现实世界，尤其在人类的 自然语言中几乎无处不在。造成模糊的原因很多，有概念本身的原因，也有人们 认知水平的原因，这里我们无法一一加以论述。实际上，模糊概念，如大小、多 少、轻重、好坏、智愚、年轻人、老年人等，又如学生“学得好”、“能力强”等， 一直都被人们广泛使用。尽管使用者对模糊概念往往有不同的“测量”尺度，比 如某甲称一个人是年轻人，可能是指此人在二十到三十岁之问，而某乙说一个人 是年轻人，则可能是指此人的年龄在二十五岁到五十岁，但人们使用模糊概念进 行交流时，通常都可以相互理解和沟通。人类自然语言精华与美丽的一半也许正 是它的模糊性。 另一方面，在不同的社会发展阶段，对一些模糊概念又需要进一步的精确刻 划。例如，公元五百多年前的孔子，有“学而优则仕”的说法，那么，所谓“优” 如何界定呢? 于是有了口试的测量方式；自隋初炀帝( 公元6 0 6 年) 建立了科举 制度，开始了笔试的测量方式。现在人们早已习惯用百分制或五分制记录笔试和 口试的结果，于是精确的度量分数就成为了模糊概念或属性“学得好”、“智力高” 或“能力强”的一种量化表示。在当今社会中，随着社会进步和科学技术的发展， 尤其是伴随计算机技术的革命而产生的信息领域的巨大变革，人们将被包含在无 穷无尽信息海洋之中。因此，人们迫切需要信息智能处理技术出现突破性的进展， 使计算机具有或部分具有人类的智能，能够处理包括自然语言在内的巨量信息。 不难想象，为了实现这一目标，首先需要计算机能够“理解”自然语言，而这种 理解，必须建立在对自然语言中的模糊概念的定量描述的基础上。 更普遍的，随着科学的不断发展，研究的对象越来越复杂，要求对系统的控制 精度越来越高，而复杂的系统是难以精确化的，这样，复杂性与精确性就形成了十 分尖锐的矛盾。 美国加里福尼亚大学扎德( l a z a d e h ，1 9 1 2 ) 教授仔细地研究了这个问题，他 发现古典集合论中的集合概念必须进行推广，这样有利于用数学模型来描述某些 现象中的模糊性。1 9 6 5 年，z a d e h 教授发表了模糊集合论论文，提出用“隶属 函数”这个概念来描述现象差异的中间过渡，从而突破了古典集合论中属于或不 北京工业大学理学硕上学位论文 属于的绝对关系。 定义1 1 1 论域u 上的模糊集合一，定义为 a = ( 心( 功，曲lx u 其中心( 工) 称为隶属函数，它满足 u _ ：u 哼m = 【o ，1 】 这里肘称为隶属空间。 z a d e h 教授这一开创性的工作，标志着数学的一个新的分支一一模糊数学的 诞生。模糊数学的诞生与发展，适应了历史需要，是不断发展的信息科学的一部 分。 控制论创始人维纳在谈人胜过任何最完善的机器时说：“人具有运用模糊概 念的能力”。人脑能对模糊事物进行识别和判决，但计算机对模糊现象识别能力 较差，为提高计算机识别模糊现象的能力，就需要把人们常用的模糊语言设计成 机器能接受的指令和程序，以便机器能像人脑那样简洁灵活的做出相应判断，从 而提高自动识别和控制模糊现象的效率，这就推动了数学家深入研究模糊数学。 类似于普通二元关系在数学中的地位和作用一样，模糊二元关系在模糊数学 中有着特别重要的作用。 定义1 1 2 设肖，y 为集合，称笛卡儿积x y = ( 工，y ) l 工x ，y 】，) 的任意 一个模糊子集胄，为x 到y 的模糊关系( f u z z yr e l a t i o n ) 。记为x r y 作为经典数学中函数关系的扩张，模糊关系正在逐渐应用于语言学、心理学、 工业设计和经济决策等各个领域。其中模糊二元关系已经成为一种简单有效的信 息描述方式，我们可以利用模糊矩阵来表达有限论域上的模糊二元关系，以有利 于探讨模糊关系之间的各种合成运算。 定义1 1 3 模糊关系r 与s 的复合关系记为ro s ，定义为 z r ( x ，力= s u p m i n z r ( x ，力，z s ( y ，力) ，暑z z 性 注意，这里只给出了模糊关系的一种复合运算，即所谓的s u p - n f i n 复合，一 般而言，模糊关系以什么样的方式复合取决于模糊集应用了哪些模糊运算。 当一个模糊关系的支撑集为有限集时，我们称之为有限模糊关系。显然， 所有有限模糊关系都可以由它们的模糊矩阵唯一确定地描述，因此，有关有限模 糊关系的一切运算都可以用模糊矩阵来相应的表示。可以看到，模糊矩阵是分析 有限模糊关系的重要工具，而模糊矩阵的特征值、特征向量的研究则是分析矩阵 性质的重要途径。本文则着重研究矩阵的特征向量问题，并且把模糊矩阵推广到 分配格上进行讨论。 2 第1 章绪论 推广到格上，是因为格是一种重要的代数结构，它和模糊理论结合得非常 紧密。生活中的事物有的具有可比性，比如风的强弱，衣服颜色的深浅，苹果的 大小等等，同时，也存在大量不可比的事物，比如：树的年龄和头发的长短，铅 笔的颜色和铅笔的耐用程度等等。如果这些不可比的事物也用全序集合来描述显 然不够恰当，所以格作为一种偏序集能够更准确地描述生活中不可比的事物。许 多定理及理论工具在格上进行推广也就显得更加必要。 讨论格三上的矩阵止如果有彳亭= 砧，五工，那么五称为特征值， 称为 格矩阵a 的一个对应于a 的特征向量。研究特征值、特征向量是研究线性变换， 矩阵性质，以及方程组解等的重要途径，在模糊数学理论中有着重要的应用，比 如，模糊矩阵所表达的复杂模糊关系能否用一个特征值来简化是个重要问题，再 比如，模糊离散动力系统z ( “1 ) = 丘r ( “，v 量0 ，就是通过标准特征向量的研究 得到了平衡态的解x = 彳) y ，】，f 4 7 8 。事实上，很多实际问题已经被归 结为模糊矩阵以及格矩阵的特征向量问题。 1 2 相关工作 1 2 1 模糊矩阵幂序列的研究工作 本文主要研究矩阵的特征向量，在证明结论时大量利用了模糊矩阵幂序列的 性质，对于模糊矩阵幂序列问题，最早研究的是m g t h o m a s o n ，他的最主要的 成果是：任一n 阶模糊矩阵的幂序列在有限步内或者收敛或者振荡，这一结论是 以后研究幂序列的主要依据 2 0 。h h a s h i m o t o 在1 9 8 3 年讨论了传递矩阵幂序 列的收敛性以及在m a x m i n 算子下模糊矩阵收敛的一些条件 2 1 ；我国的z h u r e i y i n g 在1 9 8 4 年讨论了对称矩阵幂序列的收敛性；w a l d e m a rk o l o d z i e j c z y k 在 1 9 8 8 年讨论了强传递模糊矩阵幂序列 2 2 。在当时，这方面最好的结果是由我 国的l ij i a n x i n 做出的。他在1 9 8 9 年讨论了关于幂零模糊矩阵的若干结果 2 3 ； 1 9 9 2 年给出了可控矩阵的充要条件，于1 9 9 4 年讨论了可控矩阵幂序列的收敛性 2 4 。他所做的成果是对当时所研究问题的一个更广意义上推广，因为可控矩阵 包括了当时所研究一切特殊矩阵，比如对称矩阵、传递矩阵等。但是可控矩阵这 一类型未能包含全部的常用矩阵，所以需要进一步发展。在这方面最好的结果是 由我国的f a nz h o u t i a n 和l i ud e f u 做出的。在1 9 9 7 年，他们研究了一个模 糊矩阵幂序列收敛的主对角元素，并且总结一些以前所取得的成果 1 ；在1 9 9 7 年，他们还讨论了模糊矩阵幂序列收敛的充分必要条件，研究了收敛指数，给出 了对任一n x n 收敛的模糊矩阵它的收敛指数最大到( n - 1 ) 2 + l 2 ；在1 9 9 9 年， f a n 把m i n 和m a x 算子推广为任意的模运算，即t 一模和s 一模运算 1 2 ；在2 0 0 0 北京工业大学理学硕士学位论文 年，p a n 对算子作了一个推广，给出了在m a x t 算子下的模糊矩阵幂序列收敛的 一些充分必要条件 2 0 。在这之后，许多学者又对f a n 和l i u 的成果作了总结和 更细的研究、更深的推广。比如说，s y m i n gg u u ，y u n g y i hl u r ，c h i n _ t z o n gp a n g 研究了在i i l a x m i n 运算符下的有限数量的模糊矩阵的无限次乘积 2 4 ；研究了幂 零矩阵问题，并在此基础上作了推广，讨论联立幂零矩阵问题 2 5 。 1 2 2 格矩阵幂序列的研究工作 本文着重讨论格上的矩阵，对( 0 ，1 ) 上取值的模糊矩阵做了进一步的推广。 选择在格上推广一方面是因为，格是一种广泛应用于计算机领域的代数系统，有 很强的实用性，格理论既能处理全序信息，又能处理不可比的信息，从而可以更 有效地刻画人类的推论、判断和决策的不确定性，尤其是对真值不完全可比较性 的研究，能够更真实地刻画人类的思维活动。另一方面，在理论上，诸如同态、 同构等许多代数概念可以直接应用于格的讨论。 有关格上模糊矩阵幂序列的研究工作主要是，2 0 0 1 年，t a ny i j i a 研究了 在e 0 ，1 上的格矩阵的指数和周期，给出了格矩阵收敛的充分必要条件，幂零格 矩阵的等价条件 2 6 ；在2 0 0 2 年，他研究了分配格矩阵算子的一些性质 2 7 ： 2 0 0 5 年，他研究了分配格上的幂零矩阵的一些性质和特点，给出了指数为n 的 幂零矩阵的充要条件以及递减的幂零矩阵的一些性质 2 8 。2 0 0 1 年，z h a n g k u n - l u n 研究了在d 。格下的幂零矩阵，给出了d 0 。格矩阵是一个幂零矩阵的充要 条件 2 9 ；2 0 0 4 年，姜超讨论了利用完备的分配格l 上三角模定义l 上的矩阵 运算，给出了这些运算的一些基本性质 3 0 ，并讨论了l 上的t 一幂等矩阵、t 一 传递矩阵 3 1 ；2 0 0 5 年，z h o uj i t u a n 讨论了在 0 ，1 上八一v 算子下格矩阵的 收敛性，得到了一些相应的性质，并且证明了任何非自反矩阵的幂序列都是递减 和收敛的 3 2 。 1 2 3 模糊矩阵特征向量的研究工作 早期的工作，最一般的结果应属于g o n d r a n 和m i n o u x ，他们在半环圆，。，o ) 上进行了类似讨论 1 0 一1 1 ，其中。和。都满足结合律、交换律和幂等律，并 且彼此都有分配律。主要结果是： 设a 为s 上的方阵，且当k - - - ) o o 时， a i k l ：a o o a k 的极限存在，令 爿：o l i m a i k i t 其中i 为单位矩阵。则， 4 第1 章绪论 1 ) a + 的列“乘以”某些常数是a 的特征向量。 2 ) 彳的任一特征向量都可写成a 的列向量的“线性”组合。 可以看出，上述结论中没有证明一的存在性，也没有涉及特征向量的具体 算法。 之后，k c e c h l a r o v a 用图论的方法主要证明了下面的定理： 设a = ( 吼) 为”月模糊矩阵， 1 ) 令 “彳) 2m i n ( m a xa , j ) x = ( 力。是模糊常向量。则x 是a 的特征向量当且仅当工c ( 彳) 2 ) 令x + ( 爿) = ( f ( 一) ，io $ e ( 彳) ) 7 ，其中 z ( 一) = m a x 伪；k 是d ( 以) 的前向顶点 则x ( 爿) 是4 的最大特征向量。 这里前向结点指的是以之为起点存在包含回路的通路。 到此，特征向量的判定或结构问题依然没有解决。 后来成功解决这个问题的是范周田，程乾生教授 7 利用了模糊矩阵的幂序 列性质给出了定理： 设a 为任意的n 阶模糊方阵，令 4 ( ) = ( i v 彳1 “4 ，v k l 其中，为刀阶单位矩阵。则a x = x 当且仅当存在只使j = 彳( “f 这个定理实际上说明了特征向量的代数结构，可叙述为：j 是a 的特征向量 当且仅当j 可表示为彳( 4 ) 的列向量的“线性”组合。 本文的主要工作之一就是在分配格上对此结论进行推广，以解决分配格上 特征向量的代数结构问题。 1 2 4 分配格上特征向量的研究工作 对于分配格上矩阵的特征值和特征向量问题，早期的研究工作参见文献 1 4 ，之后，许多工作围绕这个展开 1 5 一1 7 ，初期的工作都是在布尔代数或模 糊代数上给出的。这使得结论的应用范围有一定局限性。 ， y i j i at a n 把问题推广到完全完备分配格上 1 2 ，证明了关于某特征值的 北京1 = 业大学弹学硕士学位论文 特征向量构成一个子格，并讨论了在子格里最大特征向量孝+ 的求解： = 州”e v 彳( 一7 p ) ，如果五满足五v 刀= 1 其中五为特征值，4 是n x n 的格矩阵，五= 五o c 0 这一结论将在后面进行详细地 讨论。 对应的，证明了关于某特征向量的特征值也构成一个子格，同时讨论了在 子格里最大特征值z 和最小特征值刀的求解。 斧= e t 4 f ，z = 0 7 ao c 刀 但遗憾的是，作者没有给出分配格上特征向量子格的结构，以及所有特征 向量的具体求法。本文主要就足为了解决这两个问题 1 3 本文主要研究内容及结构 本文主要在分配格上分析矩阵特征向量的代数结构，首先研究模糊矩阵的幂 序列性质，在布尔矩阵和模糊矩阵之间利用模糊矩阵的分解定理构建了一个桥 梁，使得几乎所有布尔矩阵关于幂序列的结论可以平行推广到模糊矩阵。借助矩 阵的伴随图，可以较容易地判定模糊矩阵的收敛性。用类似的方法，进一步研究 格矩阵的分解定理，得到格矩阵幂序列的性质。接下来，通过证明格矩阵幂序列 彳扯) 的收敛性，利用格矩阵幂序列一o ) 的极限4 ( ”) 研究标准特征向量。可以把4 ”) 看成一个变换，任意特征向量只都可以通过这个变换，成为标准特征向量，因 而构成一个“线性”的标准特征向量的代数结构。同时，文中给出了计算a 扣) 的 简单算法，这样就可以容易地表示所有标准特征向量。求得最大标准特征向量以 及判定标准特征向量。 之后，讨论对应于旯的特征向量的代数结构，求得格矩阵对应于五的最大特 征向量，并分析特征向量小于等于知的特征向量的代数结构，利用格矩阵幂序 列4 ( ) 的极限4 ”) 来表示特征向量，给出具体特征向量的求法。并给出一个实例， 利用最大特征向量的判定，求得格上特征向量的全部解。 由实例的特殊性进行分析，给出了一个能求到全部特征向量的充要条件。 接下来，讨论特征向量小于等于刀e 的特征向量的代数结构，证明了 刀( 一7 w 是a 关于特征值五的小于等于刀e 的特征向量。这样就揭示了格矩阵对 应于a 的特征向量的两个重要部分的代数结构。 1 4 本文的创新内容及意义 6 第l 章绪论 本文在文献 1 2 的研究成果上进一步讨论了格矩阵的特征向量。文献 1 2 的结论只给出了最大特征向量的一个计算方法，而没有给出特征向量的整体结 构，也无法求得具体的每一个特征向量，本文解决了上述问题，创新如下： 1 利用格矩阵分解定理，证明了格矩阵幂序列彳是一定收敛的。 ( 定理3 2 7 ) 2 利用格矩阵幂序列一( 的极限彳( “来“线性”的刻画格矩阵4 的标准特征向 量的代数结构，可以用来表示所有标准特征向量。 ( 定理3 3 1 ) 3 给出了计算彳( ”的简便方法，降低了求解特征向量的计算复杂度。 ( 定理3 4 1 ) 4 讨论对应于a 的特征向量的代数结构，证明了仍然可以利用4 ( “) 。线性”的 刻画特征向量小于等于知的特征向量。 ( 定理4 2 1 ) 5 利用最大特征向量的判定，给出了一个能利用4 加) 求到全部特征向量的充要 条件。 ( 定理4 2 2 ) 6 进一步讨论对应于五的特征向量，求得了小于等于刀p 的特征向量。 ( 定理4 2 3 ) 本文把文献 7 关于普通模糊集合的重要结论推广到了格这一代数结构上， 是因为格理论和模糊理论是结合得非常紧密的。其中，格值逻辑是一种重要的非 经典逻辑，它是经典逻辑和模糊逻辑的推广。格值逻辑把多值逻辑的链型真值域 拓广到较一般的格上，既能处理全序信息，又能处理不可比的信息，从而可以更 有效地刻画人类的推论、判断和决策的不确定性，尤其是对真值不完全可比较性 的研究，能够更真实地刻画人类的思维活动。同时，格作为一种重要的代数结构， 在信息科学领域已得到了广泛的应用。比如，可以利用格理论，解决无限维空间 中关于严格拟凸，强拟凸向量优化问题中的有效解集与弱有效解集的连通性问 题。再比如，会议论文集c r y p t o g r a p h ya n dl a t t i c e s2 0 0 1 ，l n c s2 1 4 6 ， s p r i n g e r v e r l a gb e r l i nh e i d e l b e r g2 0 0 1 ，是格理论在密码学中应用研究的第 一个论文专辑。该专辑全面展示了目前国际上在这方面研究所取的成果，同时也 肯定了格理论在密码学中的重要地位。所以格理论的研究无论是在理论上还是实 际应用中都有着重要意义。本文通过分析格矩阵的特征向量，研究格上的矩阵， 7 北京工业大学理学硕士学位论文 使得矩阵这一表示二元关系的重要工具能够在格上得到更好的应用。为在格上进 一步的研究工作提供了理论基础。本文的研究方法，特别是利用格矩阵的分解定 理作为桥梁，把全序集合的结论推广到格上，为进一步的理论推广提供了有效途 径。 3 第2 章预备知识 第2 章预备知识 首先回顾一下将要用到的知识，包括模糊矩阵的定义，所涉及的格理论，格 上矩阵的运算性质以及图论的一些术语。这一章的定义，定理参见 3 5 2 1 模糊矩阵的定义与运算 定义2 1 1 设r 为m 元集合x = 瓴，x 2 ，j 。) 到一元集合 】，= j ，。，y 2 ，儿 的模糊关系，称矩阵m ( r ) = 吒) 为r 的模糊矩阵， 其中 白= ( 而，x j ) ，v i , j ，1 i m ，1 s ，以 定义2 1 2 设4 = 以“) 。，b = ( ) 。为模糊矩阵， ( a ) 序关系：彳b 当且仅当a f ，i = 1 , 2 ，m ，j = 1 ，2 ，刀 ( b ) j i f f y ： a v b = ( m a x ( a 。，) ) 一= ( a v ) 。 ( c ) 合取： 4 a b = ( m i n ( a ，) ) 。= ( ) 。 定义2 1 3 设彳= ( 嘞) 。，口= ( ) 。，为模糊矩阵a 称4 b = ( 白) 。，为模糊 矩阵4 和b 的乘积，其中 勺2 m l n a g x ( a ma b e ) 定义2 1 4 设r 和s 为以元集合y = v 。，v 2 ，) 上的模糊关系，对应模糊 矩阵分别为膨( r ) 和m ( 回，则有 ( 1 ) r s 当且仅当m ( r ) m ( $ ( 2 ) m ( r u 研= 肼( 胄) v m ( s ) ( 3 ) m ( r 趵= 吖( 胄) m ( s ) ( 4 ) m ( r o s ) = m ( r ) m ) 注意到，模糊矩阵的运算和布尔矩阵相类似，因为布尔矩阵恰好是特殊的模 糊矩阵，所以，在后面的证明中，我们可以利用矩阵分解定理，把格上的矩阵分 解为布尔代数上的矩阵来研究。 2 2 格 9 北京工业大学理学硕上学位论文 i i 格作为一种理论和数学中一个很有特色的分支，大体上说形成于2 0 世纪的3 0 到4 0 年代，在计算机科学中有广泛的应用。可以看到，格是普通模糊集的一个推 广。格实际上是这样一个偏序集，如果对于任意a ，b 上，子集 口，6 ) 在中都有 上确界和下确界，分别记为s u p a ，b 和i n f a ，。定义了这两种运算后，格也可 以这样定义： 定义2 2 1 工= ( 厶v ， ) 为一个格，这里，l 为任意集合， a i v y = s u p x ，力，x a y = i n f x ，y ) 当且仅当，对任给的a ，b ，c ，d s ，满足下面条件： 1 a v b = b v a ，a a b = b 八a ：( 交换律) 2 a v ( b v c ) = ( a v b ) v c ，a a ( b a c ) = ( a a b ) 八c ；( 结合律) 3 a v ( a a b ) = a ，a 八( a v b ) = a ；( 吸收律) 按照格的不同性质，格又可分为很多种，其中分配格的定义是： 定义2 2 2 设 为一个格，对任给的a ，b ，c l 满足a v ( b a c ) = ( a 八b ) v ( a 八c ) ， a a ( b v c ) = ( a v b ) 八( a v c ) ，则称 为分配格。 这篇文章的部分结论是建立在完全完备分配格( ，v ， ) 上的 1 2 。 定义2 2 3 设= ( 厶v ，、) 为格，是由v 或 诱导的上的偏序关系。 如果满足： ( 1 ) 格上的每个非空子集s 都有一个下确界和一个上确界。 ( 2 ) v x l ，v y ； j ( 兰乃) = 兰o 只) ： 工v ( 全咒) 2 念( x v m ) ( 3 ) v a ，b l ，子集扛l l a a 工b 有最大元，记为a b 则称三为完备b r o u w e r i a n 格，即完全完备分配格。 例如： 令g ，与v ，、) 为整除格( s 。，1 ) ，”z + ，其最小元为1 ，最大元为疗，其中， 运算i 为正整数集z + 的整除关系，x l y 当且仅当x 整除y ， 我们有： 1 0 第2 章预备知识 x v y = l c m x , 刀，x y = g c d ( x ，y ) ，v x ，y z + 易见，其满足完全完备分配格的定义。 此外，任意集合的幂集格也都是完全完备分配格。 分配格上向量的运算： 令：善= 而 工2 ： x n ， ，7 = 定义：善v ，7 = 口f = v 乃 v y 2 ： v y 。 圪( 三) o = ，善a 叩= f = 乃 y 2 y 其中：工= 工0 2 3 格上的矩阵 关于模糊矩阵幂序列的主要研究工作参见 1 - - 6 利用格矩阵幂序列的性 质，可以更清楚的分析格矩阵特征向量的代数结构。这也是这篇文章所要重点论 述的。 首先给出格矩阵及其运算的定义： 格矩阵定义：设l = ( l , v ， ) 为格，l 上全体m n 矩阵构成集合为r ”，记 号彳表示，4 = 0 。) ，l ，i = 1 ，2 ，m ，_ ，= 1 , 2 , - - - , 玎称彳为格l 上的m x 甩矩阵。 格矩阵加法：设三- - ( l ，v ， ) 为格，彳= 0 p ) 一，b = ( 6 f ) e 三一， 定义彳v 丑= ( 嘞v b , ) 称p o 彳与曰的和 格矩阵数乘：v a l ，定义训= ( a a a f ) ，称为口与a 的数乘。 格矩阵乘法：设三= ( 厶v ， ) 为格，a = 0 p ) ，占= ( 6 ，) ， o o ；o 一 ； 屯 矗而屯； 而而 研； 北京工业大学理学硕上学位论文 定义爿b = ( c ，) ”为矩阵a 和曰的乘积，其中： 气。品钆 ，扛i ，2 ，埘，。1 ，2 ，3 格矩阵集合偏序关系： 设三= ( 厶v ， ) 为格，为三上的偏序关系，4 = o ，) ，b = p ，) 矿”， 如果口，( 扛l ，2 ，m ，= 1 , 2 ，一) 则称彳不大于历记为彳b 如果4 b ，且存在“，- ，。，有 则称爿小于夙记为a b 如果爿b ，且b a ，则称a 等于层记为a = b 很明显，格矩阵的运算具有以下性质： w ，b ，c m 。( ) ， 有：( 1 ) a ( b v c ) = a b v a c ( 2 ) f b v c ) a = b a v c a ( 3 ) a ( 8 a c 、a b a a c ( 4 ) ( 口 c ) 一b a a c a ( 5 ) ( 4 b ) c = a ( s c ) ( 6 ) 4 b j a c b c 且c a c b 本文是利用矩阵幂序列的一些性质来求解特征向量的。 定理2 3 1l 为格，则三上的矩阵乘法满足结合律当且仅当l 为分配格。 证明：只证明必要性。v x ，y ，z l 取c x a y a z 令 彳= ( ： ，曰= ( ；：) ，c = ( ：) 有 4 曰= ( x ：y ：) ，b c = i x a z ： ， c 4 b ，c = ( x v ： 2 ： ，彳c b c ，= ( 工 y ：。 z ) ： 由矩阵乘法满足结合律有 1 2 o v 力a z = o a z ) v o a 力，v x , y , z l 即a 对v 有分配律成立，再由格的对偶原理， 对v 也有分配律，即三为分 配格。 推论2 3 1 设三为分配格，a f ”，则一“= 爿a7 由定理2 3 1 ，可以在分配格上定义矩阵的幂序列。 定义2 3 1 设为分配格，a 上，定义a 1 = a ，a = a h 彳，v k 2 ，称 卅) 。为一的幂序列。 定理2 3 2 设三为分配格，则w 上掣，都存在正整数和只使得 a “，= 一，v k k 其中，最小正整数和p 分别称为a 的收敛指数和周期指数。 定理说明：分配格上的任意方阵要么是收敛的，要么是振荡的。 2 4 格矩阵方程 后面定理的证明要涉及到格矩阵的方程，特别是计算最大解的问题，所以这 里简要介绍一下格矩阵方程的一些性质。本节定理都是建立在完全完备分配格 上，见定义2 2 3 。 定义2 4 1 设一= ( 口f ) ，b = ) 工_ ，记一o b = ) ，其中 巳2 金吩“6 i o = l ，帕，称爿。口为似= 曰的形式最大解。 引理2 4 1 设一，b ，且方程a x = b 设x 为方程肛= b 的 任一解，则有x 彳o b 证明：因为a x = b 越= 骂，扛1 , 2 ，m ，因此不失一般性，我们只讨 论b r 的情形即可。设彳= ( 口。) p ”，b = ) p ，设 x = “，工2 ，) 7 是方程五y = b 的解。即h v a ，a x j 2 包，i = l ，2 ，m 则对任意给定的j ( 1 j 坊有 匆= 苫口业 黾口fa x j ，f = 1 ，刀 北京工业大学理学硕上学位论文 则 x a f0 ( 2 玩，i = 1 , 2 ，玎 所以 _ 全( “t ) 证毕。 引理2 4 2 对任意的a p “，b ，有a ( a o 研b 证明：记a o b = ( c ，) ，则任给m i 脚) ，有 v ( a p c ) 2 二a ( 。a a ，“以) o ，1 ，茎珂 为 d ( 彳) 的边集。有向边“，_ ) 的权定义为以 ) = 嘞v ( q ，_ ) e 定义2 5 2 d ( 爿) 中的通路l 的容量记为 国( 工 ) ，或简记为( 工) ，其中： m ( 上 ) = 4 嵋a a i d a a 口k l ， 引理2 5 1 设图d 中的通( 回) 路l 可分解为通( 回) 路厶和厶之和，则 ( 三) = 出( 厶+ 三2 ) = m ( 厶) a 国( 厶) 很明显，1 1 阶格矩阵a 的有向伴随图d ( a ) 中任意初级通路的长度都不大于 n - 1 ，而任意初级回路的长度都不大于n ，即，任意长度大于玎一1 的通路都可分 解成一条初级通路与若干初级回路的和，而任意回路或是初级回路或是初级回路 的和。 下面的定理揭示出了格矩阵的幂序列与其伴随图之间的内在联系。 定理2 5 1 设三 为分配格，a = ( 露) 为工上的矩阵4 的幂序 列。任给正整数盂，任给( f ，)