Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
share|improve this question
1  
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
1  
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
add comment

2 Answers 2

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
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
1  
    
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
    
Tracy, might that mean there is a greedy algorithm for the case when there is a solution with all 1's on the diagonal? –  Will Jagy Aug 11 '10 at 20:43
    
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 –  Gerhard Paseman Aug 11 '10 at 21:15
add comment

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.