Let $A$ be a $108 \times 26$ matrix with integer entries and $b\in \mathbb{Z}^{108}$. Consider the system of $108$ linear equations: $Ax=b$. Suppose the system has an irrational solution $x_0$ (i.e. some entries of $x_0$ are not rational), prove or disprove that the system has a rational solution (i.e. all the entries of the solution are rational)
Here is my thought: Suppose $x_0$ is the unique solution to the system, let $A'$ be the square matrix consists of any $26$ rows of $A$ and $b'$ be the column matrix consists of the corresponding $26$ rows of $b$, then $x_0$ is still a solution to the system of equation $A'x=b'$. Now since linear equations with rational numbers as coefficients have rational numbers as solutions, $x_0=A'^{-1}b'\in \mathbb{Q}^{26}$, a contradiction.
Hence $Ax=b$ has infinitely many solutions. Hence all $108$ equations must be linearly dependent. Thus there exists infinitely many rational solutions (fix any $25$ rational numbers and solve for the last one).
I wanna ask is my solution correct and if there is any slicker solution using the theory of linear algebra? Thank you so much.
Best Answer
That idea of fixing any $25$ rational numbers and solve for the last one does not work. Consider, for instance, the system:$$\left\{\begin{array}{l}x+y=2\\x+2y=3\\y=1.\end{array}\right.$$Those $3$ equations are linearly dependent (the second one is the sum of the other two), and the system can be solved (take $(x,y)=(1,1)$). But, if you put $x=0$, the system becomes$$\left\{\begin{array}{l}y=2\\2y=3\\y=1,\end{array}\right.$$and this system has no solution.
Let $n=\operatorname{rank}A$. Then there is a $n\times n$ submatrix of $A$ whose determinant is not $0$. For instance, suppose that$$A=\begin{bmatrix}\color{red}1&2&\color{red}{-1}\\0&0&1\\\color{red}1&2&\color{red}0\\2&4&-1\end{bmatrix},$$whose rank is $2$ (the determinant of the submatrix with red entries is not $0$, but the determinant of any $3\times3$ submatrix is $0$), and suppose that, say, $b=\begin{bmatrix}1&2&3&4\end{bmatrix}^T$. Then the system $Ax=b$ has solutions. So, the rank of the augmented matrix (the matrix that you get adding to $A$ an extra column at the end whose entries are the entries of $b$) is also $2$. In particular, the rank of$$\begin{bmatrix}\color{red}1&\color{red}{-1}&1\\\color{red}1&\color{red}0&3\end{bmatrix}$$is $2$. And now you can apply your idea. If you consider the system$$\left\{\begin{array}{l}\color{red}x+2y\color{red}{-z}=1\\\color{red}z=2\\\color{red}x+2y=3\\\color{red}{2x}+4y\color{red}{-z}=4,\end{array}\right.$$you can replace $y$ by any rational number you want, and then solve the system.
In the general case, you can replace $26-n$ variables by any $26-n$ rational numbers, and then solve the remaining equations. You shall get rational solutions, because you shall be solving a system of the type $A'x=b'$, where $A'$ is a $n\times n$ matrix with rational coefficients and non-zero determinant and $b'$ will consist of rational numbers.