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

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

-
Wikipedia offers the Cholesky decomposition. Given a real symmetric matrix, there exists a lower triangular matrix $L$ such that $LL^t = A$. You could then try to conjugate $L$ to find more solutions. I'm not sure how the algorithm restricts (if at all) to $M_n(\mathbb{Z})$. en.wikipedia.org/wiki/Cholesky_decomposition –  A Walker Oct 19 '11 at 23:11
There are some points in your question that needs to be updated. First, $A$ is always positive (semi) definite. Hence not all symmetric matrices lead to an admissible $X$. Second, if $X$ has integer entries so does $A$ necessarily anyway. Lastly you did not consider rectangular $X$ which may lead to infinitely many solutions in the sense that you can take wider and wider $X$ matrices while having the same product $A$. –  user13838 Oct 20 '11 at 0:18
@percusse: I believe if the columns of X are required to be nonzero, then there are finitely many X (possibly 0), no matter what the width. This is lemma 2.8.14 of the textbook I mention. –  Jack Schmidt Oct 20 '11 at 0:28
@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. –  user13838 Oct 20 '11 at 0:33

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.

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

-
It's really very interesting. I'll take a paused look in that paper, looks very helpfull. –  GarouDan Oct 20 '11 at 14:58
This gap is powerfull, he found that example solution and another one that I put. Looks like it solves my another question that I asked in Math.SE. And solves using 0 and 1, just what I need. This OrtogonalEmbeddings function always shows a canonical solution? And your paper 160ff,is about the gap and his creators algorithms? –  GarouDan Oct 20 '11 at 15:04
As I told...I will need a bit of time to look that paper. But, is there in it, a human readable proceeding to do this calculus by hand? Just for understand the math proceddings? –  GarouDan Oct 20 '11 at 15:09
@GarouDan: There is a finite list of possible nonzero columns of X ("x.vectors" in GAP), and it returns exactly one matrix X using a particular subset of those columns. So not quite canonical, but very reasonable. The book describes computational representation theory of finite groups, especially as implemented by the research groups associated to GAP (and its predecessors/siblings CAS and MOC). I like to think of it as the textbook form of the source code to GAP. –  Jack Schmidt Oct 20 '11 at 15:10
@GarouDan: mostly yes. The book assumes for big problems you would use a computer, but it explains (1) how to do a small problem by hand and (2) how to program your own version that works a little slowly but fast enough. If you are doing character theory, GAP has even better commands. –  Jack Schmidt Oct 20 '11 at 15:12