How to know if it is possible to rearrange columns of a matrix to avoid nulls on the diagonal? I have a square matrix with binary entries, 1 - 0.
Is there a mathematical way/trick/algorithm to know if it is possible to rearrange the columns in order to have all the elements on the main diagonal non null?
Thank you.
 A: By Hall's marriage theorem, it is sufficient to check that for any subset $S$ of size $k$ of $\{1,2,\dots,n\}$, we have at least $k$ columns that have a $1$ in the "$s$th" position for some $s \in S$.  
Checking this condition directly (as opposed to checking all permutations) takes us down from a $O(n \cdot n!)$ method to a $O(n^2\cdot 2^n)$ method.
I don't believe this is the most efficient approach.  You should try looking for "matching algorithms" in literature.  Perhaps this will prove useful.
A: the trick is to reduce the size of the problem. so if you can rearrange the rows and columns such that you get a  1 in diag $1$, and zeros on the rest of the first row and column, then you can forget the first row and column, and continue with the submatrix of size $(N-1)\times(N-1)$. if you can't get a $1$ alone in diag $1$, then I propose to minimize the number of wasted $1$ in the rest of column and row $1$. and in the case you wasted some $1$'s, I don't know if it is useful to backtrack if no solution is founded at the end, that's the interesting question. if not, you would get a $\mathcal{O}(n^2)$ algorithm ?
