# System of linear equations having a real solution has also a rational solution.

I saw this question

Let $A ∈ M_{m\times n}(\mathbb{Q})$ and $b ∈ \mathbb{Q}^m$. Suppose that the system of linear equations $Ax = b$ has a solution in $\mathbb{R}^n$. Does it necessarily have a solution in $\mathbb{Q}^n$?

and I thought I'd give an interesting, possibly wrong, approach to solving it. I'm not sure if such things can be done, if not maybe you can help me refine.

I considered the form of the equality as

$$A^{(1)}x_1+\cdots+A^{(n)}x_n=b,$$

where $A^{(i)}$ is a column vector of $A$. I then noticed that for $x_i\in\mathbb{R\setminus Q}=\mathbb{T}$ then, and this is where I think I'm doing something forbidden, each $x$ has the represenation

$$x_1 = k_{11}\tau_1+\cdots+k_{1p}\tau_p \\ x_2= k_{21}\tau_1+\cdots+k_{2p}\tau_p \\ \vdots \hspace{4cm} \vdots \\ x_n=k_{n1}\tau_1+\cdots+k_{np}\tau_p,$$

where $\tau_i$ is a distinct irrational number, $k_{ij}\in\mathbb{R}$, and $p$ is the number of such distinct irrational numbers. I wound this out, but there may be a discrepancy with $p$ and $m$. I feel this method can lead me to the answer, but I'm not sure where to go from here.

## EDIT$^1$:

I end up getting something like this, I believe, after substitution:

$$A(k^{(1)}\tau_1+\cdots+k^{(p)}\tau_p)=b$$

Here, $k^{(i)}$ is the vector

$$\begin{pmatrix} k_{1i} \\ \vdots \\ k_{ni} \end{pmatrix}.$$

## EDIT$^2$:

I think there is no discrepancy with $p$ and $m$ because $A\in M_{m\times n}(\mathbb{Q})$, $K\in M_{n\times p}(\mathbb{R})$, and $\tau\in M_{p\times 1}(\mathbb{T})$, so

$$(m\times n)\cdot (n\times p)\cdot (p\times 1) = m\times 1.$$

• I know that each $k_{1i},\dots,k_{ni}$ must sum to zero because no $\tau_i$ should be apparent in $AX=B$ because $B\in \mathbb{Q}^m$. May 17 '13 at 5:58

Yes, if the coefficients of $A$ and $b$ are rational and the system has at least one solution in reals, it also has at least one rational solution.
The elementary row operations performed during Gaussian elimination only use existing entries from the matrix and their inverses, thus keeping the matrix (and the vector $b$) rational all the time. Once the matrix is in reduced row-echelon form, some of the unknowns will be "free" to be set to any value (this happens if the rank of the matrix is smaller than the number of unknowns) and the others will be completely determined by them and the vector $b$. Setting the "free" ones to rational numbers yields completely rational solution to the original system.
More generally, if a system of linear equations over some field $F$ has a solution in its extension $E$, it also has a solution in $F$. Moreover, if we know there is at least one non-rational (or non-$F$ solution in the general version) solution, the cardinality of the set of solutions in $F$ will not be smaller than $|F|$, since there will be at least one "free" unknown.
• Your comments about the cardinality of the set of solutions aren't correct. The equation $AX=B$ can easily have only a single solution, for example when $A$ is invertible. May 17 '13 at 7:10
• @Greg Thanks for spotting it! Yes, I forgot to mention that the cardinality estimate only applies if we have at least one non-rational (or non-$F$) solution. May 17 '13 at 8:39