Oct.2015
CHINESE JOURNAL
OF ENGINEERING MATHEMATICS
Vol.32No.5
doi:10.3969/j.issn.1005-3085.2015.05.014Article ID:1005-3085(2015)05-0772-11
The Maximal SNS-pattern Matrix
for a Signed Digraph?
MOU Gu-fang1,2,HUANG Ting-zhu1
(1-School of Mathematical Sciences,University of Electronic Science and
Technology of China,Chengdu611731;2-College of Mathematics and
Information Science,Leshan Normal University,Leshan614000)
Abstract:For an asymmetric sign pattern matrix P,we analyze the sign characteristic of P with the help of a signed digraph in this paper.The maximal SNS-pattern matrix
for a signed digraph is the maximal sign-nonsingular sub-pattern among all real
matrices having the given sign pattern P.In this paper,SNS problems for signed
digraphs are studied by converting a signed digraphΓinto a signed bipartite graph
G(U,V).We propose the algorithms for searching for a sub-signed bipartite graph
G(U′,V′)with the maximum perfect matching M′corresponding to every set of
disjoint M′-interlacing cycles,which contain an even number of M′-interlacing e-
cycles.The maximal SNS-pattern for a signed digraph is obtained according to
algorithms.
Keywords:SNS-pattern matrix;signed digraph;signed bipartite graph;matching;determ-inant
Classi?cation:AMS(2000)05C50CLC number:O157.6
Document code:A
1Introduction
The maximal SNS-pattern is to determine the maximal sign-nonsingular sub-pattern among all asymmetric real matrices whose sign pattern P is described by a signed di-graphΓ.The problem has been studied extensively[1-3].In[1],the characterization of SNS-pattern by analyzing square sign patterns and giving a graph-theoretic test to count the number of positive and negative signs in determinants expansions was stud-ied.There is a complete and satisfying theory which associates a digraph to a square sign pattern and a test which determines if the sign pattern is SNS[4].Signs in de-terminants expansions for sign patterns are of interest for chemical reaction networks such as[3,5,6].In[7],the SNS number to usefully generalize triangle number to sign
Received:15Jan2015. Accepted:04June2015.Biography:Mou Gufang(Born in1981),Female,Doctor,Lecturer. Research?eld:combinatorial matrix theory.
?Foundation item:The National Natural Science Foundation of China(61170309).