On digraphs and forbidden configurations of strong sign nonsingular matrices

✍ Scribed by Jia-Yu Shao

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 764 KB
• Volume: 282
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(98)10063-0

✦ Synopsis

A square real matrix A is called a strong sign nonsingular matrix (or "S2NS "" rnatrixl if all matrices with the same sign pattern as A are nonsingular and lhe inverses of these matrices all have the same sign pattern. A digraph which is the underlying digraph of the signed digraph of an S"NS matrix (with a negative main diagonal) is called an S'-NS digraph. In [9], Thomassen gave a characterization of strongly connected S'-NS digraphs in terms of the forbidden subdigraphs, in [2], Brualdi and Shader constructed minimal forbidden configurations for S"NS digraphs for the general cases where the digraphs considered are not necessarily strongly connected. They also proposed the problem about the existence of new m~nimal forbidden configurations other than those found in [2,9]. in this paper, we construct infinitely many new (basic) minimal forbidden conligurations and thus obtain the answer to this problem. We also obtain several necessary conditions for minimal forbidden configurations and give a generalization of Thomassen's Theorem.