Let $A$ be a binary square matrix in {$0,1$}$^{n\times n}$. What is the number of row permutations that will result in nonzero diagonals? I.e., the number of permutation matrices $P$ s.t. the diagonal of $PA$ has no zero?
I have some intuition to relate it to n-rooks problem, or directed graphs (maybe with cycles). But I don't know how to proceed.
Suppose that we take the matrix $A$ to represent a balanced bipartite graph: one with vertices $v_1, v_2, \dots, v_n$ and $w_1, w_2, \dots, w_n$, and an edge $v_i w_j$ whenever $A_{ij}=1$.
Then a permutation matrix $P$ such that the main diagonal $PA$ consists of ones corresponds to a perfect matching: more precisely, if we permute the rows by permutation $\sigma$, then the edges $$v_1 w_{\sigma(1)}, v_2 w_{\sigma(2)}, \dots, v_n w_{\sigma(n)}$$ are the edges of a perfect matching in the graph.
Hall's theorem gives a condition for such a permutation to exist. (It is sufficient, but not necessary, for $A$ to be invertible; Hall's condition is both necessary and sufficient.) However, it is computationally difficult to compute the number of perfect matchings: the problem is ♯P-complete, which is an analog of NP-completeness for problems with numerical answers.
In particular, from the point of view of the matrix $A$, what we want to compute is the permanent of $A$: a quantity defined similarly to the determinant, but as an unsigned sum of products. Wikipedia has some more details on how to compute this faster than brute force, though the result is still not going to be efficient.