复方阵的行列式值域及赋权图的保直径生成树

摘要

本文的研究课题来自于两个方面,分别是复方阵的行列式值域和赋权连通图的保直径生成树。其中复方阵的行列式值域来源于符号可解性理论从实数域向复数域的推广,保直径生成树问题来源于网络设计。
　　 符号可解性理论是为了解决经济学中的定性分析类问题而提出的数学理论,其开创性工作是由诺贝尔经济学奖获得者、经济学家P.Samuelson在1947年作出的。经过半个多世纪的发展,实数域下的符号可解性理论已臻于完善。目前的研究工作集中于该理论从实数域向复数域推广过程中出现的一些新问题。本文涉及的推广有两种,分别是Ray模式推广及复符号模式推广。其中Ray模式推广是由J.J.McDonald等人在1997年引入的,复符号模式推广则是由Eschenbach等人在1998年引入的。
　　 行列式值域是为了研究复推广中矩阵的Ray非异性或复符号非异性而提出的概念。本文的第二至第四章主要研究了矩阵行列式值域的相关性质,包括行列式值域的拓扑性质、拓扑性质与矩阵的代数性质之间的关系、以及两种不同复推广在行列式值域类问题上的关系。第二及第三章中研究的是Ray模式行列式值域,第四章中讨论两种推广在行列式值域类问题中的关系。
　　 确定行列式值域边界的位置有利于理解其拓扑结构。1998年,Eschenbach等人对复符号模式行列式值域提出公开问题:是否复符号非异矩阵的行列式值域的边界都落在轴上?2005年,Shao和Shan正面回答了这个问题,证明了任意复方阵的复符号模式行列式值域的边界都落在坐标轴上。本文的第二章研究了Ray模式行列式值域RA的非0边界,确定了其可能出现的位置。称一个复方阵A的行列式展开式中非0项的Ray所构成的集合为其行列式值域展开基,记为T(A)。我们证明了RA的边界与单位圆的交集bU,(RA)是T(A)的子集。这个结论有一个直观的几何解释:RA是由T(A)生成的锥的子集,而生成锥的边界与单位圆的交集也是T(A)的子集。结合第四章中的结果可知,Shao和Shan在2005年的关于复符号模式行列式值域边界的结论是此结论的一个推论。
　　 复方阵的叶数nR(A)指的是RA＼{0}的连通分支个数。2006年,我们证明了任意复方阵的叶数只能等于0、1和2。其中叶数为0的情形是一种平凡情形,一个复方阵的叶数为0当且仅当其项秩不满。于是满项秩的所有复方阵可以按其叶数自然的分为两类。若称叶数为1的矩阵是第一类矩阵,叶数为2的矩阵是第二类矩阵,则就自然产生了如下的一个分类问题:能否找到判定第一、第二类矩阵的非平凡的充要条件?
　　 本文的第三章中,我们完全解决了这个分类问题,给出了第二类矩阵即叶数为2的矩阵的特征刻画。(这种特征刻画等价的刻画了第一类矩阵,即不是第二类的满项秩矩阵都是第一类的。)为了给出第二类矩阵的特征刻画,我们引入了三种基本矩阵,证明了叶数为2的矩阵都置换等价于这三种基本矩阵的半直和。于是叶数为2的矩阵的识别问题可以转化为对三种基本矩阵的识别问题。文中同时用行列式值域展开基给出了三种基本矩阵的特征刻画,这种特征刻画等价于给出了识别这三种基本矩阵的算法。本章中的结论还说明当叶数为2时,矩阵的行列式值域是可计算的。
　　 在给出叶数为2的矩阵的特征刻画的过程中,我们首先讨论了复方阵的叶数与其部分可分性的关系,证明了当叶数为2且Ray模式行列式值域不是一条经过原点的直线时,矩阵都是部分可分的。证明的过程中我们使用了矩阵的伴随有向图作为工具,引入了圈链的概念,并证明了圈链在强连通有向图中的普遍存在性。1997年,J.J.McDonald等人提出问题:是否存在完全不可分的Ray非异矩阵A,使得0是其行列式值域展开基T(A)的凸包的相对内点,即0∈ri(cone(T(A)))?2000年,G.Y.Lee等给出了两个具体的4阶方阵满足上述性质,正面回答了此问题。作为证明部分可分性结论的副产品,在第三章中我们利用圈链给出了上述问题的一个较一般的例子。
　　 Ray模式推广和复符号模式推广是两种不同方式的推广,但当矩阵中的元素都是实数和纯虚数时,这两种推广方式等价。称所有元素都是实数或纯虚数的矩阵为轴元阵。本文的第四章中引入了复符号模式矩阵规范型的概念。规范型矩阵都是轴元阵。我们证明任意矩阵的复符号模式行列式值域都与其规范型的复符号模式行列式值域相同,进而跟其Ray模式行列式值域相同。此结论说明,复符号模式行列式值域的问题,如第二章中的边界问题等,可以转化为Ray模式行列式值域来考虑,Ray模式行列式值域的所有必要条件对复符号模式行列式值域均成立。此种意义下,我们可以认为Ray模式推广是一种更一般的推广。
　　 生成树问题是网络设计中的一类常见问题,其典型代表是最小生成树问题。直径是表征一个通讯网络最大网络时延的重要参数,性能优良的通讯网络往往要求有较小的直径。在生成树问题中考虑直径这个参数,可得最小直径生成树问题。保直径生成树是一种特殊的最小直径生成树,并不是每一个通讯网络所对应的赋权图都含有保直径生成树。第五章中我们给出了赋权连通图含有保直径生成树的一个简单的充分条件。具体的来说,设G=(V E,fE)是一个赋权连通图,其中fE是边权函数。记fV是由边权函数fE诱导的点权函数,其中fV(v)=max{fE(e):e与v关联)。我们证明若d(G)≥2/3∑v∈V fV(v),则G含有保直径生成树,其中d(G)表示G的直径。有例子表明,条件里的系数2/3是不可改进的。

目录

文摘

英文文摘

第一章 绪论

1.1 符号矩阵理论及其复推广

1.1.1 背景

1.1.2 实数域下的符号矩阵理论

1.1.3 符号矩阵理论在复数域下的推广

1.2 保直径生成树

第二章 Ray模式行列式值域及其边界

2.1 基本定义

2.2 常用术语及已知结果

2.3 Ray模式行列式值域的边界

第三章 叶数为2的Ray模式矩阵的特征刻画

3.1 叶数及其相关性质

3.2 弧赋权伴随有向图

3.3 圈链

3.4 叶数与矩阵部分可分性的关系

3.4.1 开扇角度小于π时的证明

3.4.2 开扇角度等于π时的证明

3.5 叶数为2的Ray模式矩阵的特征刻画

3.5.1 主要结论

3.5.2 三类基本矩阵的特征刻画

第四章 关于复符号模式

4.1 复符号模式推广的相关概念和性质

4.2 复符号模式矩阵的规范型

4.3 复符号模式矩阵类的相关性质

第五章 赋权稀疏连通图的保直径生成树

5.1 背景

5.2 保直径生成树的存在性

致谢

参考文献

索引

个人简历、在读期间发表的论文与研究成果