Let \(A\) be an \(m\times n\) matrix with rational entries and let \(b\in\mathbb Q^m\). Prove or disprove: if \[ Ax=b \] has a solution \(x\in\mathbb C^n\), then it has a solution \(x\in\mathbb Q^n\).
Solution
1. Elementary row reduction of the augmented matrix\[ [A\mid b] \]can be performed entirely inside \(\QQ\).
All entries of \(A\) and \(b\) lie in \(\QQ\). The elementary row operations used in Gaussian elimination are:
- interchange two rows;
- multiply a row by a nonzero entry’s inverse; and
- add a rational multiple of one row to another.
The field \(\QQ\) is closed under these operations. Hence the resulting row-echelon matrix still has rational entries.
2. The row-echelon form of \([A\mid b]\) contains no row of the form\[ \begin{pmatrix} 0&\cdots&0&\mid&c \end{pmatrix}, \qquad c\neq0. \]
Elementary row operations do not change the solution set of a linear system over any field containing \(\QQ\), in particular over \(\CC\). Such a row would represent the impossible equation \[ 0=c. \] Since the original system has a solution in \(\CC^n\) by hypothesis, no such row can occur.
3. The row-echelon system has a solution all of whose coordinateslie in \(\QQ\).
Assign the value \(0\) to every free variable. Starting from the bottom pivot row and proceeding upward, each pivot variable is then determined by an equation whose coefficients and right-hand side are rational and whose already determined variables are rational. Division by the nonzero rational pivot therefore gives a rational value for the pivot variable.
Thus the resulting solution vector belongs to \(\QQ^n\).
4. The original system \(Ax=b\) has a rational solution.
The vector constructed in step 3 solves the row-echelon system. Because elementary row operations are reversible and preserve the solution set, it also solves the original system.
5. Therefore the assertion in the problem is\[ \boxed{\text{true}}. \]
Step 4 constructs a solution in \(\QQ^n\) whenever a solution in \(\CC^n\) exists.
6. Q.E.D.
Step 5 is the required determination and proof.