0

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

jskattt797
  • 1,731
  • 4
    It is correct that $\ker A$ could have vectors with irrational entries; they are not saying that all elements of the kernel have rational entries. However, there always exist vectors with rational entries in the kernel, and we always have enough of these to form a basis. – Ben Grossmann Aug 01 '20 at 22:02
  • Oh right, I forgot that the span of the rational basis vectors will be a set of linear combinations with coefficients from $\mathbb{R}$, not only from $\mathbb{Q}$. – jskattt797 Aug 01 '20 at 22:50

1 Answers1

1

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.

Aphelli
  • 34,439
  • So we can treat $A$ as a linear transformation from $F^n$ to $F^m$, which are both vector spaces over $F$. In this case, $\ker{A}$ is a subspace of finite dimensional $F^n$, so it has a basis of up to $n$ vectors in $F^n$. These will still be in $\ker{A}$ and linearly independent when we treat $A$ as a map from $K^n \to K^m$ (both over $K$), so it's sufficient to show that $\ker{A}$ has the same dimension when we replace $F$ with $K$. – jskattt797 Aug 02 '20 at 01:38
  • Note that in the comment above, "these will still be linearly independent" follows from https://math.stackexchange.com/questions/546728/linear-independence-of-vectors-over-larger-fields – jskattt797 Aug 02 '20 at 02:34
  • Why is $\text{rank}A$ equal to the unique integer $r$ such that $A = PDQ$ with $P, Q$ invertible and $D$ diagonal with $r$ nonzero entries? It reminds me of the singular value decomposition. How do you prove this alternative definition of the rank? – jskattt797 Aug 02 '20 at 03:22
  • @jskattt797: your first comment is an accurate description of what I’m doing. For the third one, you just need to show that the rank of matrices $D$ such as described is $r$; and, if $A$ is any $m \times n$ matrix, $P \in GL_m$, $Q \in GL_n$, $A,PA,AQ$ have the same rank. Therefore, if $A=PDQ$ with $D$ diagonal and $P,Q$ invertible, then $A$ and $D$ have the same rank, so the rank of $A$ is the number of nonzero entries of $D$. – Aphelli Aug 02 '20 at 07:38
  • If $A = PDQ$ for diagonal $D$ and invertible $P, Q$, then $D = P^{-1}AQ^{-1}$, and the rank of $P^{-1}AQ^{-1}$ is equal to the rank of $A$ from your preceding sentence ($P^{-1}A$ has the same rank as $A$, and right multiplying by $Q^{-1}$ preserves this rank), so $\text{rank}A = \text{rank}D$ in any such expression. Why did you write that the nonzero entries of $D$ will all be equal to $1$? Is such a decomposition always possible? – jskattt797 Aug 03 '20 at 05:44
  • Indeed, it’s not necessary to require $D$ to have only ones as nonzero entries. But it’s possible (just replace $P$ with $P\Delta$ for a suitable diagonal $m \times m$ matrix $\Delta$). – Aphelli Aug 03 '20 at 07:15