3 upper case title

2 edited tags
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