The Matrices With Signed Generalized Inverses And The Laplacian Eigenvalues Of Graphs

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.