Solving linear set of equations

Hi,

I have a linear set of equations Ax=b, where A is not square (more variables than equations), A and b members is of integer type, and the vector x members needs to be integer>=0. which function from the MATLAB C++ math library can I use to solve this equation? (inv() works on square, non-singular matrixes) I would also like MATLAB to warn me if there is no solution..

Answer 1

[Walter Roberson]

What you describe would essentially be a set of simultaneous knapsack problems; such problems are not solvable by linear equation methods. See http://en.wikipedia.org/wiki/Knapsack_problem

[Meytal]

The linear set of equations I'm talking about is supposed to be solvoable, because there are other constraints that I didn't mention.

an example for what I want to do:

the set of equations:

7 = 7a+15b

28 = 6b+7c

64 = 4c+3d

when I use '\', it will give me an answer: [0;0.4667;3.6;16.533]

but I need it with integers. for example, the answer [1;0;4;16] would be the answer I'm looking for.

is there any way to look for unsigned int vectors that will solve the equations?

[Walter Roberson]

I did not say the problem was not solvable: I said it is not solvable using linear equation methods. The "\" operator cannot solve these kinds of equations over integers.

Consider that if you were to allow your x to be negative as well, what you would be describing would be a set of simultaneous linear Diophontine equations, http://en.wikipedia.org/wiki/Diophantine_equation . These are not solved using linear algebra.