I have a $m\times n$ matrix $A$, such that $m>n$. Matrix $A$ is also comprised of only the values $-1,0,1$. We also have a vector $\vec b$ that is $m\times1$. $\vec b$ only has the restrictions that its first element is non-negative, and the elements are all integers.
I want to know if there is a way to prove in polynomial time whether or not there exists a vector $\vec x$ such that every element of $\vec x$ is non-negative and
$$ A\vec x = \vec b $$
Note the elements of $\vec x$ do not need to be integers
I'm trying to practice my math notation so I'm just going to rewrite the problem below, let me know if I'm wrong
Given $A$ an $m\times n$ matrix s.t. $a_{ij} \in \{-1,0,1\} \forall 1\leq i \leq m, 1\leq j \leq n$ and $\vec b \in \mathbb{Z}^m$
Prove $\exists \vec x \in \mathbb{R}^n_+ \,\, x_i \geq 0, A\vec x= \vec b$
I believe the answer is yes, as follows:
Introduce $2n=O(n)$ non-negative slack variables $s^+,s^-\geqslant0$, then solve the LP
$$ \begin{array}{rl} \min\ & \sum_{i=1}^ns_i^+ +\sum_{i=1}^ns_i^- \\ \text{s.t.}\ & Ax+s^+-s^-=b \\ & x,s^+,s^-\geqslant0 \end{array} $$
The system has a non-negative solution iff the optimal objective value if this LP is zero. (This is actually how the two-phase simplex method finds initial feasible solutions when solving LPs). Since LPs can be solved in polynomial time, this is a polynomial time procedure.