Every integer vector in $\mathbb R^n$ with integer length is part of an orthogonal basis of $\mathbb R^n$

Suppose $\vec x$ is a (non-zero) vector with integer coordinates in $\mathbb R^n$ such that $\|\vec x\| \in \mathbb Z$. Is it true that there is an orthogonal basis of $\mathbb R^n$ containing $\vec x$, consisting of vectors with integer coordinates, all with the same length?

For example: let $\vec x = \left<2,10,11\right>$, so $\|\vec x\| = 15$. Then the vectors $\left<14,-5,2\right>$ and $\left<5,10,-10\right>$ complete a basis of $\mathbb R^3$.

I've checked all such integer vectors in $\mathbb R^3$ with an integer length up to 17 and found no counter examples. Moreover, these can always be arranged as a symmetric matrix, possibly changing the order (or permuting the coordinates) and changing signs (edit: not always; see answer below). For example, the vectors above can be arranged as:

$$\begin{bmatrix}14&-5&2\\-5&-10&10\\2&10&11\end{bmatrix}$$

This is easily true if $n$ is even (edit: rather, if $n=4$), you can simply permute the entries of $\vec x$ (altering signs appropriately) to find $n-1$ other vectors orthogonal to $\vec x$. In $\mathbb R^3$, finding a second integer vector is sufficient because the cross product of the two (divided by $\|\vec x\|$) will give the third vector of such a basis. Then it is straightforward to prove for special cases (like $\vec x = \left<1,2m,2m^2 \right>$, $m\in \mathbb Z$), but I can't think of a good reason why this should be true in general.

Edited, hopefully for clarity, by o.p. The original phrasing and title referred to $\mathbb Z^n$.

Solution 1:

EDIT: This is true up to dimension 8. An article that I have, Hsia, J.S. Two theorems on integral matrices. Linear Multilinear Algebra 5, 257-264 (1978). I put a pdf at TERNARY with the name Hsia_1978.pdf. He calls the the Completion problem, answers it in Theorem 2. He also gives my dimension 9 example, page 262. So, I was only about 34 years late. This reference was provided on MO by someone anonymous using the name http://en.wikipedia.org/wiki/Yazdegerd_III , which I really thought was a Dr. Seuss name because of the rhyme, compare http://en.wikipedia.org/wiki/Yertle_the_Turtle_and_Other_Stories and see http://en.wikipedia.org/wiki/Dr._Seuss_bibliography#Dr._Seuss_books

ORIGINAL: Finally got it. The task is impossible for a 9 by 9 matrix with first row $$ (1,1,1,1,1,1,1,1,1 ). $$

I Win.

The trick is that $$ x^2 \equiv x \pmod 2. $$ So, if I take any ODD number $k,$ and consider a $k^2$ by $k^2$ matrix, then take the first row of the matrix to be all 1's, we find that there are NO other rows of the same length orthogonal to the first row, because a row $(x_1, \ldots, x_{k^2})$ is required to have squared length $k^2$ in this problem, so $$ \sum_{j=1}^{k^2} \; x_j^2 \; = \; k^2 \equiv 1 \pmod 2. $$ Then the dot product with the row of all 1's is $$ \sum_{j=1}^{k^2} \; x_j \; \equiv \; \sum_{j=1}^{k^2} \; x_j^2 \equiv 1 \pmod 2. $$ That is, the dot product is odd and therefore nonzero. So, in fact, there are just no orthogonal rows of the same squared length, you cannot fill in the entire matrix, you cannot even get a second row.

EDIT: a similar thing can be done for any $n$ by $n$ matrix when $$ n \equiv 1 \pmod 8. $$ So, for example, when $n = 17,$ the matrix cannot be filled in as desired when the first row is $$ (3,1,1,1,1, 1,1,1,1, 1,1,1,1, 1,1,1,1). $$ The entries do not need to be 1, just odd. So, there should be infinitely many first rows (for each $n$) for which this task is impossible, as long as we have $ n \equiv 1 \pmod 8. $ Yes, that is quite easy. Gauss showed that every number is the sum of three triangular numbers, such being $(1/2)(p^2 +p)$ for integer $p \geq 0.$ Now, $8 \cdot (1/2)(p^2 +p)= 4 p^2 + 4 p.$ So we can represent any multiple of 8 as $4 p^2 + 4 p + 4 q^2 + 4 q + 4 r^2 + 4 r$ with integers $p,q,r \geq 0.$ As a result, we may have any odd square we like (no smaller than $n$) as the sum of the squares of $$ (2p+1,2q+1,2r+1,1,1,1, \ldots, 1,1,1,1) $$ with the row being of length $ n \equiv 1 \pmod 8. $ As a result, we can have the length be any odd integer we like, as long as it is at least $\lceil \; \sqrt n \; \rceil.$

