Let $v_0$ be the zero vector in $\mathbb{R}^n$ and let $v_1, v_2, . . . , v_{n+1}$ be vectors in $\mathbb{R}^n$ such that the Euclidean norm $|v_i − v_j|$ is rational for every $0 ≤ i, j ≤ n + 1$. Prove that $v_1, . . . , v_{n+1}$ are linearly dependent over the rationals.

I was reading an ingenious proof of this result, an outline of which I present here:

  1. "by passing to a subspace", we may assume that $v_1,...,v_n$ are linearly independent over $\mathbb{R}$

  2. since $v_1,...,v_{n+1}$ is a family of $n+1$ vectors in the $n$- dimmensional space $\mathbb{R}^n$ (considered over the field $\mathbb{R}$), they are linearly dependent over $\mathbb{R}$. Hence write $v_{n+1}=\sum_{k=1}^n\lambda_kv_k$. The goal is to show that $\lambda_k$ is rational.

  3. by the parrallelogram inequality, all the scalar products $<v_i,v_j>$ are rational. Hence the Grammian matrix $G$ of $v_1,..,v_n$ has all entries rational. Furthermore, since $v_1,...,v_n$ are linearly independent $G$ is invertible (well-known property of the Grammian)

  4. Let $w$ denote the column vector of size $n$ with coordinate $k$ given by $<v_{n+1},v_k>$. Let $\lambda$ denote the column vector of size $n$ with coordinate $k$ given by $\lambda_k$. Then we have $w=G\lambda$.

  5. From the above, $\lambda=G^{-1}w$ which is a product of matrices with rational entries, thus a rational matrix. done.

The only step I don't understand is step 1. Why do we have the right to assume $v_1,...,v_n$ are linearly independent over $\mathbb{R}$, and which subspace are we "passing to"?

  • 3
    $\begingroup$ You should first replace $\mathbb{R}^n$ by an arbitrary inner product space $V$ over $\mathbb{R}$. This extra generality is needed for the argument to work. Now, if the span of $v_1, v_2, \ldots, v_{n+1}$ has dimension $< n$, then you can always replace the inner product space $V$ by this span while throwing away as many of your vectors as the dimension you are losing (i.e., if the span has dimension $n-i$, then you throw away the vectors $v_{i+2}, v_{i+3}, \ldots, v_{n+1}$). Thus, you can WLOG assume that the span of $v_1, v_2, \ldots, v_{n+1}$ has dimension $n$. Therefore, ... $\endgroup$ – darij grinberg Jul 22 '17 at 22:59
  • 3
    $\begingroup$ ... some $n$ among the $n+1$ vectors $v_1, v_2, \ldots, v_{n+1}$ are linearly independent. Assume WLOG that the first $n$ vectors $v_1, v_2, \ldots, v_n$ are linearly independent (otherwise, just permute them appropriately). This is what constitutes step 1. $\endgroup$ – darij grinberg Jul 22 '17 at 23:00
  • $\begingroup$ @darijgrinberg : sorry can you elaborate a bit more I don't understand why we are done if $v_1,...,v_{n+1}$ are not linearly independent. Why can we "throw away" those vectors? $\endgroup$ – Joshua Benabou Jul 22 '17 at 23:59
  • $\begingroup$ Well, you don't need to care about them. If you can show that $v_1, v_2, \ldots, v_{i+1}$ are linearly dependent, then $v_1, v_2, \ldots, v_{n+1}$ will be linearly dependent a fortiori. $\endgroup$ – darij grinberg Jul 23 '17 at 0:08
  • $\begingroup$ Sorry, I still don't understand. $v_1,v_2,…,v_{n+1}$ are in any case linearly dependent over $\mathbb{R}$... $\endgroup$ – Joshua Benabou Jul 23 '17 at 0:15

If $v_1, \dots v_n$ are linearly dependent, then instead of working in $\mathbb{R}^n$ we can work in $\text{span}(v_1, \dots v_n)$, which is some real inner product space of dimension $\le n-1$. So we can argue by induction on $n$: if we've already proven the result for inner product spaces of dimension $\le n-1$, then we can apply it to $v_1, \dots v_n$. Of course it would be nice to be more explicit about the base case here.

  • $\begingroup$ Ah. I see now. So the argument was even more clever than I thought. $\endgroup$ – Joshua Benabou Jul 23 '17 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.