A class of strictly semimonotone matrices in linear complementarity theory.

It is known that special types of linear complementarity problems can be solved in polynomial time, although the general problem is NP-complete. One example is the case where the defining matrix is nondegenerate and for which the n-step property holds. In this dissertation the property is extended to the degenerate case. Specifically, the concept of an extended n-step vector is introduced, which gives rise to a class of matrices called ENS matrices. It is shown that the LCP defined by a matrix of this type is polynomially solvable, and that the matrix is in fact strictly semimonotone. Matrix-theoretic studies of these matrices are conducted. Among the major results established are the derivations of necessary conditions and sufficient conditions for a real square matrix whose principal minors are nonnegative to belong to the ENS class. Each of these conditions defines a collection of matrices that properly contains the class of matrices for which the transpose is hidden Minkowski. In addition, geometric and set-theoretic properties of the set of extended n-step vectors are investigated, under the assumption that the associated matrix has nonnegative principal minors. A geometric property relating the set in question to complementary cones is given. It is also proven that under the usual perturbation of the matrix, the set increases monotonically with the perturbation parameter. A separate but related topic is also explored in this thesis. It involves the connection between those matrices with nonnegative principal minors and those characterized by non-strict semimonotonicity. Two different sets of conditions under which the two matrix classes coincide are derived and proven.Ph.D.Applied SciencesMathematicsOperations researchPure SciencesUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/127422/2/3029319.pd