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

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