Deterministic inverse zero-patterns (Q5951964)
From MaRDI portal
scientific article; zbMATH DE number 1687490
Language | Label | Description | Also known as |
---|---|---|---|
English | Deterministic inverse zero-patterns |
scientific article; zbMATH DE number 1687490 |
Statements
Deterministic inverse zero-patterns (English)
0 references
11 June 2002
0 references
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}\)? In 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. Here, 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.
0 references
directed graph
0 references
chordality
0 references
invertible matrix
0 references
vertex separator
0 references
matrix completion
0 references
undirected graph
0 references
invertible completions
0 references
Gaussian elimination
0 references
connected digraphs
0 references