# Sorting a binary matrix diagonal in polynomial time while preserving rows

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

-
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) –  Gilead Aug 12 '10 at 1:40
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)$. –  Gilead Aug 12 '10 at 4:07

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.

-
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. –  Will Jagy Aug 11 '10 at 18:23
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. –  Tracy Hall Aug 11 '10 at 20:29