Generalizations of P0- and P-properties; extended vertical and horizontal linear complementarity problems

AbstractGeneralizing the concept of W0-pair of Willson, we introduce the notions of column (row) W0- and column (row) W-properties for a set of k + 1 square matrices {M0, M1, …, Mk} (of the same dimension), where k ⩾ 1. When k = 1 and M0 = I, these reduce to the familiar P0- and P-properties of a square matrix. We show that these notions are related to the extended vertical and horizontal LCPs. Specifically, we show that these notions appear in certain feasible/infeasible interior point algorithms and that the column (row) W-property is characterized by the unique solvability in extended horizontal (vertical) LCPs. As a by-product of our analysis, we show that a monotone horizontal LCP is equivalent to a (standard) LCP and that for a monotone horizontal LCP, feasibility implies solvability