Algorithmic detection and construction of N-matrices

DOI10.1016/J.LAA.2020.04.028MaRDI QIDQ2185838zbMATH OpenOpenAlexFDO

Authors Projesh Nath Choudhury, M. Tsatsomeros

Publication date 5 June 2020

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

Full work available at URL https://arxiv.org/abs/2001.06761

zbMATH Keywords

almost P-matrixN-matrixP-matrixprincipal minorprincipal submatrixSchur complement

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Factorization of matrices (15A23) Positive matrices and their generalizations; cones of matrices (15B48) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Abstract: N-matrices are real $nimesn$ matrices all of whose principal minors are negative. We provide (i) an $O(2^n)$ test to detect whether or not a given matrix is an N-matrix, and (ii) a characterization of N-matrices, leading to the recursive construction of every N-matrix.

Review text

A real \(n \times n\) matrix is called an N-matrix if all the principal minors of \(A\) are negative. N-matrices form an important matrix class due their connection to univalence theory and the linear complementarity problem. Here, the authors provide an \(\mathcal{O}(2^n)\) test to detect whether or not a given matrix is an N-matrix. A characterization of N-matrices is then presented. This leads to their recursive construction.

Recommendations

• N-matrices
• N-matrices
• A recursive test for P-matrices
• The completion problem for N-matrices
• N-matrix completion problem.

Cites work

• A generalization of N-matrices
• A recursive test for P-matrices
• Almost N-matrices and linear complementarity
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• scientific article; zbMATH DE number 1506179 (Why is no real title available?)
• scientific article; zbMATH DE number 6890171 (Why is no real title available?)
• Inverse \(N_ 0\)-matrices
• Mapping and preserver properties of the principal pivot transform
• Matrix Positivity
• N-matrices
• On characterizing N-matrices using linear complementarity
• Principal pivot transforms: Properties and applications
• Some Aspects of the Theory of PN-Matrices
• Some characterizations of totally nonpositive (totally negative) matrices
• Some matrix inequalities
• The P-matrix problem is co-NP-complete
• The Production Coefficient Matrix and the Stolper-Samuelson Condition

Cited in

(6)

• On testing nonnegativity of principal minors of \({\mathbf{Z}} \)-matrices using simplex method
• Interval hulls of \(N\)-matrices and almost \(P\)-matrices
• scientific article; zbMATH DE number 5189315 (Why is no real title available?)
• N-matrices
• A recursive algorithm for constructing complicated Dixon matrices
• A polynomial-time test for M-matrices

This page was built for publication: Algorithmic detection and construction of N-matrices

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