Combinatorial characterizations of K-matrices

DOI10.1016/J.LAA.2010.08.008MaRDI QIDQ609481zbMATH OpenOpenAlexFDO

Authors Jan Foniok, Komei Fukuda, Lorenz Klaus

Publication date 1 December 2010

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

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

zbMATH Keywords

oriented matroid\(P\)-matrixlinear complementarity\(Z\)-matrix\(K\)-matrix

Mathematics Subject Classification ID

Positive matrices and their generalizations; cones of matrices (15B48) Oriented matroids in discrete geometry (52C40) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Abstract: We present a number of combinatorial characterizations of K-matrices. This extends a theorem of Fiedler and Ptak on linear-algebraic characterizations of K-matrices to the setting of oriented matroids. Our proof is elementary and simplifies the original proof substantially by exploiting the duality of oriented matroids. As an application, we show that a simple principal pivot method applied to the linear complementarity problems with K-matrices converges very quickly, by a purely combinatorial argument.

Recommendations

• A finite characterization ofK-matrices in dimensions less than four
• Complementarity in Oriented Matroids
• LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
• Karamardian matrices: an analogue of \(Q\)-matrices
• Pivoting in linear complementarity: Two polynomial-time cases

Cites work

• scientific article; zbMATH DE number 3156382 (Why is no real title available?)
• scientific article; zbMATH DE number 3159112 (Why is no real title available?)
• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 3508258 (Why is no real title available?)
• scientific article; zbMATH DE number 3212891 (Why is no real title available?)
• A Partition Theorem for Euclidean n-Space
• A Probelm in Linear Inequalities
• A correction to a result in linear programming
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• Bimatrix Equilibrium Points and Mathematical Programming
• Complementarity in Oriented Matroids
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Good hidden \(P\)-matrix sandwiches
• LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
• NP-completeness of the linear complementarity problem
• On the complexity of polyhedral separability
• On the number of solutions to the complementarity problem and spanning properties of complementary cones
• Orientability of matroids
• Oriented Matroids
• Oriented matroids
• Pivoting in linear complementarity: Two polynomial-time cases
• Principal pivot transforms: Properties and applications
• Some generalizations of the criss-cross method for the linear complementarity problem of oriented matroids
• Symmetry and positive definiteness in oriented matroids
• The P-matrix problem is co-NP-complete

Cited in

(9)

• A uniform realization of the combinatorial \(R\)-matrix
• A combinatorial interpretation of the inverse kostka matrix
• Submatrices of character tables and basic sets
• Enumeration of PLCP-orientations of the 4-cube
• Combinatorial properties of some classes of matrices over GF(2)
• A diagonal form for the incidence matrices of t-subsets vs. k- subsets
• A finite characterization ofK-matrices in dimensions less than four
• Some Combinatorially Defined Matrix Classes
• Frobenius-König theorem for classes of \((0, \pm 1)\)-matrices

This page was built for publication: Combinatorial characterizations of \(K\)-matrices

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