most recent 30 from http://mathoverflow.net 2013-05-22T09:37:16Z http://mathoverflow.net/feeds/question/35257 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35257/sorting-a-binary-matrix-diagonal-in-polynomial-time-while-preserving-rows Tristan 2010-08-11T17:56:00Z 2010-08-13T00:10:21Z

<p>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?</p> <p>For example given matrix:</p> <pre><code>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 </code></pre> <p>A solution would be:</p> <pre><code>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 </code></pre> <p>Given a matrix:</p> <pre><code>1 0 0 r0 0 0 1 r1 1 0 1 r2 </code></pre> <p>There could be multiple solutions:</p> <pre><code>1 0 0 r0 1 0 1 r2 0 0 1 r1 1 0 0 r0 1 0 1 r2 0 0 1 r1 </code></pre>

http://mathoverflow.net/questions/35257/sorting-a-binary-matrix-diagonal-in-polynomial-time-while-preserving-rows/35261#35261 Aaron Meyerowitz 2010-08-11T18:15:52Z 2010-08-11T18:15:52Z

<p>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.</p>

http://mathoverflow.net/questions/35257/sorting-a-binary-matrix-diagonal-in-polynomial-time-while-preserving-rows/35405#35405 Tracy Hall 2010-08-13T00:10:21Z 2010-08-13T00:10:21Z

<p>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 <a href="http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs" rel="nofollow">maximal matching</a>, 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.</p>