【作者】 贺金陵；

【导师】 邵嘉裕；

【作者基本信息】 同济大学 ， 基础数学， 2006， 博士

【摘要】 本文主要分两个部分，第一个部分是与广义逆符号唯一阵相关问题的研究，主要包含在第二，第三以及第四章中；第二部分是关于树的拉普拉斯特征值的部分和的可达上界问题，即第五章。符号矩阵理论是组合矩阵论的一个新兴研究分支，是近年来在组合数学中较为活跃的一个研究方向。该理论主要研究矩阵的仅与其符号模式有关的定性性质。符号矩阵理论最早起源于经济学中对某些问题的定性性质的研究。其开创性工作是由诺贝尔奖获得者、经济学家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》一文中研究最小二乘符号可解方程组时，引入了广义逆符号唯一阵的概念。它与S²NS阵、最小二乘符号可解方程组有着密切的关系，是S²NS阵概念的推广。在专著《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所提的公开问题。在第二章中，我们研究了具有特殊逆符号模式的S²NS矩阵（其逆非负，非正，全负，全正，无零元）特征刻画的问题（文献[30]）。并且进一步研究S²NS矩阵的推广，即广义逆符号唯一阵。讨论何时一个矩阵A既是广义逆符号唯一阵又满足其广义逆非负（非正，全负，全正，无零元）?通过引入CC-矩阵，CR-矩阵以及RR-矩阵的概念，利用代数与图论相结合的方法给出了上述问题的完全刻画。1994年，R.A.Brualdi，K.L.Chavey和B.L.Shader在文献[7]中研究了完全不可分的极大S²NS矩阵的非零元个数的问题，并且得到了如下结果：n阶完全不可分的极大S²NS矩阵的非零元个数为3n-2。在本文第三章中，我们继续研究非零元个数的问题（文献[31]），考虑了一般的S²NS矩阵A的非零元个数的上界的问题（下界显然是n，且等号成立当且仅当A的每一行每一列恰有一个非零元），并且进一步考虑广义逆符号唯一阵（S²NS矩阵概念的推广）的非零元个数的上界（下界显然为0），分列满项秩和列不满项秩两个情形给出了上界的刻画。在第二章中，关于S²NS阵和广义逆符号唯一矩阵，我们给出了一个实矩阵A是S²NS阵（或广义逆符号唯一阵）且其逆（或广义逆）非正的特征刻画，在第四章中我们研究该问题的反问题，即如下的两个问题：问题1：给定一个n阶符号模式矩阵N≤0，是否存在S²NS阵A使得sgn(A^-1)=N?问题2：给定一个符号模式矩阵N_m×n≤0，是否存在广义逆符号唯一阵A使得sgn（A⁺）=N?同时给出了上面两个问题的特征刻画。设G是一个图，令d_i（G）表示G的第i大的度，即有d₁（G）≥d₂（G）≥…≥d_n（G），图G的拉普拉斯矩阵定义为L（G）=D（G）-A（G），其中D=D（G）=diag（d（v₁），d（v₂），…，d（v_n））是图G的度对角矩阵。容易证明L（G）是一个半正定的、对称的实矩阵且它的每一行的行和为零，因此，L（G）又是奇异的。从而，我们可以假设它的特征值按照从大到小的顺序排列为：μ₁（G）≥μ₂（G）≥…≥μ_n（G）=0，且称μ_k（G）为图G的第k大的拉普拉斯特征值。特别地，称μ₁（G）为图G的拉普拉斯谱半径，记为μ（G）。矩阵L（G）的谱称为G的拉普拉斯谱，记作Spec（G），即Spec（G）={μ₁（G），μ₂（G），…，μ_n（G）}。1994年，R.Merris和R.Grone在文献[59]以及[60]中考虑了拉普拉斯特征值的部分和的下界的问题：如果G是至少含有一条边的图，则：μ₁（G）≥d₁（G）+1。如果G是一个至少有两个点的连通图，则有μ₁（G）+μ₂（G）≥d₁（G）+d₂（G）+1，μ₁（G）+μ₂（G）+μ₃（G）≥d₁（G）+d₂（G）+d₃（G）+1。在文献[59]以及[60]中，R.Merris和R.Grone提出了如下的猜想：对于任意的k，sum from i=1 to kμ_i（G）≥sum from i=1 to k d_i（G）+1。在第五章中我们考虑研究一类特殊的图：树的拉普拉斯特征值的部分和的上界问题，同时说明该上界是可达的。即如下的结论：设T是有n≥2个顶点的树，则有sum from i=1 to kμ_i（T）≤n+sum from i=2 to k d_i（T），（2≤k≤n-1），且当T=K_1，n-1时等式成立。更多还原

