Positive integer vectors from null space

[woelen]

Í have a problem from chemistry, which translates to the following mathematical problem:

 

Given a (non-square underdetermined) matrix A with integer elements only, find the null-space of it. I.e. determine the space of vectors x, with the property

 

Ax = 0

 

The space is determined by computing all independent base vectors of the null-space.

 

An example is given below:

 

(1 -2 0 1)

(3 -2 1 0)

 

Here the matrix A has two rows, each having 4 elements.

 

The null-space of this matrix A is fully specified by the following two vectors:

 

x1 = (1 1 -1 1)T and x2 = (0 1 2 2)T

 

With (...)T I mean a column vector (the math editor is not very cooperative to me ).

 

So, the null-space of this matrix is 2-dimensional.

 

Right now, I have written an algorithm in the C-language, that for ANY given A of ANY non-square dimension with all integer elements gives a set of all-integer null-vectors, which completely spans the null-space of the given matrix.

 

My problem is that some of these null-vectors may contain negative integer elements. What I'm looking for is an algorithm, which gives a set of vectors, which span all dimensions of the null-space and which only have non-negative elements.

 

For the system, shown above, this is trivial. The vector x1+x2 also is an element of the null-space and it has no negative elements. Hence, the set {x1+x2, x2} is a solution to my problem. In general, however, solving this problem has proven to be very hard for me. I've implemented a rude, brute force search by adding systematically vectors, looking at their coefficients and checking whether the set obtained so far still is a set of linearly independent vectors. This algorithm works OK for 2D and 3D null-spaces, but for 4D or even higher dimensional null-spaces things can become VERY time consuming. There must be some more elegant algorithm.

 

There also are systems, in which it simply is not possible to determine a set of null-vectors, which span the complete null-space with all non-negative elements. The algorithm also should detect such a situation.