Complex Extension Of The Symbol Matrix Of Problems And Their Methods Of Graph Theory Research

Sign pattern matrix theory is a new branch of combinatorial matrix theory,which involves the study of the properties of matrices that depend only on thesign pattern of the matrices. The subject, started by the Nobelist P.Samuelsonwho is an economist, is usually considered to have originated with the discussionon "qualitative propertied" of some problems in economics (see [46]). Becauseof its great importance in economics, it has been paid wide attention by manyresearchers including economists, mathematicians and theoretical computer sci-entists. In 1995, R.A.Brualdi and B.L.Shader's book《Matrices of Sign-solvableLinear systems》(see [12])was published, which is the first monograph on signpattern matrix theory. In this book, they systematically summarized the resultson the subject and gave many new results. It makes sign pattern matrix theorybegin an active research area of combinatorics.In this paper, two special topics on the complex generalizations of the signpattern matrix have been studied. One is the ray-solvability of the complex linearsystems with square coefficient matrix; The other is the study on the relationsbetween the DRU matrices (as the complex generalization of SNS matrices) andray S^*- matrices (as the complex generalization of S^*-matrices). We will use thegraph theoretical method to study these pure algebra problems.Recently, the complex generalizations of the sign pattern matrix theory havebecome a heated point concerned by many scholars. Firstly, attention is paidto the complex generalizations of key contents in the study on the sign patternmatrix. These contents include the complex generalizations of the sign solvablelinear systems, complex generalizations of SNS matrices and S^*-matrices whichplay very important roles in the complete solution to the study on the sign solvablelinear systems.In the very beginning of the study on the complex generalizations, ray-nonsingular matrices is the standard complex generalization of SNS matrices.After the study on ray-nonsingular matrices have been carried on, it is foundthat many important characters of SNS matrices do not hold for ray-nonsingularmatrices (especially the graph theoretical characterizations of the SNS matricesand many important relations between the SNS matrices and sign solvable linearsystems). In this instance, people look for other complex generalizations of SNSmatrices. In [26], Shao and Shan introduced another complex generalization ofSNS matrices—DRU matrices, that overcomes the above difficulties, and bringnew developments to the theory of complex generalizations of sign matrices.In this paper, we use DRU matrices as the complex generalization of SNSmatrices and use the graph theoretical method to study the ray-solvable conditionsof the complex linear systems with square coefficient matrix, obtain the followingresults: 1. In§2.3, we obtain the graph theoretical characterizations of totally nonzeroray-solvable complex linear systems with standard square coefficient matrix,and the graph theoretical descriptions of the ray patterns of the solutions ofthese types of linear systems.2. In§2.3, we also obtain the graph theoretical characterizations of totallypositive ray solvable complex linear systems with standard square coefficientmatrix:Let Ax=b and W be the same as in Theorem 3.1, then Ax=b is totallypositive ray solvable if and only if S(A) and W satisfy the following condi-tions:(1). Any ray of a cycle in S(A) is negative.(2). There exists a path from each vertex in S(A) to some vertex in W.(3). All vertices in W are the positive terminus of S(A).On the base of above conclusions, we study on the graph theoretical character-izations of the ray-solvability in a general case, and obtain the main conclusion ofChapter Two—graph theoretical characterizations of general ray solvable complexlinear systems.In Chapter Three, we define the ray digraph that appeared above as the W⁺-ray solvable ray digraph, and research these ray digraphs and their underlyingdigraphs, then we obtain following conclusions:1. For the strongly connected W⁺-ray solvable ray digraph and strongly con-nected W-ray solvable underlying digraph, we obtain their characterizationsdescribed by forbidden subdigraphs.Let D be a strongly connected digraph and w be a given vertex of D, thenthere exists a W-ray solvable ray digraph S with D as its underlying digraphif and only if D contains no subdigraph of the type D_w(see the Fig.1).2. In§3.4, we mainly study the characterizations of W⁺-ray solvable ray di-graph and W-ray solvable ray digraph in the general case (that is to say itmay not be strongly connected)(A): Characterizations of W⁺-ray solvable ray digraphs:Let S be a digraph and W be a nonempty vertex subset of S. Suppose Sand W satisfy the assumptions (A.1)-(A.3) (see the definitions of ChapterThree), then S is W⁺-ray solvable (that is to say the ray of each cycle of S isnegative and all vertices in W are positive terminus) if and only if S satisfiesthe following two conditions:(1). All ray of the arcs that connect two strong component are positive.(2). For each strong component S_i of S, there is a only vertex v_i satisfyingthe following three conditions: (2.1). v_i=w_i for i=1,…, r.(2.2). Each S_i is (strong connected) v_i⁺-ray solvable.(2.3). All arcs in S leaving the component S_i start from v_i.(B): Characterizations of W-ray solvable ray digraphs in the general cases:Let S be a digraph and W be a nonempty vertex subset of S. Suppose Sand W satisfy the assumptions (A.1)-(A.5)(see the definitions of ChapterThree), ray digraph D is defined to be the digraph with vertex set V(D)={d₁,…, d_n} and arc set E={(d_i, d_j)|when there is a arc from S_i to S_j}, ray(d_i, d_j) is equal to the any ray of the path which is from v_i to v_j andthrough an arc from S_i to S_j, then S is W-ray solvable if and only if S satisfythe following two conditions:(1). Any ray of the path from d_i (1≤i≤r) to d_j(1≤j≤r) is positive.(2). All rays of the path from one d_i (i＞r) to any d_j(1≤j≤r) are equal.It is well known that SNS matrices and S^*-matrices which play very im-portant roles in the complete solution to the research on the sign solvable linearsystems are the key contents in the study on the sign pattern matrix.In [5], He and Shah give some sufficient and necessary conditions of exploita-tion from one SNS matrix to S^*-matrix. On the base of that, we use the graphtheoretical method to discuss the relationships between the DRU matrices (as thecomplex generalization of SNS matrices) and ray S^*- matrices (as the complexgeneralization of S^*-matrices) in Chapter Four, and get following conclusions:1. In§4.3, we discuss the exploitation from one DRU matrix to a ray S^*-matrix in the strongly connected cases, get following conclusions:(A): A is a fully indecomposable DRU matrix, S is the ray digraph of thematrix A, w is any one vertex in S, if S contains no subdigraph of type D_w, b is a column vector whose unique nonzero entry is at its w-row, then (A, b)is a ray S^*- matrix.Therefore, any fully indecomposable DRU matrix A can be exploited to aray S^*- matrix.(B): A is a fully indecomposable DRU matrix, S is the ray digraph of thematrix A, then the sufficient and necessary condition of that A can be ex-ploited to a ray S^*- matrix is that S contains a vertex w, such that S containsno subdigraph of type D_w.2. In§4.4, we discuss the exploitation from one DRU matrix to a ray S^*-matrix in general cases, and get some sufficient and necessary conditions.