Polynomial-Time P-Matrix Linear Complementarity Problem

Polynomial-Time P-Matrix Linear Complementarity Problem

Definitions and mathematical statement

A real square matrix $M$ is a $P$-matrix if every principal minor is strictly positive. For rational $M\in{\mathbb{Q}}^{n\times n}$ and $q\in{\mathbb{Q}}^n$, a linear complementarity solution consists of vectors $z,w\in{\mathbb{R}}^n$ with \[ w=Mz+q,\qquad z\ge0,\quad w\ge0,\quad z^{\mathsf T}w=0. \] The last condition is equivalent to $z_iw_i=0$ for all $i$. For a $P$-matrix the solution is unique. The task asks for a deterministic algorithm computing this solution in time polynomial in the binary encoding length of $(M,q)$, under the promise that $M$ is a $P$-matrix. Recognizing that promise is a separate problem. Arithmetic-operation counts with unbounded real precision do not establish a bit-complexity bound.

Formulation and concept references: [S1].

Short English statement

Can the unique solution of every rational $P$-matrix linear complementarity problem be found in polynomial bit time?

Research attempt

Scope, process, and first gap.

This GPT-6 Astra Ultra attempt, dated 27 September 2026, studies complementary supports and exact rational arithmetic. It proves a polynomial output-size bound, an exponential finite search, and a polynomial-time triangular subcase, then tests a simultaneous iteration on an explicit $P$-matrix. These are standard partial arguments. The promise is retained and is never replaced by a procedure for recognizing $P$-matrices.

The source [S1] distinguishes general geometric unique-sink orientations from additional structure arising in symmetric complementarity problems. Its symmetric results cannot be applied to every nonsymmetric $P$-matrix. The first gap here is finding a feasible complementary support in polynomial time; the rational numbers describing a solution do not themselves require exponentially many bits.

A support determines a rational candidate.

For a subset $S\subseteq[n]$, impose \[ z_{[n]\setminus S}=0,\qquad w_S=0. \] Every principal submatrix $M_{SS}$ is invertible by the $P$-matrix promise. Thus the resulting candidate is uniquely determined: \[ z_S=-M_{SS}^{-1}q_S,\qquad w=Mz+q. \tag{424.1} \] Check $z\ge0$ and $w\ge0$ exactly. If both hold, the imposed equations make every product $z_iw_i$ zero, so this is a solution.

Conversely, take the unique solution guaranteed by the promise and let $S=\{i:z_i>0\}$. Complementarity gives $w_S=0$, so it is obtained by $424.1$. Enumerating all $2^n$ subsets therefore finds a solution. The empty subset is included: it gives $z=0,w=q$, valid when $q\ge0$.

Degeneracy causes no gap. If both $z_i$ and $w_i$ vanish, several subsets may produce the same solution. The promise says that valid solution vectors are unique, not that their combinatorial support certificates must be unique. Requiring every coordinate indexed by $S$ to be strictly positive would be unnecessary for the verification test.

Polynomial bit length of the output.

Let $L$ be the total binary input length. Multiply $M$ and $q$ by the product $D>0$ of their denominators. This product has $O(L)$ bits. We obtain an integer matrix $A=DM$ and integer vector $b=Dq$ whose entries also have $O(L)$ bits, and the candidate equations are \[ A_{SS}z_S=-b_S. \] Cramer's rule expresses each coordinate as a ratio of determinants of order at most $n$. The determinant expansion, or Hadamard's inequality, bounds their bit lengths by $O(nL+n\log n)$. Computing $w=(Az+b)/D$ also gives a polynomial-size rational vector.

Thus every promised input has a rational solution of polynomial encoding length. For a supplied support, fraction-free elimination and exact sign tests run in polynomial bit time; the relevant intermediate determinants satisfy the same size bound. Listing $2^n$ supports remains exponential. A short verifiable answer does not explain how to locate its support quickly.

This distinction also prevents an unjustified complexity-class conclusion about unpromised inputs. Verification of the displayed rational equations is easy, but the total-solvability guarantee used here assumes that $M$ is a $P$-matrix. No recognition algorithm or total search procedure outside that promise has been proved.

