Kernel of rational matrix has rational elements arbitrarily close to real elements

287 Views Asked by At

I am trying to understand this:

Let $\mathscr{S}$ be a finite system of homogeneous linear equations with rational coefficients, i.e. $Ax = 0$ for some rational matrix $A$. If $\hat{x} \in \mathbb{R}^n$ is a real solution to $\mathscr{S}$, then there exist rational solutions $x' \in \mathbb{Q}^n$ arbitrarily close to $\hat{x}$. (This follows from the solution space having a basis of rational vectors.)

In other words, let $A$ be an $m \times n$ matrix with entries from $\mathbb{Q}$. If some $\hat{x} = (\hat{x}_1, \dots, \hat{x}_n) \in \mathbb{R}^n$ is in the "solution space" $\ker{A}$, then there is another vector $x' = (x'_1, \dots, x'_n) \in \mathbb{Q}^n$ that is as "close" as we want to $\hat{x}$.

How do we know that $\ker{A}$ will have a basis of rational vectors - couldn't we have $A \hat{x} = 0$ for $\hat{x} \in \mathbb{R}^n \setminus \mathbb{Q}^n$?

I'd assume the metric $d$ we use to measure closeness is $d(\hat{x}, x') = ||\hat{x} - x'||_1 = \sum_{i=1}^n |\hat{x}_i - x'_i|$, or perhaps $d(\hat{x}, x') = \sqrt{\sum_{i=1}^n (\hat{x} - x')^2}$ using the dot product on $\mathbb{R}^n$. Since we can get $d(\hat{x}, x') < \epsilon$ for any $\epsilon > 0$, I wonder if it makes a difference?


The italicized text is from: Archer, A. F. (2000). On the upper chromatic numbers of the reals. Discrete Mathematics, 214(1-3), 65-75

Related questions: System of linear equations having a real solution has also a rational solution., If Ax=v has a real solution then it must have a rational solution, When a system of rational linear equations have complex solutions does it have rational solutions?.

1

There are 1 best solutions below

6
On BEST ANSWER

This fact is rather general from linear algebra. The general idea is that homogeneous linear systems are insensitive to scalar extensions – you can’t create a “really new” solution to them by extending the base field. There will be solutions in the extended field, sure, but they will be linear combinations of solutions from the smaller field.

Let $A$ be a $m \times n$ matrix with entries in a field $F$. You know from linear algebra that $\dim{\ker{A}}+\mathrm{rk}\,A=n$ (all of this over $F$).

We want to show that $\dim{\ker{A}}$ (which a priori would depend on $F$) does not change if we replace $F$ with a larger field $K$.

Because of the equation above, it is enough to do so for the rank of $A$. But the rank of $A$ is the unique integer $r$ such that $A=PDQ$ with $D$ having exactly $r$ nonzero entries, all equal to one, on its main diagonal, and $P \in GL_m(F),Q \in GL_n(F)$.

But then $P,Q,D$ are matrices with entries in $K$ with the same size as in $F$, and $P,Q$ are invertible in $F$ thus in $K$. So the rank of $A$ over $K$ is the same as the rank of $A$ over $F$.

So, let $x_1,\ldots,x_p$ a basis in $F^n$ of the kernel over $F$ of $A$.

Then $x_1,\ldots,x_p$ generate a subspace $V \subset K^n$ of the kernel of $A$. Now $V$ is the image in $K^n$ of the matrix $B$ (in $F$) with columns $x_1,\ldots,x_p$, so the dimension of $V$ is the rank of $B$ over $K$, thus the rank of $B$ over $F$, which is $p$, which is the dimension of the kernel of $A$ over $K$. So $V$ is the kernel of $A$ over $K$ and we are done.