Finding an integer orthogonal basis Say I have some non-orthogonal basis of some vector space that only have integer elements. Is it possible to find an orthogonal basis consisting of basis vectors with integer elements? 
 A: Orthogonalization without normalization does not generate vectors with irrational components if the original basis is composed of vectors with integer or rational components only. Multiplying each orthogonal vector with a suitable integer can hence make the basis consist entirely of integers. The magic number for a given vector would be simply the least common multiple of the denominators of the vector's components (written in the fractional form).
For example, an orthogonal basis of the span of $[-3,0,2]$ and $[3,5,0]$ could be given by $[-57,0,38]$ and $[12,65,18]$.
More formally, if $a_1,\ldots,a_n\in\mathbb{Q}^m$ then the $k$th vector of the orthogonal basis generated by the Gram-Schmidt orthogonalization is
$$
q_k=a_k-\sum_{j=1}^{k-1}\frac{\langle q_{j},a_k \rangle}{\langle q_{j},q_j\rangle}q_j,
$$
where $\langle\cdot,\cdot\rangle$ is the Euclidean inner product.
You can use the induction to show that the orthogonalization coefficients are rational and hence each vector $q_k$ has the form $q_k=[\frac{r_1}{s_1},\ldots,\frac{r_n}{s_n}]$, where $r_i\in\mathbb{Z}$ and $s_i\in\mathbb{Z}^+$. Setting $\tilde{q}_k=\mathrm{lcm}(s_1,\ldots,s_n)\times q_k$ then provides the orthogonal basis $\tilde{q}_1,\ldots,\tilde{q}_k\in\mathbb{Z}^n$ of $\mathrm{span}(a_1,\ldots,a_n)$.
