From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Non-Negative,  Integer  solution to simple matrix equation?
Date: 20 Nov 1998 21:40:16 GMT

In article <3653b989.0@news3.ibm.net>, Brian... <bvy@bigfoot.com> wrote:
>I'm developing an algorithm to be used in in a program I'm writing.  I've
>narrowed the problem down to a matrix equation:

[Comes out to:  A X = B  where  A is 2xn, X is nx1, B is 2x1.]

>To solve this, I know I can row-reduce the augmented 2  X  n+1 matrix
>[ a_11  ...  a_1n  |  b_1 ]
>[ a_21  ...  a_2n  |  b_2 ]
>but the catch is that the solution matrix must consist of *non-negative
>integers*.  The values I'll be working with will guarantee that such a
>solution exists, but I still need to know how to get that solution, and also
>how to determine (or what happens) when no such solution exists.

I'm going to assume the entries of  A  and  B  are integers too. If they're
rational, scale to make them integral; if they're not rational, you
probably will have no integer solutions  X.

When you do row-reduction, you can arrange to take care not to introduce
fractions. You won't be able to get a 2x2 identity matrix on the left
of  A, but you can get it diagonal, and indeed have  a_11 | a_22. This
amounts to computing the Smith Normal Form of the matrix (or homomorphism,
or Abelian group, or however you look at the underlying problem).
You can thus express the general solution  X  using linear combinations
of linearly independent solutions, in the usual way.

Your positivity condition is a little harder to confront. You need to 
select integer parameters  r_i  so that the components of a solution
vector  v_0 + Sum(r_i v_i)  are all positive. These conditions will
describe a polytope in Euclidean space; you need to see if there are
any integer points in it. I don't really know if there is an easy way to
answer this with certainty -- think about the postage stamp problem,
which is the easiest case and still not really solvable.

On the other hand, it's pretty easy to look at a region in space and
see if it has any integral points _if_ the region is fairly boxy, that is,
it should help as a practical matter to select the generators of your
kernel to be nearly orthogonal. You can do that fairly efficiently with
lattice reduction techniques (e.g. LLL).

Sorry to be vague here; I don't quite know the context of your problem, and
I think even if I did I'd have to tell you there's no clean way to 
address your problems completely -- you may have to settle for partial
results and heuristics.

dave