An exact triangular algorithm.

Suppose $M$ is lower triangular with positive diagonal. Every principal submatrix is lower triangular with positive diagonal product, so this is indeed a $P$-matrix subclass. Process coordinates in order. Once $z_1,\ldots,z_{i-1}$ are known, set \[ a_i=q_i+\sum_{j<i}M_{ij}z_j. \] The remaining coordinate equation is $w_i=M_{ii}z_i+a_i$. Its unique nonnegative complementary solution is \[ z_i=\max\{0,-a_i/M_{ii}\},\qquad w_i=\max\{0,a_i\}. \tag{424.2} \] If $a_i\ge0$, positive $z_i$ would make $w_i>0$, violating complementarity, so $z_i=0$. If $a_i<0$, nonnegativity of $w_i$ requires $z_i>0$, and then complementarity forces $w_i=0$. This proves $424.2$, including $a_i=0$. Induction proves the whole solution.

There are $O(n^2)$ arithmetic operations, but a bit bound is also needed. Use the cleared integer data $A,b$. At step $i$, all denominators divide $\prod_{j\le i}A_{jj}$, whose bit length is $O(nL)$. Since the positive integer diagonals are at least one, a rough recurrence bounds magnitudes by $(1+2^{O(L)})^{O(n)}$. Numerators therefore also have polynomial bit length. Ordinary exact arithmetic implements the recurrence in polynomial bit time.

An upper triangular matrix is handled in reverse order, and a known simultaneous row/column permutation to triangular form is handled by relabeling coordinates. The proof uses this acyclic dependency order essentially.

Why a convexity shortcut changes the matrix.

For a symmetric positive definite matrix, the complementarity conditions are the optimality conditions of minimizing \[ \tfrac12 z^{\mathsf T}Mz+q^{\mathsf T}z \quad\text{over }z\ge0. \] For a nonsymmetric matrix, however, the gradient of that quadratic expression is $\tfrac12(M+M^{\mathsf T})z+q$, not $Mz+q$. Replacing $M$ by its symmetric part changes the problem.

Nor must that symmetric part be positive definite for a $P$-matrix. For \[ M=\begin{pmatrix}1&3\\0&1\end{pmatrix}, \] all principal minors are positive, but with $v=(1,-1)^{\mathsf T}$ one has $v^{\mathsf T}Mv=-1$. This matrix is easily solved by the triangular algorithm, yet the proposed general convex minimization argument has lost its hypothesis. A solvable subclass need not satisfy the additional structure used by another method.

A four-cycle in simultaneous coordinate updates.

Consider the promised instance \[ M=\begin{pmatrix}1&2\\-2&1\end{pmatrix}, \qquad q=\begin{pmatrix}-3\\1\end{pmatrix}. \] The principal minors are $1,1,5$, so $M$ is a $P$-matrix. Its solution is $z=(1,1)$, $w=(0,0)$.

The tempting simultaneous update, solving each coordinate against the previous iterate, is \[ T(z_1,z_2)=\left(\max(0,3-2z_2),\max(0,-1+2z_1)\right). \] Starting from zero gives \[ (0,0)\mapsto(3,0)\mapsto(3,5)\mapsto(0,5)\mapsto(0,0). \] Thus this iteration never reaches the unique solution. Every iterate is nonnegative, but nonnegativity and uniqueness do not imply convergence. This is a counterexample to this particular simultaneous method, not to all pivot algorithms or to polynomial-time solvability. Changing update order, damping, or the search rule would require a fresh correctness and complexity argument.

Verification and outcome.

Exact rational tests enumerate supports on small promised matrices, verify the triangular recurrence, and check every step of the displayed cycle. The determinant bounds and denominator accounting are symbolic; small numerical residuals are not used to certify complementarity.

UNRESOLVED. Polynomial solution encoding length, an exhaustive support algorithm, and the triangular polynomial-bit-time subcase are established. The first missing step is a deterministic polynomial-time method selecting a valid support for a general rational $P$-matrix, with no symmetry or triangularity assumption.

Sources

• S1 A new combinatorial property of geometric unique sink orientations. https://arxiv.org/abs/2008.08992. Formulation source.