【Abstract】 In this paper, we study some related topics on the matrices with signed gen-eralized inverses in signed matrix theory, we also presents an attainable upperbound for the sum of the first k Laplacian eigenvalues of a tree in Chapter 5.Signed matrix theory is a new branch of combinatorial matrix theory, whichinvolves the study of the properties of matrices that depend only on the signpattern of the matrices. The subject, started by the Nobelist P.Samuelson whois an economist, is usually considered to have originated with the discussion on"qualitative properties" of some problems in economics （see[16]）. Because ofits great importance in economics, it has been paid wide attention by many re-searchers including economists, mathematicians and theoretical computer scien-tists. In 1995, R.A.Brualdi and B.L.Shader’s book《Matrices of sign-solvable lin-ear systems》（[5]） was published, which is the first monograph on signed matrixtheory. In this book, they systematically summarized the results on the subjectand gave many new results. It makes signed matrix theory being an active areaof combinatorics.In 1995, the notion of matrices having signed generalized inverses was firstintroduced in [17] in the study of the least square sign-solvability of linear systemsof equations. It has close relationship with S²NS matrix and the least square sign-solvability of linear systems of equations. It is also a generalization of the conceptof S²NS matrix. R.A.Brualdi and B.L.Shader proposed an interesting questionabout the characterizations of the matrices which have a special lower triangularblocked form to have signed generalized inverse in [5, 17].In 2002, based on the work of [22], by using sign majorizations, graph theoret-ical techniques, Jia-Yu Shao and Hai-Ying Shan first settled the remaining casesof the case k=2 of R.A.Brualdi and B.L.Shader’s question. By introducing theconcept of a "standard order" T^*-type matrix and using a combination of graphtheoretical methods, algebraic methods they obtain several important results.Thus they get characterizations of the matrices with a special lower triangularblocked form to have a signed generalized inverses, so the problem proposed in [5,17] is solved.A real matrix A is said to have a signed generalized inverse （or signed GI）,if the sign pattern of its generalized inverse A⁺ is uniquely determined by thesign pattern of A. in Chapter 2 of this paper, we continue to study the matri-ces with signed generalized inverses, by introducing the concept of CC-matrix,CR-matrix and RR-matrix, we give complete characterizations on those signpattern matrices with signed generalized inverse and the generalized inverse of itis nonnegative or is positive, or has no zeros.In 1994, R.A.brualdi, K.L.Chavey and B.L.Shader consider the number ofnonzero entries of fully indecomposable, maximal S²NS matrices（in [7]） and ob- tain the following result: if A is a fully indecomposable, maximal S²NS of ordern, then N（A）=3n-2. As we all known, the notion of matrices having signed GI’sis a generalization of the well known notion of strong SNS matrices （or S²NS）.in Chapter 3 of this paper, we continue to study the problem, Sharp bounds, andcharacterization of equality for the number of nonzero entries of S²NS matricesof order n are given, we also give sharp bounds and characterization of equalityfor the number of nonzero entries of m×n matrices with signed GI’s.In Chapter 2 of this paper, we characterize those matrices with signed gen-eralizrd inverses and its generalized inverse are nonpositive. In Chapter 4 of thispaper, we continue to investigate the problem and obtain complete characteriza-tion of nonpositive sign pattern matrices N which satisfy the following condition:there exist a real matrix A that has a signed generalized inverse and sgn（A⁺）=N.Another topic of this paper is the study of the upper bound for the sum ofthe first k Laplacian eigenvalues of a tree, first we give the following fundamentalfacts.There are various matrices that are naturally associated with a graph, such asthe adjacency matrix, the incidence matrix, and the Laplacian matrix. Among theabove mentioned matrices of graphs, the most important two are the adjacencymatrix and the Laplacian matrix of graphs.Laplacian matrix has a long history.The most renowned application of the Laplacian matrix L（G） of a graph G isin the following well-known Matrix-Tree-Theorem which is usually attributed toKirchhoff.Matrix-Tree-Theorem: Let G be a graph on n vertices and let L（i|j） be thematrix obtained from L（G）, the Laplacian matrix of the graph G, by deleting thei^th row the j^th column. The absolute value of the determinant of L（i|j） is equalto the number of spanning trees of the graph G.In 1994, R.merris and R.Grone study the lower bound for the sum of the firstk Laplacian eigenvalues of a graph（in [59] and [60]）. As the simplest connectedgraphs, trees usually play a special role in studying some problems in graph theory,in Chapter 5 of this paper, we presents an attainable upper bound for the sum ofthe first k Laplacian eigenvalues of a tree.更多还原