EDDDITTT: the part about Gauss and triangular numbers says something stronger, making for far more counterexamples: with $ n \equiv 1 \pmod 8, $ we may specify any $n-3$ odd numbers we like, then use the final three positions (also odd numbers) to force integral length, as requested in the original problem. Hence this example: $$ (1,3,5,7,9,11,13,17,25) $$ which has length 37. But any other integer vector of length 37 has an odd, hence nonzero, inner product with this vector.

Solution 2:

Well, if your real question is what @user1551 says, then it is probably true in $\mathbb Z^3.$ See the paper I call Pall_Automorphs_1940 at one of my websites, TERNARY. All that is necessary for this to settle dimension 3 is this: If $n$ is odd and $$ n^2 = x^2 + y^2 + z^2 $$ with $x$ odd, then we can find $a,b,c,d$ such that $$ x = a^2 + b^2 - c^2 - d^2, \; \; y = 2(ad - bc), \; \; z = 2(ac+bd) $$ and $$ n = a^2 + b^2 + c^2 + d^2. $$ This seems likely to me, and may be in one of Pall's articles. He and Jones found every way to use integral quaternions in studying the sum of three squares.

Other than that, I will need to think about it.

The shortest integral length for which a 3 by 3 such matrix cannot be made symmetric is 39, as in $$ \left( \begin{array}{ccc} 29 & 22 & 14 \\ 2 & 19 & -34 \\ -26 & 26 & 13 \end{array} \right) . $$ As the only repeated absolute value is 26, you do not have the three pairs of repeated absolute values necessary for transpositions of rows, or columns, and negation of either to result in symmetry. Actually, I suppose there could be some shorter length where some combinatoric problem prevents symmetry. Hard to tell.

The shortest integral length where you get nine distinct absolute values is 57, as in

$$ \left( \begin{array}{ccc} 47 & 28 & 16 \\ 4 & 23 & -52 \\ -32 & 44 & 17 \end{array} \right) . $$

The dimension 3 case is looking very good. I was looking in Dickson's History, volume II, page 271, where he mentions briefly that H. Schubert suggested this in 1902: we consider $4x^2 + 4y^2 + z^2 = n^2 $ with $z,n$ odd and $\gcd(n,z) = 1.$ This is not every case but it is a good start. It follows that with $$ u = \frac{1}{2}(n-z), \; \; v = \frac{1}{2}(n+z), $$ we also get $\gcd(n,z) = 1.$ Then, from $$ uv = x^2 + y^2, $$ we know that the two factors are separately sums of two squares, that is $$ v = a^2 + b^2, \; \; u = c^2 + d^2 $$ for some $a,b,c,d.$ But this immediately gives $$ n = a^2 + b^2 + c^2 + d^2, \; \; z = a^2 + b^2 - c^2 - d^2. $$ That is most of the battle.

FOUND IT. For dimension 3, this is Theorem 3 on page 176 of Jones and Pall (1939) which is on that website, taking $\lambda = 1.$ So dimension 3 is affirmative.

Dimension 4 is also affirmative, because you may begin with any quaternion $t$ and make the evident matrix out of $t,it,jt,kt.$

However, I do not see why that says anything about dimension 6. Given a row of six integers, certainly a rearrangement of pairs, with one extra minus sign for each pair, gives an orthogonal row. I don't see what to do after that. It is always possible that the octonions give some method for dimensions 5,6,7,8, but I would not be too sure about dimension 9 and above.

Solution 3:

This answer is wrong. And let it remain there as a reminder for me.

Some thoughts: For any integer $N \times 1$ vector , you can find another $N-1$ orthogonal set of vectors in the rational field. This is always true. Since it is in the rational field, you can multiply by a large integer, and make them all have integer entries.

Now we have seen that for every integer vector, you can find a integer orthogonal basis. But we have neglected the length part.

Let us say you have two integer vectors $\vec{x}$ and $\vec{y}$. Then there always exist a positive number $c_1$ and another positive number $c_2$ such that $c_1||\vec{x}||=c_2||\vec{y}||$. I think this should be true for any number of integer vectors. If that is true, then you can past the length part also.