Affordable Access

Publisher Website

Generalizations of the hidden Minkowski property

Authors
Journal
Linear Algebra and its Applications
0024-3795
Publisher
Elsevier
Publication Date
Volume
429
Identifiers
DOI: 10.1016/j.laa.2008.06.003
Keywords
  • P0-Matrix
  • K0-Matrix
  • Hidden Minkowski (Hiddenk) Matrix
  • Irreducible Matrix
  • Linear Complementarity
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract The linear complementarity problem whose defining feature is the extended n -step property is known to be solvable in polynomial time. This paper focuses on the investigation of the subclass of P 0 -matrices that possess this particular property. We present a necessary condition and a (separate) sufficient condition for membership in the class. It is shown that each of the conditions defines a set of matrices that properly contains the (transposed) hidden Minkowski set, thus generalizing previous work developed in Ref. [J.-S. Pang, R. Chandrasekaran, Linear complementarity problems solvable by a polynomially bounded pivoting algorithm, Math. Program. Study 25 (1985) 13–27] and in Ref. [W.D. Morris, Jr., J. Lawrence, Geometric properties of hidden Minkowski matrices, SIAM J. Matrix Anal. Appl. 10 (1989) 229–232]. To prove the necessity result we use a matrix-analytical approach instead of a geometric argument as in the previous case. To prove the sufficiency result we first establish two characterizations of singular irreducible K 0 -matrices.

There are no comments yet on this publication. Be the first to share your thoughts.