2
$\begingroup$

Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column?

For example given matrix:

0 1 1 1 0  r0
1 0 0 1 0  r1
1 1 1 0 1  r2
0 0 0 0 1  r3
0 0 0 1 1  r4

A solution would be:

1 0 0 1 0  r1
1 1 1 0 1  r2
0 1 1 1 0  r0
0 0 0 1 1  r4
0 0 0 0 1  r3

Given a matrix:

1 0 0   r0
0 0 1   r1
1 0 1   r2

There could be multiple solutions:

1 0 0   r0    1 0 1   r2
0 0 1   r1    1 0 0   r0
1 0 1   r2    0 0 1   r1
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This sounds an awful lot like the Maximum Traversal problem. This is dealt with in this classic paper by Duff (portal.acm.org/citation.cfm?id=355963). There is also a piece of FORTRAN code called mc21a in the Harwell libraries for doing this efficiently. (hsl.rl.ac.uk/specs/mc21.pdf) $\endgroup$
    – Gilead
    Commented Aug 12, 2010 at 1:40
  • 1
    $\begingroup$ Incidentally the algorithm proposed by Duff has a worst case complexity of $O(n\tau)$ where $n$ is the order of the matrix, and $\tau$ is the number of nonzeros, though it is mentioned that in practice, the algorithm achieves $O(n) + O(\tau)$. The paper also cites another algorithm by Hopkroft and Karp that has a worst case complexity of $O(\sqrt{n}\tau)$. $\endgroup$
    – Gilead
    Commented Aug 12, 2010 at 4:07

2 Answers 2

Reset to default
4
$\begingroup$

The rows and columns of your matrix are the two sides of a bipartite graph, with the entries equal to 1 representing edges. What you are looking for is a maximal matching, for which there are many algorithms known; in particular, you can do it pretty easily in $n^3$ time using one of the methods in the link provided.

Improve this answer
$\endgroup$
3
$\begingroup$

No, there might be many ones but concentrated on only one row. It sounds like a maximal matching problem to maximize the number of ones on the diagonal and there are good algorithms for that.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I see, an "optimal assignment problem" where the final row $i$ gets the current contents $P(i)$ and the cost function is simply nonzero constant for a 0 in $(i,i)$ and cost zero for a 1 in $(i,i).$ The way I learned it you have workers as rows and jobs as columns, and a cost assigned to each square. So this needs some fiddling to be programmed properly but should work, and rapidly. $\endgroup$
    – Will Jagy
    Commented Aug 11, 2010 at 18:23
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Assignment_problem $\endgroup$
    – Will Jagy
    Commented Aug 11, 2010 at 19:11
  • $\begingroup$ In particular, there is a solution with every diagonal entry 1 if and only if every time you remove all but $k$ columns, you still have at least $k$ nonzero rows. $\endgroup$
    – Tracy Hall
    Commented Aug 11, 2010 at 20:29
  • $\begingroup$ Tracy, might that mean there is a greedy algorithm for the case when there is a solution with all 1's on the diagonal? $\endgroup$
    – Will Jagy
    Commented Aug 11, 2010 at 20:43
  • $\begingroup$ Related is the following: If the matrix A has nonzero determinant (over the integers), then such a diagonal will exist and can be gotten by row permutations alone. However, if A has nonzero determinant , has sufficiently many rows, AND there is at least one zero in every row and in every column, it is possible that no permutation of rows or columns or both will place all zeros on the diagonal. Gerhard "Ask Me About System Design" Paseman, 2010.08.11 $\endgroup$
    – Gerhard Paseman
    Commented Aug 11, 2010 at 21:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .