The Permanent of an Matrix with all entries either 0 or 1 is 0 Iff the Matrix contains an submatrix of 0s with . This result follows from the König-Egeváry Theorem.