Thread: nonnegative solution in rationals

Hi,

I encounter the following problem.

Let A be an m*n matrix with all integer entries (may be positive or nonpositive).

Suppose that Ax=0 admits a nonnegative solution x (i.e., xi>=0 for all i=1,...n).

Is it true that A also admits a nonnegative solution with all entries being rational numbers?

I know the answer is yes when we take away "nonnegative" from the above: putting A in reduced row-echelon form shows that the solution-space is spanned by vectors with rational coordinates. Rational multiples of the spanning vectors are then dense in the solution space, so vectors with rational coordinates are also dense in the solution-space.

but how about with "nonnegative" added in?

Hi vivian6606,

Yes, it is true. Because the set of the solutions of your equation (Ax=0, x >= 0) is a rational polyhedral cone. In particular, its extremal edges are rational lines. Since this cone is not empty, it has extremal edges.

This is the short answer. If you do not believe me, here is a more direct proof.

Consider E the R-vector-space Ker A, and C the intersection of E with the set .

The coordinates x_i gives linear forms on E and C is the set of all v in E such that .

C is not empty, is is your hypothesis. Assume that C contains an element v with for all i. (Easy exercise : reduce to this case by adding equations in A.)
Then C contains a neighbourhood of v, since the x_i are continuous.
Since the rationnal points of E (points a with the x_i(a) rational) are dense (you did the proof), C contains a rational point.

Hi, Lierre,

Thank you so much for the detailed reply. However, I still miss something in both arguments you provide (very likely due to my lack of background).

For the first one, how do we know its extremal edges are rational lines?

For the second one, why "reduce to this case by adding equations in A?" Can we add equations in a way that still guarantee the solution exists?

Thanks again!

Originally Posted by Lierre

Hi vivian6606,

Yes, it is true. Because the set of the solutions of your equation (Ax=0, x >= 0) is a rational polyhedral cone. In particular, its extremal edges are rational lines. Since this cone is not empty, it has extremal edges.

This is the short answer. If you do not believe me, here is a more direct proof.

Consider E the R-vector-space Ker A, and C the intersection of E with the set .

The coordinates x_i gives linear forms on E and C is the set of all v in E such that .

C is not empty, is is your hypothesis. Assume that C contains an element v with for all i. (Easy exercise : reduce to this case by adding equations in A.)
Then C contains a neighbourhood of v, since the x_i are continuous.
Since the rationnal points of E (points a with the x_i(a) rational) are dense (you did the proof), C contains a rational point.

Btw, I am writing a paper that uses this result (if true), so it will be great if you also give me any reference that you are aware of. thanks!

Well, if , then you can add the equation in A, v will still be a solution, right ?
But then x_i will vanish on E, so its zero set is an open set of E, so the argument works.

Concerning the extremal rays, it is just an extension of the previous proof.
Take now a v such that it spans an extremal ray. Let I be the set of i such that x_i(v) = 0.
As in the proof above, let E' be the intersection of Ker A and Ker x_i, for i in I.
The vector v lies in E', right ? An entire neighbourhood of v in E' is solution of your system.
But v is an extremal ray, so dim E' = 1.
Since E' is a rational subspace, the extremal ray spaned by v is a rational line.

I got it. Thank you so much!