For an integral matrix A, how to quickly determine if there exists a positive rational vector such that Ax=0?
PS: no need to solve a solution :-)
Since the right-hand side is 0 and all data is rational the question ought to be equivalent to the same question but replacing "rational" with "integer", right? It's just a question of multiplying away all the divisors. So suppose you solve the problem to maximize the sum of the x_j:s over the set A'x = 0 (where now the original A has been pre-multiplied with a large enough integer scalar so that all data in A' is integer) under the additional constraint that the sum of the x_j:s is bounded to some VERY large positive integer. (The latter ensures that the problem has an optimal solution.) If you still obtain zeroes in the solution then the answer to the question is "no". (Speaking in engineers' terms here.)
There is a version of Gaussian elimination called ''division free'' (it postpones necessary divisions to a very last diagonal system). applying this should be the fastest method to determine this. If there is more than one degree of freedom, then indeed you are left with an optimization problem but the structure of this will be much easier.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics