REVISITED $^2$: Does a solution in $\mathbb{R}^n$ imply a solution in $\mathbb{Q}^n$?

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$?

Where do I start?

I feel I can use this to help:

$$x_i=\frac{1}{a'_{ii}}\left(b'_i - \sum_{j=i+1}^{k} a'_{ij} x_j \right).$$

Here is a thought that just crossed my mind, but I'm not sure if this is legal:

Suppose $Y\in \{\mathbb{R}\setminus \mathbb{Q}\}^n$ and $Y'\in\mathbb{Q}^n$ are solutions to $AX=B$. Then $AY=AY'=B$, or $A(Y-Y')=A(Y+(-Y'))=0$, but addition between $\{\mathbb{R}\setminus \mathbb{Q}\}^n$ and $\mathbb{Q}^n$ is . . .

@GEdgar 1. No. My professor expect us to come up with the simplest most elegant way to show this using what he feels we should already know by now and the abstract lecture notes he provides us. So, any attempt is valid so long as it makes sense. 2. I don't know. — Trancot, May 14 '13 at 04:31
@Barisa, if you haven't yet learned an algorithmic method to solve $AX=B$, perhaps now would be a good time. It's a topic covered in linear algebra books. It will make the answer to GEdgar's second question clear. — Jonas Meyer, May 14 '13 at 05:51
How does this differ from http://math.stackexchange.com/questions/394223/linear-equations-real-solution-rational-solution which you also asked recently? How does this differ from http://math.stackexchange.com/questions/391909/mathbbrn-and-mathbbqn-on-the-nature-of-solutions which you also also asked recently? Why three versions of the same question? — Gerry Myerson, May 23 '13 at 13:26

score 9 · Accepted Answer · edited May 17 '13 at 06:15

I think the question is: if $A\in M_{m\times n}$ and $B\in\mathbb{Q}^m$ and $AX=B$ for some $X\in\mathbb{R}^n$, does there exist an $X'\in\mathbb{Q}^n$ so that $AX'=B$?

Assume the $m$ rows of $A$ are independent. If not, choose a subset of the rows of $A$ that form a basis of the row space of $A$ and the corresponding subset of the rows of $B$. Show that the removed rows can always be put back and will satisfy any solution that applies to the basis rows.

Since the rows of $A$ are independent, show that $AA^T\in M_{m\times m}$ is invertible.

What can be said of $A^T(AA^T)^{-1}B$?

Full answer

I think the question is: if $A\in M_{m\times n}$ and $B\in\mathbb{Q}^m$ and $AX=B$ for some $X\in\mathbb{R}^n$, does there exist an $X'\in\mathbb{Q}^n$ so that $AX'=B$?

Assume the $m$ rows of $A$ are independent. If not, choose a subset of the rows of $A$ that form a basis of the row space of $A$ and the corresponding subset of the rows of $B$. The removed rows can always be put back and, because there is a solution $X$, the removed rows will satisfy any solution that applies to the basis rows. This is because the same combination of basis rows in $A$ that make up a removed row in $A$ will make up the corresponding removed row of $B$ from the corresponding basis rows of $B$.

Since the rows of $A$ are independent, we have that $AA^T\in M_{m\times m}$ is invertible: suppose that $xAA^t=0$, then $|xA|^2=xAA^Tx^T=0\implies xA=0\implies x=0$.

Set $X'=A^T(AA^T)^{-1}B\in\mathbb{Q}^n$, then $AX'=AA^T(AA^T)^{-1}B=B$.

Since this question is 4 days old and obviously these hints are not helpful enough (the OP has started a bounty), I will assume it is okay to post the full solution on which my hint was based. — robjohn, May 17 '13 at 05:57
I like this attempt. Do you think you could explain it in this context? — Trancot, May 18 '13 at 00:04
@BarisaBarukh: you're welcome. The point is that the stuff in the null space of $A$ can be reduced to $\mathbb{Q}^n$ by using the pseudoinverse (which is $A^T(AA^T)^{-1}B$) — robjohn, May 23 '13 at 18:24

jkn · Answer 2 · 2013-05-15T10:57:50.207

3

No, think about $A=I$, $B=\pi\mathbb{1}$, where $\mathbb{1}$ denotes the vector of ones.

EDIT: I'm assuming $F$ is $\mathbb{R}$ or $\mathbb{C}$.

