7
$\begingroup$

Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $<n$. What is the complexiy to check whether it has a solution $x$ such that all entries of $x$ are stricly greater than 0 (namely, $x$ is a positive vector)? Of course, one can use Gauss elimination, but this seems not to be optimal.

$\endgroup$
  • 2
    $\begingroup$ Simultaneously crossposted on CSTheory. Please don't do this, it makes your question seem more important than others. $\endgroup$ – Juho Apr 25 '12 at 12:43
  • $\begingroup$ Is the "of course" obvious? I don't know the various LP standard forms off the top of my head, but this is a pretty general looking setup. $\endgroup$ – Louis Apr 25 '12 at 12:53
  • 2
    $\begingroup$ The paper "On Positive Solutions of a System of Linear Equations" by Lloyd Dines seems to address this. If you don't have access through JSTOR, I will read and summarize the article in an answer. $\endgroup$ – Patrick87 Apr 25 '12 at 13:02
  • 4
    $\begingroup$ @user29271 Please let us know whether this paper answers your question. If so, you might post an answer with a brief description of the technique... I'm sure you would receive plenty of reputation for providing such a useful result for the community. $\endgroup$ – Patrick87 Apr 25 '12 at 14:21
  • 2
    $\begingroup$ It is fairly straightforward to take an arbitrary linear program for a feasibility question (is there a point in the interior of a polytope given by linear inequalities) and manipulate it so that it is in your desired form. Since feasibility for linear programming is as hard as arbitrary linear programming, your problem is as hard as an arbitrary linear program. And it can indeed be solved by linear programming. I have no time right now, but if nobody else explains this and you still haven't found a satisfactory answer by the middle of next week, I can try to explain the details. $\endgroup$ – Peter Shor Apr 26 '12 at 14:19
14
$\begingroup$

First, this can be solved by linear programming. Let $x_1$, $x_2$, $\ldots$, $x_n$ be your variables. The linear program that solves your question is then

$\max t$
subject to
$t \leq x_i$, for $i=1 ... n$,
$Ax = 0$.

If the maximum is 0, then there is no positive solution. If the maximum is $\infty$ (i.e., the linear program is unbounded) then there is a positive solution.


Second, using standard transformations on linear programs, the feasibility problem for an arbitrary linear program with strict inequalities can be reduced to your problem. We start with the feasibility problem

Does there exist $x$ such that
$A x < b$ ?

We can now add a new variable $x_{n+1}$ to the right-hand-side of all these equations and an inequality $x_{n+1} > 0$ to make everything homogeneous. So for the $k$th equation, we now have

$a_{k,1} x_1 + \ldots + a_{k,n} x_n - b_k x_{n+1} < 0$.

This gives an equivalent problem on a new matrix $A'$:

Does there exist $x$ such that
$A'x < 0$ ?

Next, we can turn the inequalities into equations by adding some variables $y_i$ and requiring that $y_i > 0$. The $k$th equation on the new problem turns into

$a'_{k,1} x_1 + \ldots + a'_{k,n} x_n + a'_{k,n+1} x_{n+1} +y_k = 0$.

Finally, we want to allow all the variables to be positive. How we do this? For every variable $x_i$ with an arbitrary sign, we replace $x_i$ by $z_i - w_i$, and require $z_i>0$, $w_i > 0$.

The feasibility problem is essentially as hard as an arbitrary linear programming problem, so in general there won't be any easier way to solve your problem than using linear programming.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.