Let M be an n x n matrix with each entry equal to either 0 or 1. Let mij denote the entry in row i and column j. A diagonal entry is one of the form mii for some i.
Swapping rows i and j of the matrix M denotes the following
action: we swap the values mik and mjk for k
= 1,2, ... , n. Swapping two columns is defined analogously.
We say that M is rearrangeable if it is possible to swap some of
the pairs of rows and some of the pairs of columns (in any
sequence) so that, after all the swapping, all the diagonal entries
of M are equal to 1.
(a) Give an example of a matrix M that is not rearrangeable, but
for wbich at least one entry in each row and each column is equal
to 1.
(b) Give a polynomial-time algorithm that determines whether a
matrix M with 0-1 entries is rearrangeable.
* Please provide feedback if it clarifies your doubt.
Get Answers For Free
Most questions answered within 1 hours.