Combinatorial characterizations of K-matrices

DOI10.1016/J.LAA.2010.08.008zbMATH Open1206.15023arXiv0911.2171OpenAlexW2053642809MaRDI QIDQ609481FDOQ609481

Komei Fukuda, Jan Foniok, Lorenz Klaus

Publication date: 1 December 2010

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

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.

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)

Cites Work

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

Cited In (7)

• 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
• Some Combinatorially Defined Matrix Classes

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)