<p>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 $&lt;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.</p>

CC BY-SA 3.0
2012-04-25T12:44:24.240Z
Simultaneously crossposted on [CS.SE](http://cs.stackexchange.com/questions/1500/complexity-of-checking-whether-linear-equations-have-a-positive-solution). Please don't do this, it makes your question seem more important than others.
Juho
CC BY-SA 3.0
2012-04-25T13:06:04.707Z
I suspect that this is as hard as an arbitrary linear programming problem, which means that you cannot solve it just by using Gaussian elimination. If the rank is exactly $n$, then Gaussian elimination works, but whether you can solve it faster is an interesting question.
Peter Shor 
CC BY-SA 3.0
2012-04-25T18:44:22.337Z
It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).
Kaveh
<cc.complexity-theory><ds.algorithms><linear-algebra><linear-equations>
Complexity of checking whether linear equations have a positve solution
user29271
# Complexity of checking whether linear equations have a positve solution

(Asked by: username_0 on 2012-04-25)

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 $

**Tags:** cc.complexity-theory, ds.algorithms, linear-algebra, linear-equations
> **Comments:**
> **username_1**: Simultaneously crossposted on [CS.SE](http://cs.stackexchange.com/questions/1500/complexity-of-checking-whether-linear-equations-have-a-positive-solution). Please don't do this, it makes your question seem more important than others.  
> **username_2**: I suspect that this is as hard as an arbitrary linear programming problem, which means that you cannot solve it just by using Gaussian elimination. If the rank is exactly $n$, then Gaussian elimination works, but whether you can solve it faster is an interesting question.  
> **username_3**: It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).  

---

## 0 answers

