Solving the matrix equation $XX^t = A$ for binary matrix $X$ How to find all matrices $X \in \{0,1\}^{n \times m}$ that satisfy these equations?
$$X X^t = A \\ \sum_{j=1}^m x_{ij} = 2$$
These articles maybe could help us:


*

*Completely Positive Matrices

*Solving X times Transpose of X Is Equal to A - Over Integers
(in which he claims to find all $X$ to satisfies, but in Integers, maybe we can transform this solution to this problem and find the solutions).
 A: For general $A,X~$ this is a very difficult problem, but the condition you give that the rows of $X~$ have sum 2 makes it much easier.  Consider each row to be an edge of a graph $G~$ (i.e. the two ones in the row say which two vertices are connected).  Then $A~$ is the adjacency matrix of the linegraph $L(G)$, except for the diagonal.  It has long been known that one can determine $G~$ from $L(G)~$ even in linear time.  See this article of Lehot, for example.
(ADDED:) The theory of linegraphs says that two connected simple graphs have isomorphic linegraphs iff they are isomorphic or one is $K_{1,3}$ and the other is $K_3$.  For disconnected simple graphs, you can swap any $K_{1,3}$ component with $K_3$ and vice-versa, and you can also add isolated vertices (which doesn't change the linegraph).
So to find all the solutions for $X$:


*

*Off-diagonal entries in $A$ equal to 2 correspond to equal rows of $X$.  Collapse all sets of equal rows into single rows so that the problem reduces to one where $A$ is 0-1 off the diagonal.

*Find the connected components of $A$ and solve the inverse linegraph problem for them.  If the inverse linegraph problem has multiple solutions (as above), take all solutions. (If you are told in advance how many columns $X$ must have, there will be few possibilities with the right total number of vertices.)

*Now apply all possible permutations of the columns (if you really want all solutions).
