On a Characterization of P -Matrices
Katta G. Murty · SIAM Journal on Applied Mathematics · 1971
It has been shown earlier that the complementarity problem \[ w - Mz = q,\quad w\geqq 0,\quad z\geqq 0,\quad w^T z = 0 \] has a unique solution for each $q \in R^n $ if and only if M is a P-matrix. Here we show that if the complementarity problem has a unique solution for each \[ q \in \Gamma = \{ I_{ \cdot 1} , \cdots ,I_{ \cdot n} , - I_{ \cdot 1} , \cdots , - I_{ \cdot n} ,M_{ \cdot 1} , \cdots ,M_{ \cdot n} , - M_{ \cdot 1} , \cdots , - M_{ \cdot n} ,q^1 \} , \] where $q^1 $ is a point in the interior of some complementary cone, then M is a P-matrix and hence it has a unique solution for each $q \in R^n $. Hence in order to test whether the complementarity problem has a unique solution for each $q \in R^n $ (or equivalently to test whether M is a P-matrix) it is sufficient to test the uniqueness of the complementary feasible solution when q is equal to any one of the $4n + 1$ vectors in the finite set $\Gamma $.