Deciding whether a binary matrix contains a permutation matrix

Question

I would like to know if there is any condition to check whether a binary matrix contains a permutation matrix of the same size. E.g. $$A_1=\pmatrix{1&1&1&1\\ 1&0&0&1\\ 1&0&0&1\\ 1&0&0&0}$$ does not contain any permutation matrix, whereas $$A_2=\pmatrix{1&1&1&1\\ 1&0&1&1\\ 1&0&0&1\\ 1&0&0&0}$$ contains $$P=\pmatrix{0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0}.$$

Thank you very much for your help!

Answer 1

A binary matrix contains a permutation matrix (in the sense illustrated by your example) if and only if its permanent is non-zero. The permanent can be computed in $O(2^nn)$ time.