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?
Asked
Active
Viewed 841 times
1 Answers
3
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)$.
Algebraic Pavel
- 22,928