Essentially, I want to solve the following problem:
Given a vector of rational numbers, $\vec{X}\in \mathbb{Q}^d$, find the smallest integer vector perpendicular to it. That is, find $\vec{n}\in \mathbb{Z^d}$ such that $\vec{n}\cdot\vec{X} = 0$ and $|\vec{n}|$ is minimized.
In other words, find the integer solution to the equation $n_1 X_1 + n_2 X_2 + \cdots + n_dX_d = 0 $ with the added condition of minimizing $n_1^2 +n_2^2 + \cdots + n_d^2.$
My partial attempt at a solution: we can construct a basis of integer vectors that spans the $d-1$ dimensional space of vectors perpendicular to $\vec{X}$. The desired $\vec{n}$ is some linear combination of these basis vectors. So it is reduced to the following problem:
Given a set of integer vectors $\vec{V_1}, \vec{V_2}, \vec{V_3}, \dots \in \mathbb{Z^d}$, find the set of coefficients $a_1, a_2, a_3, \dots$ such that the magnitude of $a_1\vec{V_1} + a_2\vec{V_2} + \dots \in \mathbb{Z}^d$ is minimized.
The recast version of the problem seems perhaps a bit clearer, but I am still not sure how (if possible) to turn it in to some analytic or even numerical algorithm, beyond trial and error.
Edit: previously, I incorrectly assumed that the coefficients $a_1, a_2, a_3, \dots$ would have to be integers.
Also, if there is no unique solution $\vec{n}$, any one such vector is desired.
Best Answer
Let $x\in\Bbb{Q}^d$ be given. If $x_i=0$ for some $i$ then the $i$-th basis vector $e_i$ is perpendicular to $x$, and its magnitude is minimal. So suppose that $x_i\neq0$ for all $i$. Scaling up, without loss of generality $x\in\Bbb{Z}^d$. Then the vector $$y:=(x_2,-x_1,0,0,0,\ldots,0),$$ is perpendicular to $x$, and $||y||^2=x_1^2+x_2^2$. It follows that for a vector $z\in\Bbb{Z}^d$ perpendicular to $x$ of minimal magnitude we must have $z_k<\sqrt{x_i^2+x_j^2}$ for any pair of indices $1\leq i<j\leq d$, for every index $1\leq k\leq d$. This shows that any such minimal vector is contained in the box $[-(m-1),(m-1)]^d\subset\Bbb{Z}^d$, where $$m:=\min_{1\leq i<j\leq n}\sqrt{x_i^2+x_j^2}.$$ Of course once you find a vector of smaller magnitude inside this box, you can restrict your further search to the box with $m$ defined by this smaller vector.