Deterministic inverse zero-patterns (Q5951964)

For an \(n \times n\)-matrix \(A\) given by a collection of positions in \(A\) and for an \(n \times n\)-matrix \(B\) given by another collection of positions in \(B\) the following problem is studied. When does it happen that for each set of values for the entries in all these positions there is at most one completion of \(A\) and \(B\) such that \(B=A^{-1}\)? NEWLINENEWLINENEWLINEIn this work the case in which positions in \(A\) include the diagonal positions, the positions in \(B\) are the complement of those in \(A\) and the values of all ``specified'' entries of \(B\) are \(0\) is studied. In such a case, the positions in \(A\) may be described by a directed graph \(D\), which contains all the combinatorial information about the problem. The case in which \(D\) is essentially an undirected graph because the specified entries of \(A\) occur in symmetrically placed positions is already well known and uniqueness occurs if and only if \(D\) is chordal. An analysis of the directed case naturally means generalization of the notion of chordality to directed graphs. NEWLINENEWLINENEWLINEHere, even several natural directed generalizations of chordality including one that has been previously studied in the context of Gaussian elimination are given. It is shown, for strongly connected digraphs, that all these generalizations are sufficient for uniqueness of invertible completions with \(0\)'s in the correct places. All of them are contained in one general class of digraphs that may characterize uniqueness of invertible completions.