Generalizations of the hidden Minkowski property Original Research Article

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 P0-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 K0-matrices.