Decidir si una matriz binaria contiene una matriz de permutación

Question

Me gustaría saber si existe alguna condición para comprobar si una matriz binaria contiene una matriz de permutación del mismo tamaño. Por ejemplo $$A_1=\pmatrix{1&1&1&1\\ 1&0&0&1\\ 1&0&0&1\\ 1&0&0&0}$$ no contiene ninguna matriz de permutación, mientras que $$A_2=\pmatrix{1&1&1&1\\ 1&0&1&1\\ 1&0&0&1\\ 1&0&0&0}$$ contiene $$P=\pmatrix{0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0}.$$

Muchas gracias por su ayuda.

Answer 1

Una matriz binaria contiene una matriz de permutación (en el sentido ilustrado por su ejemplo) si y sólo si su permanente es distinto de cero. El permanente puede ser calculado en $O(2^nn)$ tiempo.