Results 1 to 6 of 6

Math Help - nonnegative solution in rationals

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    7

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jul 2011
    From
    Paris, France
    Posts
    3

    Re: nonnegative solution in rationals

    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 \{ \forall i, x_i \geq 0 \} .

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

    C is not empty, is is your hypothesis. Assume that C contains an element v with x_i(v) > 0 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2011
    Posts
    7

    Re: nonnegative solution in rationals

    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!

    Quote Originally Posted by Lierre View Post
    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 \{ \forall i, x_i \geq 0 \} .

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

    C is not empty, is is your hypothesis. Assume that C contains an element v with x_i(v) > 0 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2011
    Posts
    7

    Re: nonnegative solution in rationals

    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2011
    From
    Paris, France
    Posts
    3

    Re: nonnegative solution in rationals

    Well, if x_i(v) = 0, then you can add the equation x_i = 0 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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2011
    Posts
    7

    Re: nonnegative solution in rationals

    I got it. Thank you so much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 20th 2011, 10:13 AM
  2. nonnegative integer
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 30th 2010, 09:20 AM
  3. Nonnegative integers problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 10th 2010, 07:45 AM
  4. Function Continuous on Rationals but not on Rationals
    Posted in the Differential Geometry Forum
    Replies: 12
    Last Post: May 28th 2009, 09:49 AM
  5. convex due to nonnegative hessian proof
    Posted in the Calculus Forum
    Replies: 0
    Last Post: February 24th 2008, 09:50 PM

Search Tags


/mathhelpforum @mathhelpforum