MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

How to find all matrices $X$ which satisfy this equation?

These articles maybe could help us:

Completely Positive Matrices

Solving X times Transpose of X Is Equal to A - Over Integers (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).

share|cite|improve this question
There is one way to find those matrices: list all the possible matrices $X$ made out of zeroes and ones (there are a finite number of them) and keep only those that satisfy your conditions. Presumably, you will not be satisfied by this answer... You can improve your question by making it be precise about what you want. – Mariano Suárez-Alvarez Nov 6 '11 at 23:05
...and why you want it. (I cleaned up some of the formatting) – David Roberts Nov 7 '11 at 0:18
@BrendanMcKay says, I'm investigating graphs but by linear algebra. And I think, but don't know why yet, it's possible find a good method to find the solutions because in that link of the integers matrices, he claims to find all integers matrices, so, binary matrices should be more easy to find but that process it's a bit fuzzy to me. – GarouDan Nov 7 '11 at 1:37

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

  1. 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.

  2. 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.)

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

share|cite|improve this answer
@BrendanMcKay I will try to get this article and take a look and return... But I think this will not can help me so much, I need find the other solutions of this problem, because this solution, by adjacency matrix I already know but I need the others, if exists. – GarouDan Nov 7 '11 at 1:40
As far as I can see, your problem is exactly the problem of finding all the vertex and edge labelled multigraphs $G$ with a particular vertex labelled linegraph $H$. I'll edit my solution to indicate how to do that. – Brendan McKay Nov 7 '11 at 6:36
There is one issue I didn't address. In order to undo the effect of step 1, the inverse linegraph solver must provide the mapping between the edges of the graph and the vertices of the linegraph. Also, this mapping can be non-unique for a few small graphs, see Hemminger, MR0396324. – Brendan McKay Nov 7 '11 at 10:55
For searching, note that "linegraph" is often written "line graph" or "line-graph". – Brendan McKay Nov 7 '11 at 10:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.