Mixed dominating matrices

DOI10.1016/S0024-3795(97)00239-5MaRDI QIDQ1377507zbMATH OpenFDO

Authors Klaus G. Fischer, Jay Shapiro, Walter Morris

Publication date 2 June 1998

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0024-3795(97)00239-5

zbMATH Keywords

Gale transformL-matricesmixed dominating matricesnonnegative vectorspolynomial-time algorithmS-matricessign-solvability

Mathematics Subject Classification ID

Hermitian, skew-Hermitian, and related matrices (15B57)

Review text

The authors characterize matrices for which the set of supports of nonnegative vectors in the null space can be determined by the signs of the matrix. This characterization is in terms of mixed dominating matrices, which are defined by the nonexistence of square submatrices that have nonzeros of opposite sign in each row. The class of mixed dominating matrices is contained in the class of L-matrices from the theory of sign-solvability, and generalizes the class of S-matrices. The authors give a polynomial-time algorithm to decide if a matrix is mixed dominating. They derive combinatorial conditions on the face lattice of a Gale transform of a matrix in this class. Theorem 2.9 is the key to a polynomial-time for recognizing mixed dominating matrices.

Recommendations

• Signsolvability revisited
• scientific article; zbMATH DE number 510841
• Recursive structure of S-matrices and an O(m^ 2) algorithm for recognizing sign solvability
• Sign-central matrices

Cites work

• 25 pretty graph colouring problems
• Affine semigroup rings that are complete intersections
• scientific article; zbMATH DE number 493147 (Why is no real title available?)
• scientific article; zbMATH DE number 825098 (Why is no real title available?)
• scientific article; zbMATH DE number 4197753 (Why is no real title available?)
• Mixed matrices and binomial ideals
• On complete intersection affine semigroups
• On the Addressing Problem for Loop Switching
• Rectangular \(L\)-matrices
• Recursive structure of S-matrices and an O(m^ 2) algorithm for recognizing sign solvability
• Sign-central matrices
• Signsolvability revisited
• Sous-monoïdes d'intersection complète de N

Cited in

(11)

• Linear systems with signed solutions
• Acyclic digraphs giving rise to complete intersections
• Sign conditions for the existence of at least one positive solution of a sparse polynomial system
• Canonical heights of toric subvarieties
• Matrices defining Gorenstein lattice ideals
• Graphs and complete intersection toric ideals
• Complete intersections in toric ideals
• When lattice bases are Markov bases
• On matrices which have signed null-spaces
• Counting solutions to binomial complete intersections
• Sign-solvable linear complementarity problems

This page was built for publication: Mixed dominating matrices

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