4
$\begingroup$

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

  • 0
    @JackSchmidt You might be right I don't have a proof now but using negative integers I think you can cancel out any entry contribution with a positive/negative cancellation. That's why I have the feeling that the family of admissible $X$ has infinitely many elements.2011-10-20

1 Answers 1

4

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

  • 0
    I think I can close this question $f$or now. `@Jack Schmidt` gave me the [GAP](http://www.gap-system.org/) and a reference to this [book](http://www.cambridge.org/gb/knowledge/isbn/item2714038/?site_locale=en_GB), in this book I found an interesting reference to this [article](http://www.sciencedirect.com/science/article/pii/S0024379504002137) (found too this [another article](http://www.sciencedirect.com/science/article/pii/002437959500156L)) exactly about what I'm looking for. So, I dont know how to solve this question and found X matrices, but, in these links they teach us. Thx so much Jack.2011-10-21