¿Cómo descompongo un vector en$2$ vectores ortogonales donde todas las coordenadas son números enteros?

Question

Tengo un vector de $\mathbf{n}=\langle a,b,c \rangle$ donde $a$, $b$, y $c$ son enteros y $\mathbf{n}\ne\langle 0,0,0 \rangle$.

Quiero encontrar a otros dos vectores $\mathbf{v_a}$, $\mathbf{v_b}$ que están en $R^3$ con coordenadas enteras tal que $\mathbf{n} = \mathbf{v_a} \times \mathbf{v_b}$.

Por ejemplo, cuando se $\mathbf{n}=\langle3,5,7\rangle$, una solución es$\mathbf{v_a}=\langle-1,2,-1\rangle$$\mathbf{v_b}=\langle-3,-1,2\rangle$.

Escribí una solución de fuerza bruta que funciona en todos los vectores $\mathbf{n}$ donde $a,b,c\in [-15,15]$ (de 31 x 31 x 31 cubo centrado alrededor del origen). Basándose en esta prueba, estoy razonablemente seguro de que hay una solución para cada válido $\mathbf{n}$. Sin embargo no estoy seguro de que mi solución de fuerza bruta de trabajo para todos los $a,b,c$ y la solución de fuerza bruta es lento.

Hay una manera sencilla de encontrar $\mathbf{v_a}$$\mathbf{v_b}$?

Answer 1

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

Sí, hay. Escribe tu objetivo de vectores como una fila $R$ fijo de números enteros. Requerimos su mcd 1. Ahora, mediante una secuencia de la columna de operaciones con matrices elementales $C_j,$ cada uno de todos los números enteros y cada determinante $1.$ El proceso resultante debe transformar $R$ a $(1,0,0).$ por otra parte, realmente habrá pocos $C_i,$ con el producto $C_1 C_2 C_3 ... = C.$, Entonces tenemos $$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)$$ Como filas, tenemos la solución vectores $$\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)$$ Como filas, tenemos la solución vectores $$\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.$ A continuación, el método que nos conduce a la solución general $$\left( \begin{array}{ccc} -g& sa& ta \\ 0 & -\frac{c}{g} & \frac{b}{g} \\ \end{array} \right)$$

Con el ejemplo $$R = \left( \begin{array}{ccc} 3 & 5 & 7 \end{array} \right)$$ llegamos $a=3, b=5, c=7, g=1, s=3,t=-2,q=1$ y $$\left( \begin{array}{ccc} -1& 9& -6 \\ 0 & -7 & 5 \\ \end{array} \right)$$ En esta dimensión podemos usar Gauss reducción de encontrar a una reducción de la base, $$\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)$$