How do I decompose a vector into $2$ orthogonal vectors where all coordinates are integers?

Question

I have a vector $\mathbf{n}=\langle a,b,c \rangle$ where $a$, $b$, and $c$ are integers and $\mathbf{n}\ne\langle 0,0,0 \rangle$.

I want to find two other vectors $\mathbf{v_a}$, $\mathbf{v_b}$ that are in $R^3$ with integer coordinates such that $\mathbf{n} = \mathbf{v_a} \times \mathbf{v_b}$.

For example, when $\mathbf{n}=\langle3,5,7\rangle$, a solution is $\mathbf{v_a}=\langle-1,2,-1\rangle$ and $\mathbf{v_b}=\langle-3,-1,2\rangle$.

I wrote a brute force solution that works on all vectors $\mathbf{n}$ where $a,b,c\in [-15,15]$ (a 31 x 31 x 31 cube centered around the origin). Based on this test, I'm reasonably confident there is a solution for every valid $\mathbf{n}$. However I'm not sure my brute force solution will work for all $a,b,c$ and the brute force solution is slow.

Is there a simple way to find $\mathbf{v_a}$ and $\mathbf{v_b}$?

Answer 1

Reference added: https://mathoverflow.net/questions/103152/determinant-of-integer-lattice-basis-of-l-x-1-ldots-x-n-a-1x-1-cdotsa

Yes, there is. Write your target vector as a row $R$ of fixed integers. We require their gcd to be 1. Now, using a sequence of column operations using elementary matrices $C_j,$ each of all integers and each determinant $1.$ The resulting process must transform $R$ into $(1,0,0).$ Furthermore, there will actually be few $C_i,$ with the product $C_1 C_2 C_3 ... = C.$ Then we have $$ RC = (1,0,0). $$

Given this notation, the two desired vectors are the second and third column of $C.$ If we call those columns $v,w,$ then either $v \times w = R^T$ or $w \times v = R^T$

Let me make some examples...

$$ R = \left( \begin{array}{ccc} 3 & 5 & 7 \end{array} \right) $$

$$ C = \left( \begin{array}{ccc} -2& 10& -7 \\ 0 & 1 & 0 \\ 1&-5&3 \\ \end{array} \right) $$ As rows, we have the solution vectors $$ \left( \begin{array}{ccc} 10& 1& -5 \\ -7 & 0 & 3 \\ \end{array} \right) $$

Finding $C$

parisize = 4000000, primelimit = 500000
? r = [ 3,5,7]
%1 = [3, 5, 7]
? c1 = [ 1,0,-2;0,1,0; 0,0,1]
%2 = 
[1 0 -2]

[0 1  0]

[0 0  1]

? r * c1
%3 = [3, 5, 1]


? c2 = [ 1,0,0;0,1,0; -3,-5,1]
%6 = 
[ 1  0 0]

[ 0  1 0]

[-3 -5 1]

? r * c1 * c2
%7 = [0, 0, 1]

? c3 = [ 0,0,-1;0,1,0; 1,0,0]
%11 = 
[0 0 -1]

[0 1  0]

[1 0  0]

? matdet(c3)
%12 = 1
? r * c1 * c2 * c3
%13 = [1, 0, 0]
? c = c1 * c2 * c3
%14 = 
[-2 10 -7]

[ 0  1  0]

[ 1 -5  3]

? r * c
%15 = [1, 0, 0]
? matdet(c)
%16 = 1
? 

P.S. If $g = \gcd(a,b,c) > 1,$ solve the problem for $\left(\frac{a}{g}, \frac{b}{g}, \frac{c}{g} \right).$ After finding $v,w,$ multiply one of them by $g$ but not the other.

============================================================================

$$ R = \left( \begin{array}{ccc} 6 & 10 & 15 \end{array} \right) $$

$$ C = \left( \begin{array}{ccc} 1& -10& -15 \\ 1 & -9 & -15 \\ -1&10&16 \\ \end{array} \right) $$ As rows, we have the solution vectors $$ \left( \begin{array}{ccc} -10& -9& 10 \\ -15 & -15 & 16 \\ \end{array} \right) $$

parisize = 4000000, primelimit = 500000
? r = [ 6,10,15]
%1 = [6, 10, 15]
? c1 = [ 1,0,0; 1,1,0; -1,0,1]
%2 = 
[ 1 0 0]

[ 1 1 0]

[-1 0 1]

? matdet(c1)
%3 = 1
? r * c1
%4 = [1, 10, 15]
? c2= [ 1,-10,-15; 0,1,0; 0,0,1]
%5 = 
[1 -10 -15]

[0   1   0]

[0   0   1]

? r * c1 * c2
%6 = [1, 0, 0]
? c = c1 * c2
%7 = 
[ 1 -10 -15]

[ 1  -9 -15]

[-1  10  16]

? matdet(c)
%8 = 1
? 

===============================================================

Added: we could also write the thing out in symbols, given $\gcd(a,b,c) = 1,$ with $g = \gcd(b,c) $ and Bezout expressions $sb+tc= g$ and $pa+qg=1.$ Then the method given leads us to general solution $$ \left( \begin{array}{ccc} -g& sa& ta \\ 0 & -\frac{c}{g} & \frac{b}{g} \\ \end{array} \right) $$

With the example $$ R = \left( \begin{array}{ccc} 3 & 5 & 7 \end{array} \right) $$ we get $a=3, b=5, c=7, g=1, s=3,t=-2,q=1 $ and $$ \left( \begin{array}{ccc} -1& 9& -6 \\ 0 & -7 & 5 \\ \end{array} \right) $$ In this dimension we can use Gauss reduction to find a reduced basis, $$ \left( \begin{array}{cc} 1& 1 \\ 3 & 4 \\ \end{array} \right) \left( \begin{array}{ccc} -1& 9& -6 \\ 0 & -7 & 5 \\ \end{array} \right) = \left( \begin{array}{ccc} -1& 2& -1 \\ -3 & -1 & 2 \\ \end{array} \right) $$