Possibility of making diagonal elements of a square matrix 1,if matrix has only 0 or 1

Question

Let $M$ be an $n \times n$ matrix with each entry equal to either $0$ or $1$. Let $m_{i,j}$ denote the entry in row $i$ and column $j$. A diagonal entry is one of the form $m_{i,i}$ for some $i$. Swapping rows $i$ and $j$ of the matrix $M$ denotes the following action:we swap the values $m_{i,k}$ and $m_{j,k}$ for $k = 1, 2 ..... n$. Swapping two columns is defined analogously We say that $M$ is re-arrangeable 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 re-arrangeable, but for which 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 re-arrangeable.

I tried a lot but could not reach to any conclusion please suggest me algorithm for that.

Answer 1

Do a search for Hall's Marriage Theorem. Imagine each row is a man, each column is a woman, each $1$ represents a compatible couple, and the question is whether you can pair off the men and women into compatible couples. Hall's Marriage Theorem gives a simple necessary and sufficient condition.

Then think about $$\pmatrix{1&1&1\cr1&0&0\cr1&0&0\cr}$$

Answer 2

A 2x2 matrix is rearrangeable if there is a 1 in each column and each row.

Let n $\ge$ 3. A necessary and sufficient condition for an nxn matrix A to be rearrangeable is this:

(1) That each row and each column of the matrix contains a 1 and (2) That every (n-1)x(n-1) minor (submatrix) M contains at least (n-2) 1's such that

$\hspace{50px}$ a. M is rearrangeable; or

$\hspace{50px}$ b. M has an (n-2) x (n-2) minor which contains at least (n-2) 1's and is rearrangeable.

Proof: If a row or column is all zeros, at least one diagonal element has to be zero, no matter what switching you do. So this is a necessary condition.

Now, suppose A has an (n-1)x(n-1) minor M which is all zero, and without loss of generality assume it is in the lower right side of the matrix. Then in view of condition 1 the only possibilities for A are that $a_{1j} = 1$ for all j and $a_{j1} = 1 for all j (or at least for j > 1). With this configuration, the largest possible number of 1's on the diagonal after switching columns or rows is 2; but n > 2, so A is not rearrangeable.

So for n = 3 the presence of a zero 2x2 minor means A is not rearrangeable; but if all these minors have a 1 somewhere, A is rearrangeable.

Let n > 3 and consider an (n-1)x(n-1) minor which has a single 1 on the diagonal and is all zeros elsewhere. The most promising configuration for the rearrangeability of A is $a_{1j} = 1$ and $a_{j1} = 1$. This means that we can have only 3 1's on the diagonal of A, no matter what switching we do, so A cannot be rearrangeable.

And in general if M has fewer than n-2 1's on its diagonal and is zero elsewhere, then A cannot be rearrangeable.

Finally we consider an (n-1)x(n_1) minor which has less than (n-2) 1's, not necessarily on its diagonal. Then whether M is rearrangeable or not it cannot have more than n-3 1's on its diagonal, and A cannot be rearranged.

If the number of 1's in M is greater than n-3 and it is rearrangeable, then it has enough ones on its diagonal and A is rearrangeable.

That leaves the case where the number of 1's in M is greater than n-3 and M is not rearrangeable. There are two possibilities:

1. There is no way to get more than n-3 1's on the diagonal of M. Then A is not rearrangeable.

2. It is possible to get at least n-2 1's on the diagonal of M,even though M itself is not rearrangeable. This means there is an (n-2)x(n-2) minor of M which has at least (n-2) 1's and is rearrangeable (part b of the conditions). Then A is rearrangeable

A finite matrix has only a finite number of minors (of any size). Checking the M's for 1's is a finite process; and figuring out the rearrangeability of the M's may require looking at their minors, which in turn may require looking at the minors of these minors, etc. But the process has to end in a finite number of steps.