show/hide this revision's text 3 upper case title

sorting Sorting a binary matrix diagonal in polynomial time while preserving rows
show/hide this revision's text 2 edited tags
show/hide this revision's text 1

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