4
$\begingroup$

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:

$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 6, 2011 at 23:05
  • $\begingroup$ ...and why you want it. (I cleaned up some of the formatting) $\endgroup$
    – David Roberts
    Nov 7, 2011 at 0:18
  • $\begingroup$ @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. $\endgroup$
    – GarouDan
    Nov 7, 2011 at 1:37
  • $\begingroup$ The URLs are broken. $\endgroup$ Nov 12, 2017 at 12:44
  • $\begingroup$ Should the second equation hold for all $i$? It wouldn't hurt to specify it. $\endgroup$ Nov 12, 2017 at 15:30

1 Answer 1

9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @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. $\endgroup$
    – GarouDan
    Nov 7, 2011 at 1:40
  • $\begingroup$ 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. $\endgroup$ Nov 7, 2011 at 6:36
  • $\begingroup$ 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. $\endgroup$ Nov 7, 2011 at 10:55
  • $\begingroup$ For searching, note that "linegraph" is often written "line graph" or "line-graph". $\endgroup$ Nov 7, 2011 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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