# $XX^t=A$, $X=?$. Where $X \in \{0,1\}^{n \times m}$

The problem:

$XX^t=A$, $\quad$ ($X_{ij}\in{0,1}$, $\quad$ $\sum_{j=1}^m x_{ij}=2$), $\quad$ $X=?$

Details:

$n,m \in N$

$A \in \{0,1,2\}^{n \times n}$

$X \in \{0,1\}^{n \times m}$

$A$ is a $n\times n$ symmetric matrix where the diagonal is always 2 and having off-diagonal elements just $1$ or $0$.

$(i \neq j)$ -> $A_{ij}=A_{ji}\in\{0,1\}$

$A_{ii}=2$

For example:

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

Also, $X$ is a $n \times m$ matrix where its entries are either $1$ or $0$ i.e. $X_{ij}\in\{0,1\}$ and columns have sum equal $2$:

$X_{ij}\in{0,1}$ $$\sum_{j=1}^m x_{ij}=2$$

For example:

$$X=X^T= \left( \begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right)$$

And now, $$XX^T= \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)$$

So,

$XX^t=A$

How can to find all $X$ matrices who satisfies this equation?

See this a bit general problem.

I would like a human readable process (to understand the process) and a way how to use Matlab, Mathematica or gap to solve this without brute force algorithms (just clever math).

Looking the answer of the another question. I had found recently these links.

Completly Positive Matrices

Solving X times Transpose of X Is Equal to A - Over Integers

Representation of Groups - An Computational Approach See 2.8.15 on page 161.

-
Do you really mean $a_{ii}=0$? The diagonal of $XX^t$ is the dot product of the $i^{th}$-row of $X$ with itself. This is the length of the $i^{th}$-row squared so if it's zero then the entire row is zero and so $X=0$. Your assumption $\sum_{j} x_{ij}=2$ forces the diagonal of $A$ to be 2's. – Bill Cook Oct 19 '11 at 21:22
Yes but, if the diagonal of A is irrelevant to me, can be 0 or 2 or 3 or any other number...I just need the equation holds to the other values of ${a_i}_j$. – GarouDan Oct 19 '11 at 21:39
Is your constraint that $\sum_{j=1}^{m}x_{ij}=2$ for the $3\times3$ case, or in general? – Mike Wierzbicki Oct 19 '11 at 22:04
Note that if $B$ is orthogonal (so $BB^t=I$), then $(XB)(XB)^t=XX^t$, so if your equation has one solution, it has lots and lots of them. – Gerry Myerson Oct 19 '11 at 22:06
Hint on why there is a limited response to this question: This is an integer programming problem. Actually a variant of TSP. – user13838 Oct 25 '11 at 0:16