广义逆符号唯一阵与图的拉普拉斯特征值

论文摘要

本文主要分两个部分，第一个部分是与广义逆符号唯一阵相关问题的研究，主要包含在第二，第三以及第四章中；第二部分是关于树的拉普拉斯特征值的部分和的可达上界问题，即第五章。符号矩阵理论是组合矩阵论的一个新兴研究分支，是近年来在组合数学中较为活跃的一个研究方向。该理论主要研究矩阵的仅与其符号模式有关的定性性质。符号矩阵理论最早起源于经济学中对某些问题的定性性质的研究。其开创性工作是由诺贝尔奖获得者、经济学家P. Samuelson作出的（参见文献[16]）。由于符号矩阵理论在经济学中有着重要的应用背景，从而引起了经济学家，数学家及计算机理论专家的广泛关注。1995年，R.A.Brualdi与B.L.Shader的关于符号矩阵论的专著《Matrices of Sign-solvable Linear Systems》（[5]）的问世极大地推动了符号矩阵理论的发展，它全面系统地总结了在符号矩阵理论方面的研究成果，同时给出了许多新的结论，从而使符号矩阵理论成为组合数学的一个新兴的研究热点。1995年，B.L.Shader在《Least Squares Sign-solvability》一文中研究最小二乘符号可解方程组时，引入了广义逆符号唯一阵的概念。它与S2NS阵、最小二乘符号可解方程组有着密切的关系，是S2NS阵概念的推广。在专著《Matrices of Sign-solvable Linear Systems》及《Least Squares Sign-solvability》一文中，R.A.Brualdi与B.L.Shader提出了一个关于有特定的三角分块形式矩阵是广义逆符号唯一阵的特征刻划的公开问题。2002年，J.Y.Shao和H.Y.Shan在《The solution of a problem on matrices having signed generalized inverses》一文中解决了R.A.Brualdi和B.L.Shader所提的公开问题在k=2时的情形，并且通过引入标准序的T*形矩阵，使用代数，图论相结合的方法给出了广义逆符号唯一矩阵的特征刻划。最终完全解决了R.A.Brualdi和B.L.Shader所提的公开问题。在第二章中，我们研究了具有特殊逆符号模式的S2NS矩阵（其逆非负，非正，全负，全正，无零元）特征刻画的问题（文献[30]）。并且进一步研究S2NS矩阵的推广，即广义逆符号唯一阵。讨论何时一个矩阵A既是广义逆符号唯一阵又满足其广义逆非负（非正，全负，全正，无零元）?通过引入CC-矩阵，CR-矩阵以及RR-矩阵的概念，利用代数与图论相结合的方法给出了上述问题的完全刻画。1994年，R.A.Brualdi，K.L.Chavey和B.L.Shader在文献[7]中研究了完全不可分的极大S2NS矩阵的非零元个数的问题，并且得到了如下结果：n阶完全不可分的极大S2NS矩阵的非零元个数为3n-2。在本文第三章中，我们继续研究非零元个数的问题（文献[31]），考虑了一般的S2NS矩阵A的非零元个数的上界的问题（下界显然是n，且等号成立当且仅当A的每一行每一列恰有一个非零元），并且进一步考虑广义逆符号唯一阵（S2NS矩阵概念的推广）的非零元个数的上界（下界显然为0），分列满项秩和列不满项秩两个情形给出了上界的刻画。在第二章中，关于S2NS阵和广义逆符号唯一矩阵，我们给出了一个实矩阵A是S2NS阵（或广义逆符号唯一阵）且其逆（或广义逆）非正的特征刻画，在第四章中我们研究该问题的反问题，即如下的两个问题：问题1：给定一个n阶符号模式矩阵N≤0，是否存在S2NS阵A使得sgn(A-1)=N?问题2：给定一个符号模式矩阵Nm×n≤0，是否存在广义逆符号唯一阵A使得sgn（A+）=N?同时给出了上面两个问题的特征刻画。设G是一个图，令di（G）表示G的第i大的度，即有d1（G）≥d2（G）≥…≥dn（G），图G的拉普拉斯矩阵定义为L（G）=D（G）-A（G），其中D=D（G）=diag（d（v1），d（v2），…，d（vn））是图G的度对角矩阵。容易证明L（G）是一个半正定的、对称的实矩阵且它的每一行的行和为零，因此，L（G）又是奇异的。从而，我们可以假设它的特征值按照从大到小的顺序排列为：μ1（G）≥μ2（G）≥…≥μn（G）=0，且称μk（G）为图G的第k大的拉普拉斯特征值。特别地，称μ1（G）为图G的拉普拉斯谱半径，记为μ（G）。矩阵L（G）的谱称为G的拉普拉斯谱，记作Spec（G），即Spec（G）={μ1（G），μ2（G），…，μn（G）}。1994年，R.Merris和R.Grone在文献[59]以及[60]中考虑了拉普拉斯特征值的部分和的下界的问题：如果G是至少含有一条边的图，则：μ1（G）≥d1（G）+1。如果G是一个至少有两个点的连通图，则有μ1（G）+μ2（G）≥d1（G）+d2（G）+1，μ1（G）+μ2（G）+μ3（G）≥d1（G）+d2（G）+d3（G）+1。在文献[59]以及[60]中，R.Merris和R.Grone提出了如下的猜想：对于任意的k，sum from i=1 to kμi（G）≥sum from i=1 to k di（G）+1。在第五章中我们考虑研究一类特殊的图：树的拉普拉斯特征值的部分和的上界问题，同时说明该上界是可达的。即如下的结论：设T是有n≥2个顶点的树，则有sum from i=1 to kμi（T）≤n+sum from i=2 to k di（T），（2≤k≤n-1），且当T=K1，n-1时等式成立。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景与问题
• 第2章 具有特殊广义逆符号模式的广义逆符号唯一阵
• 2.1 引言
• 2NS矩阵'>2.2 具有特殊逆符号模式的S²NS矩阵
• 2.3 广义逆为非负（或为正）的广义逆符号唯一阵
• 2.4 广义逆无零元的广义逆符号唯一阵
• 2NS阵以及广义逆符号唯一阵的非零元个数的界'>第3章 S²NS阵以及广义逆符号唯一阵的非零元个数的界
• 2NS矩阵的非零元个数的界'>3.1 S²NS矩阵的非零元个数的界
• 2NS矩阵的一个性质的推广'>3.2 S²NS矩阵的一个性质的推广
• 3.3 广义逆符号唯一矩阵的非零元个数的界
• 第4章 关于广义逆符号唯一阵其逆的非正符号模式问题
• 4.1 问题的背景及已有结果
• 4.2 主要结论
• 第5章 树的拉普拉斯特征值的部分和的可达上界
• 5.1 引言
• 5.2 主要结果
• 参考文献
• 个人简历 攻读博士学位期间的研究成果
• 致谢