Dado $XX^\top=A$, solución para $X$

Question

No es igual a este (mi) propia pregunta.

Es más general, probablemente más fácil que el original de la pregunta.

Todos los elementos de $X$ e $A$ son enteros.

$XX^\top=A$ e $A$ es una matriz simétrica. Cómo encontrar todas las posibles $X$ matrices?

Tal vez una de Gram-Schmidt método para mantener entero de sólo soluciones.

Un ejemplo:

$$ XX^\top= \left( \begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right) \left( \begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right) = \left( \begin{array}{ccc} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{array} \right)=A $$

Answer 1

En el sistema de álgebra computacional GAP utilizar el comando OrthogonalEmbeddings. Este utiliza un sistema inteligente de backtrack algoritmo sobre vectores más cortos en un asociado de la celosía creo. El código fuente se encuentra en lib/zlattice.gi y si recuerdo correctamente, una versión simplificada se describe en los libros de texto de formulario por Lux–Pahlings, por ejemplo, en la página 160ff (mi copia está en la oficina, de lo contrario me gustaría darle el papel de referencia). Su matriz es el ejemplo de 2.8.15 en la página 161.

Por ejemplo, su ejemplo es:

gap> a:=[[2,1,1],[1,2,1],[1,1,2]];;
gap> x:=OrthogonalEmbeddings(a);;
gap> xs:=List(x.solutions,sol->TransposedMat(x.vectors{sol}));
[ [ [ 1, 1, 0 ], [ 1, 0, 1 ], [ 0, 1, 1 ] ], 
  [ [ 1, 1, 0, 0 ], [ 1, 0, 1, 0 ], [ 1, 0, 0, 1 ] ] ]
gap> xs[1]*TransposedMat(xs[1]) = a;
true
gap> xs[2]*TransposedMat(xs[2]) = a;
true

Las matrices X son: $$ \left(\begin{array}{rrr}% 1&1&0\\% 1&0&1\\% 0&1&1\\% \end{array}\right) \qquad \left(\begin{array}{rrrr}% 1&1&0&0\\% 1&0&1&0\\% 1&0&0&1\\% \end{array}\right) $$