Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say you have two binary (i.e., (0, 1) ) m x n matrices A and B. Their row and column sums match up - i.e., for each attained row (column) sum k in A, there are the same number of rows (columns) with this sum in A as in B. So, it's not obvious that you can't obtain B by taking row and column permutations of A.

Other than trying every possible permutation, is there a way to know whether you can obtain B from A?

share|improve this question
    
@DavidMoews, to assist with the Crusade of Answers, would you please convert your comment to an answer, which I will approve? Thanks. –  Dan Moore Dec 17 '13 at 18:10
    
OK. ${}{}{}{}{}$ –  David Moews Dec 18 '13 at 2:56

1 Answer 1

up vote 1 down vote accepted

This problem is likely to be hard as it's essentially bipartite graph isomorphism.

Taking a bipartite graph whose parts have $m$ and $n$ vertices, its biadjacency matrix is defined to be the $m$ by $n$ matrix which has a $1$ in position $(i,j)$ if there is an edge between vertex $i$ in one part and vertex $j$ in the other, and $0$ otherwise. Taking $A$ and $B$ to be the biadjacency matrices of bipartite graphs then shows you that this problem is a special case of determining whether two bipartite graphs are isomorphic (as bipartite graphs, i.e., with a graph isomorphism which respects the partition of the vertices into two parts.) Also, it is just as hard as the general case, since an algorithm to solve the general case can quickly determine whether two bipartite graphs have biadjacency matrices of different sizes, or whether their biadjacency matrices have different multisets of row and column sums, in which case they can't be isomorphic. This reduces the problem to this special case.

The bipartite graph isomorphism problem is equivalent, under polynomial-time many-to-one reduction, to the graph isomorphism problem, for which no quick algorithm is known. To show the equivalence, for one reduction, start with two graphs $G$ and $H$, and construct the subdivision graph $S(G)$. This graph is bipartite, with one part having one vertex corresponding to each vertex of $G$ and the other part having one vertex corresponding to each edge of $G$; also, there is an edge between a pair of vertices in $S(G)$ for each corresponding incidence of a pair of a vertex and an edge in $G$. Then, construct the subdivision graph $S(H)$ in the same way. $S(G)$ and $S(H)$ will be isomorphic as bipartite graphs iff $G$ and $H$ are isomorphic as graphs (see Booth and Colbourn, 1979).

For the other reduction, start with a pair of bipartite graphs $G$ and $H$, and let the vertices of $G$ be divided into the parts $A$ and $B$. For each vertex $v$ in $A$, add a triangle $T_v$ and an edge connecting $v$ to $T_v$. Call the resulting graph $G'$. Construct $H'$ from $H$ similarly. Then $G'$ and $H'$ will be isomorphic as graphs iff $G$ and $H$ are isomorphic as bipartite graphs.

share|improve this answer

Your Answer

 
discard

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.