EDIT 2: For revised question - Then yes (although I can't think of an elegant argument why).

Think about using Gaussian elimination to solve for some solution (the fact that there is a solution in $\mathbb{R}^n$ implies that the algorithm generates a solution). The augmented matrix $[A|B]\in\mathbb{Q}^{m\times(n+1)}$. Gaussian elimination only requires us to swap rows around, add rows together and multiply a row by another element in matrix. $\mathbb{Q}$ is closed under addition and multiplication, thus the end product of the algorithm still belongs to $\mathbb{Q}^{m\times(n+1)}$. If at the end you have some "free variables" (that is, if there is multiple solutions) then just substitute any rational numbers into them.

EDIT 3: Just noticed that what I wrote in the second edit had already been pointed out by @GEdgar and @JonasMeyer in the comments.

edited May 15 '13 at 10:57

answered May 13 '13 at 22:47

jkn

5,129
25
53

I think you should assume that $F= \mathbb{Q}$, which would be the interesting case – Calvin Lin May 14 '13 at 00:31
@CalvinLin Yes, in fact, my professor just e-mailed us all and said that $F:=\mathbb{Q}$. – Trancot May 14 '13 at 04:32
@jkn What do you mean "that the algorithm also yield one"? – Trancot May 14 '13 at 22:23
@jkn In terms of the expression represented in my post, what can you say in the context of your answer as to how this expression has solutions? – Trancot May 14 '13 at 22:27

score 2 · Answer 3 · answered May 30 '13 at 08:13

I'll try to restate correctly what user1938185 wanted to say. Because $\Bbb Q$ is a field, solving any linear system cannot force your variables to take values outside$~\Bbb Q$. By comparison consider a set of linear equations in a real vector space (each one has a hyperplane of solutions, you are trying to find the intersection of those solution sets). I hope you would be mighty surprised if you were told that no solution exists (the intersection is empty) but that a generalised solution can be constructed by taking complex coordinates instread of real ones. Indeed this can never happen (although such a thing may happen for polynomial equations; indeed the complex numbers are created by "inventing" a solution to the quadratic equation $x^2=-1$).

If you look at the operations you have learned to solve linear equations (forming linear combinations of equations, Gaussian elimination, substitution, whatever), you will see that they only involve arithmetic operations (including division after checking that it is not by zero) which can never cause you to go outside of a field$~F$ that contains the coefficients of the original system (in your question that would be $F=\Bbb Q$). Either you and up with a plain contradiction of the type $0x=1$, which won't have a solution either in whatever field larger than$~F$ you may invent, or you found a unique solution using arithmetic operations (which will then only involve values in$~F$), or you get multiple solutions, where some variables can be chosen freely and the other ones can be expressed in terms of them by arithmetic operations. Only in the final situation can it occur that you also have solutions where variables take values outside$~F$ (the freely chosen ones can certainly be taken that way), but you don't need to do this: if all freely chosen variables are taken to have values in$~F$, then all variables will take variables in$~F$.

To summarize, if you have a system of linear equations with coefficients in a subfield$~F$ of a strictly larger field$~K$, then the existence of solutions with values in$~K$ implies the existence of solutions with values in$~F$. In particular if there is a unique solution with values in$~K$, it actually has values in$~F$. You can apply this in amongst others with $F=\Bbb Q$, $K=\Bbb R$, or with $F=\Bbb R$, $K=\Bbb C$.

score 1 · Answer 4 · answered May 23 '13 at 12:47

1

Of course! $\mathbb{Q}$ is a field, therefore if there is solution to linear system, the solutions will be rational.

You can check it by writing the explicit formulas for the solution -- for example, the ones you provided as help or Cramer's rule -- and notice that the formulas involves only additions and multiplications of rationals.

So if your system has a solution in $\mathbb{R}^n$, they are in facts in $\mathbb{Q}^n$. And if there is no solution in $\mathbb{R}^n$, there cannot be one in $\mathbb{Q}^n$.

It is impossible that $Y \in (\mathbb{R}∖\mathbb{Q})^n$ and $Y′∈\mathbb{Q}^n$ are solutions of the same linear system.

The crucial point is that the system is linear. The answer is totally different for systems of polynomials equations.

answered May 23 '13 at 12:47

AlainD

716

The 4th paragraph --- the system $x-y=17$ has solutions with all variables irrational, and solutions with all variables rational. – Gerry Myerson May 23 '13 at 13:23
You are correct. All what can be said about about $Y$ and $Y'$ is that $Y'-Y \in \ker(A)$, which contains irrational points. As the system can be undertermined, Cramer cannot be used. - However, when diagonalizing (Gauss) you only use additions and divisions, so if you endup somewhere you end up in $\mathbb{Q}$. Maybe I come back on this, when I have some time... – AlainD May 23 '13 at 13:58

REVISITED $^2$: Does a solution in $\mathbb{R}^n$ imply a solution in $\mathbb{Q}^n$?

4 Answers4

Linked