Keep the entries small

Algebra Level 4

When I'm teaching Linear Algebra, I'm often interested in finding orthogonal vectors with integer entries as I'm looking for examples that are easy to work in the classroom. In this context, I'm wondering whether the following statement holds true for all positive integers $n>1$ :

For every vector $\mathbf{v}$ in $\mathbb{Z}^n$ with an integer magnitude $||\mathbf{v}||$ there exists an orthogonal vector $\mathbf{w}$ in $\mathbb{Z}^n$ such that $||\mathbf{v}||=||\mathbf{w}||$ .

True False An open problem

1 solution

Brian Moehring
Oct 22, 2018

For $n=9,$ set $\mathbf{v} = (1,1,1,1,1,1,1,1,1).$ Then any orthogonal $\mathbf{w} = (w_1,w_2,w_3,w_4,w_5,w_6,w_7,w_8,w_9) \in \mathbb{Z}^9$ satisfies $\sum_{k=1}^9 w_k = \mathbf{v}\cdot \mathbf{w} = 0$ which in particular means $w_k$ is odd for an even number of values of $k,$ so $||\mathbf{w}||^2 = \sum_{k=1}^9 w_k^2$ is even. Therefore, $||\mathbf{w}|| \neq 3 = ||\mathbf{v}||.$

Since this shows any orthogonal $\mathbf{w}\in \mathbb{Z}^9$ has $||\mathbf{w}|| \neq ||\mathbf{v}||,$ the answer is $\boxed{\text{false}}.$

Notes:

This method works to generate a counterexample for any odd square $n.$
It's easy enough to see that the statement is true when restricted to even values of $n.$ However, I do not even know whether it will ever be true for odd values of $n$

Great answer, Brian! This is exactly the counterexample I had in mind (thus the heading!). Let us know what you find out about the cases of $n=3,5,7$ .

Otto Bretscher - 2 years, 7 months ago

This paper discusses when an integer $M$ is twin-complete, namely when any vector in $\mathbb{Z}^3$ of length $\sqrt{M}$ possesses an orthogonal integer vector of the same length.

It is stated there that $m^2$ is twin-complete for any integer $m$ , which means that every vector in $\mathbb{Z}^3$ of integer length has an integer orthogonal vector of the same length, which seems to wrap up the case $n=3$ .

Higher order cases are not considered in the paper, but the fact that not all integers are twin-complete leaves enough room to allow for the fact that $n=9$ does not work. The list of exactly which integers are twin-complete seems to be contingent on the truth of the Riemann Hypothesis, but we await more data before we know whether this has been settled by Michael Atiyah!

Mark Hennings - 2 years, 7 months ago

Thanks for sharing! I first got interested in these kinds of questions from a practical point of view, as I was trying to construct orthogonal matrices with rational entries for my linear algebra classes, and I was asking myself how much freedom one has to do so, row by row.

I'm surprised to read that "Not all integer vectors in $\mathbb{Z}^3$ of integer length belong to an orthogonal basis of integer vectors, all of the same length, though." I was under the impression that such a "completion" is always possible (up to $\mathbb{Z}^8$ ). Do you have a counter example?

Otto Bretscher - 2 years, 7 months ago

@Otto Bretscher – An overstatement, it seems. A previous paper I was looking at had a calculational technique which did not always work. This paper , however, seems to show that we have a positive answer to the completion problem (can an integer vector in $\mathbb{Z}^n$ of integer length) be embedded in an orthogonal set of integer vectors, all of the same length) is true for all $n$ up to (but, of course, not including) $9$ .

Mark Hennings - 2 years, 7 months ago

@Mark Hennings – Yes, exactly! More importantly for the linear algebra teacher eager to construct rational orthogonal matrices, rational completion seems to work in all dimensions: A list of orthonormal vectors in $\mathbb{Q}^n$ can always be completed to a rational orthogonal matrix.

Otto Bretscher - 2 years, 7 months ago

v = {3,4,12} is orthogonal to {{4, -12, 3}, {-4, 12, -3}, {12, 3, -4}, {-12, -3, 4}}

I have found similar cases in n=5 and n=7. I didn't try further.

A Former Brilliant Member - 2 years, 4 months ago

Keep the entries small

1 solution

0 pending reports