# Complexity of $Ax\geq 0$

May be it's a stupid question (sorry if it's the case).

What is the complexity the decision problem:

Input: $A\in\mathcal{M}_{n,m}(\mathbb{Z})$

does there exists $x\in\mathbb{N}^n,x>0$ such that $Ax\geq 0$?

Where $x\geq 0$ means for all $x_i\geq 0$ and $x>0$ means there exists $x_j>0$.

I know that integer linear programming is NP-complete but it's expressed has $Ax\leq b$ and I failed to reduce $Ax\leq b$ to $Ax\geq0$ ...

## 1 Answer

Your problem is in polynomial time, as the following claim implies.

Claim Let $A$ be an $m\times n$ matrix with rational entries. There exists an integer $x > 0$ such that $Ax \geq 0$ if and only if there exists a real $x > 0$ such that $Ax \geq 0$.

Proof The forward implication is trivial. For the backward implication, suppose that there exists a real $x > 0$ such that $Ax \geq 0$. In particular, the polytope $P = \{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \}$ is non-empty. Pick some vertex $x$ of $P$. Since all entries of $A$ are rational, all coordinates of $x$ are also rational. Therefore for some integer $N>0$, all entries of $Nx$ are integral. Furthermore $Nx > 0$ and $A(Nx) = N(Ax) \geq 0$. $\square$

Given a matrix $A$, in order to determine whether there exists a real $x > 0$ such that $Ax \geq 0$, check whether the polytope $P = \{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \}$ is non-empty using linear programming. This can be done in polynomial time.

• Wait ... Why it doesn't work for the decision version of integer linear programming which is NP? – wece May 23 '13 at 18:52
• @wece because when you scale a rational $x$ by $N$ so that $Nx$ is integral, the constraint $A(Nx) = N (Ax) \leq b$, does not have to hold for arbitrary $b$. – Sasho Nikolov May 23 '13 at 20:31
• @SashoNikolov :S thanks I feel stupid now. – wece May 23 '13 at 20:33