Complexity of checking whether linear equations have a positive solution

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.

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 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$. 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.

StackExchange Computer Science Q#1500, answer score: 14