Deterministic inverse zero-patterns

DOI10.1016/S0166-218X(00)00384-XMaRDI QIDQ5951964zbMATH OpenFDO

Authors Charles R. Johnson, Michael Lundquist, Thomas J. Lundy, John S. Maybee

Publication date 11 June 2002

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00384-X

zbMATH Keywords

chordalityconnected digraphsdirected graphGaussian eliminationinvertible completionsinvertible matrixmatrix completionundirected graphvertex separator

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inverse problems in linear algebra (15A29)

Review text

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.

Recommendations

• Matrices with chordal inverse zero-patterns
• scientific article; zbMATH DE number 2067015
• Completions of inverse M-matrix patterns
• Determinantal formulae for matrices with sparse inverses. II: Asymmetric zero patterns
• scientific article; zbMATH DE number 5260713

Cites work

• Algebraic characterizations of chordality
• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Determinantal formulae for matrix completions associated with chordal graphs
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• Inverses of banded matrices
• Local inversion of matrices with sparse inverses
• Matrices with chordal inverse zero-patterns
• On rigid circuit graphs
• Positive definite completions of partial Hermitian matrices
• Uniformly one-connected matrices and their inverses

Cited in

(5)

• Determinantal formulae for matrices with sparse inverses. II: Asymmetric zero patterns
• Inverse invariant zero-nonzero patterns
• Sparse matrix decompositions and graph characterizations
• Matrices with chordal inverse zero-patterns
• Matrix inversion and digraphs: the one factor case

This page was built for publication: Deterministic inverse zero-patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5951964)