Combinatorial characterizations of K-matrices
From MaRDI portal
(Redirected from Combinatorial characterizations of K-matrices)
Combinatorial characterizations of \(K\)-matrices
Combinatorial characterizations of \(K\)-matrices
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.
The paper provides a number of combinatorial characterizations of a \(K\)-matrix. This concept refers to a square real matrix which is simultaneously a \(P\)-matrix (i.e., the principal minors are positive) and a \(Z\)-matrix (i.e., the off-diagonal entries are nonpositive). The authors extend a theorem of \textit{M. Fiedler} and \textit{V. Ptak} [Czech. Math. J. 12(87), 382--400 (1962; Zbl 0131.24806)] on linear-algebraic characterizations of \(K\)-matrices to the setting of oriented matroids.
Recommendations
Cites work
- A correction to a result in linear programming
- A Partition Theorem for Euclidean n-Space
- A Probelm in Linear Inequalities
- 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
- 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?)
- 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 diagonal form for the incidence matrices of t-subsets vs. k- subsets
- A uniform realization of the combinatorial \(R\)-matrix
- Combinatorial properties of some classes of matrices over GF(2)
- A finite characterization ofK-matrices in dimensions less than four
- Submatrices of character tables and basic sets
- Some Combinatorially Defined Matrix Classes
- A combinatorial interpretation of the inverse kostka matrix
- Enumeration of PLCP-orientations of the 4-cube
- Frobenius-König theorem for classes of (0, 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)
