Sign-nonsingular matrices and even cycles in directed graphs (Q1073811)

A real \(m\times n\) matrix A is called a sign-nonsingular matrix or L- matrix if the columns of any real \(m\times n\) matrix with the same sign pattern as A are linearly independent. The author investigates square L- matrices using graph-theoretic methods. For, given any \(n\times n\) L- matrix \(A=(a_{ij})\), a digraph D(A) can be associated with A as follows: D(A) has vertices \(v_ i\) \((i=1,...,n)\) and \(v_ iv_ j\) is an arc in the digraph of \(a_{ij}\neq 0\), \(i\neq j\). Now the arc \(v_ iv_ j\) can be given a weight of 1 if \(a_{ij}>0\) and 0 if \(a_{ij}<0\). Then A is an L-matrix if and only if D(A) has no cycle of even weight. Maximum number of nonzero matrix entries is counted and the digraphs of the extremal cases identified. Complete characterizations are given for two types of L-matrices. Finally, there is a brief discussion of polynomial-time algorithms for recognizing certain classes of L- matrices.