Given $XX^\top=A$, solving for $X$

Question

Not equal to this (my) own question.

It's more general, probably more easy than the original question.

All of the elements of $X$ and $A$ are integers.

$XX^\top=A$ and $A$ is a symmetric matrix. How to find all possible $X$ matrices?

Maybe a Gram-Schmidt method to keep only integer solutions.

An example:

$$ 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

In the computer algebra system GAP use the command OrthogonalEmbeddings. This uses an intelligent backtrack algorithm over shortest vectors in an associated lattice I believe. The source code is in lib/zlattice.gi and if I recall correctly, a simplified version is described in textbook form by Lux–Pahlings, for instance on page 160ff (my copy is at the office, otherwise I'd give you the paper reference). Your particular matrix is example 2.8.15 on page 161.

For example, your example is:

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

The matrices X are: $$ \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) $$