Prove that if the constraints to a linear program are integer, then the optimal solution is rational

Question

I've got the following question that I can't quite figure out.

I have a vague idea of how to do this.

Attempt

Assume, for contradiction, that the optimal solution $x*$ is not rational. This means that for at least one of the variables $x_i*$, $x_i*$ can't be written as a fraction of two integers.

Now, we assumed that $x*$ is optimal. Therefore, $c^T x* \ge c^T x, \forall x$ and we have that $Ax* = b$

Now I'm not sure where to go from here. I'm trying to get a contradiction. Maybe I can somehow write $x_i*$ as a fraction of integers, or maybe I can find a rational solution $x-$ that has a higher objective value than $x*$ (i.e. $c^T x- \ge c^T x*$), thus getting a contradiction.

But I'm not sure how to do that.

Would appreciate some help.

Answer 1

One of the optimal solution is a basic feasible solution. Let $x_B$ be the basic variables and $x_N$ be the non-basic solutions.

We know that $x_N=0$, hence it is rational.

We also have $A_Bx_B=b$ where $A_B$ be the matrix corresponding to the basic columns and it is invertible.

We can solve the linear system by Cramer's rule where the solutions are quotient of the determinants of integer matrices. We know that determinant of an integer matrices is an integer, and hence their quotient is a rational number.