Determining the handicap of a sufficient matrix (Q677143): Difference between revisions

It is known that \(A\in\mathbb{R}^{n\times n}\) is sufficient if and only if there is a \(k\geq 0\) auch that (1) \((1+4k) \sum_{i\in I_+(x)} x_iy_i+ \sum_{i\in I_-(x)} x_iy_i\geq 0\) for all \(x\in\mathbb{R}^n\), where \(y=Ax\) and \(I_+(x)= \{i\mid x_iy_i>0\}\) and \(I_-(x)= \{i\mid x_iy_i<0\}\), and any sufficient linear complementarity problem can be solved by means of the unified interior point method. The smaller \(k\) in (1) can be chosen, the better the complexity bound of the method. This value is called the handicap of sufficient matrix \(A\). After some preliminaries the author derives a general expression for the handicap of a sufficient indefinite matrix of order two and determines the handicaps of P-matrices (the class of matrices with positive principal minors). Further, he shows that, for \(n\geq 3\), determining the handicap of a sufficient matrix \(A\in\mathbb{R}^{n\times n}\), not in P, can be reduced to determining handicaps of P-matrices of order less than \(n\) and those of sufficient matrices of order two. Finally, he indicates that the handicaps of a sufficient matrix and its transpose are equal.