Completions of inverse M-matrix patterns

✍ Scribed by Leslie Hogben

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

✦ Synopsis

A list of positions in an i1 x n real matrix that includes all diagonal positions (a pattern) is said to have inverse M-completion if every partial inverse M-matrix that specifies exactly these positions can be completed to an inverse M-matrix. Johnson and Smith (C.R. Johnson, R.L. Smith, Linear Algebra and its Applications 241-243 (1996) 655-667) characterize the positionally symmetric patterns that have inverse M-completion as those patterns whose graphs are block-clique. In this paper the restriction of positional symmetry is removed: A pattern has inverse M-completion if and only if the digraph G of the pattern has the properties (a) the induced subdigraph of a cycle is a clique, and (b) if G contains both arc (i,j) and a path of length >1 between i and j then the induced subdigraph of the path is a clique. Furthermore, any irreducible pattern with ioverse M-completion is positionally symmetric and has a block-clique digraph. Any pattern is permutation similar to a block-lower-triangular pattern with irreducible diagonal blocks, and such a pattern has inverse M-completion if and only if (i) the pattern-digraph ,of each diagonal block is block-clique, (ii) each subdiagonal block contains at most one position, and (iii) the pattern-digraph of the block structure has no alternate path to a single arc.