Karamardian Matrices: An Analogue of Q-Matrices

Abstract

A real square matrix $A$ is called a $Q$-matrix if the linear complementarity problem LCP$(A,q)$ has a solution for all $q \in \mathbb{R}^n$. This means that for every vector $q$ there exists a vector $x$ such that $x \geq 0, y=Ax+q\geq 0$, and $x^Ty=0$. A well-known result of Karamardian states that if the problems LCP$(A,0)$ and LCP$(A,d)$ for some $d\in \mathbb{R}^n, d >0$ have only the zero solution, then $A$ is a $Q$-matrix. Upon relaxing the requirement on the vectors $d$ and $y$ so that the vector $y$ belongs to the translation of the nonnegative orthant by the null space of $A^T$, $d$ belongs to its interior, and imposing the additional condition on the solution vector $x$ to be in the intersection of the range space of $A$ with the nonnegative orthant, in the two problems as above, the authors introduce a new class of matrices called Karamardian matrices, wherein these two modified problems have only zero as a solution. In this article, a systematic treatment of these matrices is undertaken. Among other things, it is shown how Karamardian matrices have properties that are analogous to those of $Q$-matrices. A subclass of a recently introduced notion of $P_{\#}$-matrices is shown to possess the Karamardian property, and for this reason we undertake a thorough study of $P_{\#}$-matrices and make some fundamental contributions.