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

Let `M` be an n x 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 !.

(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.

-
With the right wording, this could be a pretty good post on math.stackexchange; the linear-algebra nerds over there could probably give a good theoretical background to it. – Dennis Meng Oct 26 '13 at 4:16
If I understood right, we are allowed to swap elements in a same column. So it is a matter of counting the number of 1s in each column. If n is odd every column must have at least two 1s except the center column. Center column can have one. If n is even, every column should have at least two 1s. Therefore algorithm is even linear. I might be missing something big. – batbaatar Oct 26 '13 at 5:06
If you interpret the matrix as a digraph adjacency matrix, then you can show this problem is equivalent to determining whether the graph can be decomposed into strongly connected components. Hopefully that's enough of a hint. Play around with the transformations themselves (and try to think of those as merely shifting row and column labels). As for part (a), try the matrix `[0,1,1;1,0,0;1,0,0]` and interpret that as a graph. Is there a directed cycle? If the graph did have a directed cycle, can you arrange the matrix so that the diagonal elements were the edges of the cycle? – SheetJS Oct 26 '13 at 5:38
@Nirk I'm afraid I can't follow your hints - it looks like doing a topological sort to get an upper triangular matrix but that is not what is required here. A matrix consisting of a single diagonal of 1s does not correspond to a cycle but solves the problem. A matrix entirely 1s solves the problem and is a cycle. A matrix with top and left 1s is a cycle but does not solve the problem. An empty matrix is neither a cycle nor solves the problem so I think I have all four combinations. – mcdowella Oct 26 '13 at 16:35
@mcdowella by bubbling the last column up to the front, you have a cycle (if you interpret the first column of that matrix to be the same node as the first row). So moving the column back to the end merely shifts the label for the first column to the end – SheetJS Oct 26 '13 at 16:40
The passage describes a problem involving a square matrix with binary entries and the possibility of rearranging the matrix through row and column swaps to make all diagonal entries equal to 1. It includes multiple questions and suggestions for solving the problem.
multiple_questions
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Possibility of making diagonal elements of a square matrix 1,if matrix has only 0 or 1

Let `M` be an n x 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 !.

(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.

-
With the right wording, this could be a pretty good post on math.stackexchange; the linear-algebra nerds over there could probably give a good theoretical background to it. – Dennis Meng Oct 26 '13 at 4:16
If I understood right, we are allowed to swap elements in a same column. So it is a matter of counting the number of 1s in each column. If n is odd every column must have at least two 1s except the center column. Center column can have one. If n is even, every column should have at least two 1s. Therefore algorithm is even linear. I might be missing something big. – batbaatar Oct 26 '13 at 5:06
If you interpret the matrix as a digraph adjacency matrix, then you can show this problem is equivalent to determining whether the graph can be decomposed into strongly connected components. Hopefully that's enough of a hint. Play around with the transformations themselves (and try to think of those as merely shifting row and column labels). As for part (a), try the matrix `[0,1,1;1,0,0;1,0,0]` and interpret that as a graph. Is there a directed cycle? If the graph did have a directed cycle, can you arrange the matrix so that the diagonal elements were the edges of the cycle? – SheetJS Oct 26 '13 at 5:38
@Nirk I'm afraid I can't follow your hints - it looks like doing a topological sort to get an upper triangular matrix but that is not what is required here. A matrix consisting of a single diagonal of 1s does not correspond to a cycle but solves the problem. A matrix entirely 1s solves the problem and is a cycle. A matrix with top and left 1s is a cycle but does not solve the problem. An empty matrix is neither a cycle nor solves the problem so I think I have all four combinations. – mcdowella Oct 26 '13 at 16:35
@mcdowella by bubbling the last column up to the front, you have a cycle (if you interpret the first column of that matrix to be the same node as the first row). So moving the column back to the end merely shifts the label for the first column to the end – SheetJS Oct 26 '13 at 16:40
user
The passage describes a problem involving a square matrix with binary entries and the possibility of rearranging the matrix through row and column swaps to make all diagonal entries equal to 1. It includes multiple questions and suggestions for solving the problem.

TYPE: MULTIPLE_QUESTIONS