# Check if feasible region is zero

Say I have a system of linear equalities and inequalities with integer coefficients in $n$ variables, and let $R^n$ be the space of all possible solutions. I know that $\vec{0}$ is a solution.

Is there any efficient algorithm to check if there are any other solutions but zero? In other words, given a linear optimization problem, is there a way to check if the feasible region is a point?

• You can use some LP solver to find the $\min f$ and $\max f$ for some non zero linear function $f$.. $\min f=\max f=0$ if and only if 0 is the unique point in your feasible region – Juan Pablo Contreras Jun 17 '15 at 17:29
• Well, probably not... Say $f(x) = v * x$, if for every $x$ in the feasible region $v * x = 0$ that would imply by your assumption that the feasible region is a point while it could be a hyperplane... see my answer, it depends on $f$. – unddoch Jun 30 '15 at 14:15
• I undertand!, I'm sorry for the omission. – Juan Pablo Contreras Jul 1 '15 at 12:14

Bring the problem into canonical form (where all variables are greater than zero) and checking for maximum of the function $f(x) = (1, 1, ...,1) * x$ using any LP solver.