Given a (not necessarily square) boolean matrix in which all rows and columns have at least two $1$'s. I need to find the largest diagonal of $1$'s that can be made using row and column swaps.
Asked
Active
Viewed 133 times
1 Answers
0
In the worst case the length of a largest diagonal can be at most four, for matrices whose have $1$’s exactly in the border rows and columns, for instance as this:
\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 1 & 1 & 1\\ \end{pmatrix}
Indeed, in each $5\times 5$ submatrix of any swap of such a matrix there exist three rows containing at least three zeroes in the same columns, these rows contain no diagonal of length $3$
On the other hand, if each row and each column of a boolean matrix has exactly two 1’s then the matrix is square (say, $n\times n$ ) and, if I remember it right, in the solution of Problem 71 in [BG] it is proved that there exists a diagonal of length $n$.
References
[BG] G. Bizam, J. Herczeg. Jatek és logika. 85 Feladatban, Müszaki könyvkiado, Budapest, 1972 (Russian translation, Mir, Moskow, 1975).
Alex Ravsky
- 90,434