Check if solution to a system of linear equations is positive

Question

If I have a system of linear equations, $$\mathbf{A}\mathbf{x}=\mathbf{b},$$ where $\mathbf{A}$ is a $n \times n$ matrix with real coefficients and $\mathbf{b}$ a vector of size $n$ with real coefficients, is there a technique to check if solution $\mathbf{x}$ is positive (that is, $x_i\geq 0$ for all $i$). So I could somehow get required relationship between coefficient that would produce a positive $\mathbf{x}$ (without checking it all by hand).

Answer 1

Farkas's lemma says there is a solution to $\bf A \bf x = b$ with $\bf x \ge 0$ if and only if there is no $\bf y$ with $\bf y^T \bf A \le 0$ and $\bf y^T \bf b > 0$.

In practice, if $\bf A$ is invertible, the thing to do is simply solve $\bf A \bf x = \bf b$ and look the entries of $\bf x$. If $\bf A$ is not invertible, use linear programming software which is readily available.

Answer 2

If $A$ is invertible then your solution for $x$ is unique and as far as I know, there are no easy to check conditions on $A$ or $b$ to guarantee the solution $x$ has all non-negative entries, other than just to apply $A^{-1}$ and see what happens. If $A$ is not invertible, then either there is no solution or there is a span of solutions by adding any vector in the kernel of $A$ to a known solution. In this case, if you know a solution $x_0$ you can solve a reduced dimension linear programming problem $A(x-x_0) = 0$, $x \geq 0$. For example, if the kernel of $A$ has dimension 1 then this is very easy to solve or determine that no solution exists. Otherwise, like Robert Israel said, you have to solve a linear programming problem to determine such $x$ (if it exists), and there are many linear programming software packages online.