Sign-nonsingular skew-symmetric matrices (Q1915617)

A real matrix \(A\) is called ``sign-nonsingular'' if each matrix with the same sign patterns as \(A\) is nonsingular. This paper considers the problem of characterizing sign-nonsingular skew-symmetric matrices; evidently it is enough to consider matrices whose only entries are 0, 1, \(-1\). Since any skew-symmetric matrix with an odd number of rows and columns is singular, the only case of interest is where \(A\) has an even number of rows and columns. Every skew-symmetric \((0, 1, -1)\)-matrix \(A\) is the adjacency matrix of a digraph obtained by orienting the edges of some graph \(G\). Conversely, a graph \(G\) is called ``nonsingular'' if at least one of the matrices \(A\) derived in this way from \(G\) is sign-nonsingular; \(G\) is ``maximal nonsingular'' if, in addition, none of the graphs obtained from \(G\) by inserting a new edge between two previously nonadjacent vertices is nonsingular. The author proves a number of results on sign-nonsingular skew-symmetric matrices and the related graphs. The following are typical. In Theorem 2.3 it is shown that a graph \(G\) is nonsingular if and only if: (i) the number of perfect matchings for \(G\) is nonzero and equal to the Pfaffian of one of the skew-symmetric matrices \(A\) derived from \(G\); and (ii) whenever a spanning subgraph \(H\) of \(G\) has components which are either cycles or single edges, none of the cycles is odd. In Theorem 4.8 it is shown that for any maximal nonsingular graph \(G\) with \(2n\) vertices and \(e\) edges we have: \(e\geq 3n\) if each vertex has degree at least 3; \(e\geq 3n+2\) if \(G\) has a vertex of degree 2; and \(e\geq 5n -4\) if \(G\) has a vertex of degree 1. The latter theorem strengthens a result of \textit{R. A. Brualdi} and \textit{B. L. Shader} [Ser. Discret. Math. Theor. Comput. Sci. 4, 117-134 (1991; Zbl 0742.15001)].