Testing $0$ for a determinant like function Given $A\in\Bbb Z^{n\times n}$ we have $$Det(A)=\sum_{\sigma\in S_n}(-1)^{sgn(\sigma)}\prod_{j=1}^nA_{j\sigma(j)}$$
We can test when this is $0$ by looking at the rank in polynomial time.
Can either of following be tested for $0$ in polynomial time (it might be possible since we need only one of the $n!$ permuted diagonals to vanish which might be technically easier that testing an $n!$ sum vanishes (which is case of determinant))?
$$\prod_{\sigma\in S_n}\big((-1)^{sgn(\sigma)}+\sum_{j=1}^nA_{j\sigma(j)}\big)$$
$$\prod_{\sigma\in S_n}\sum_{j=1}^nA_{j\sigma(j)}$$
 A: The expression $f(A)$ that you wrote has  no invariant (i.e., linear algebraic) description.    The reason is that  the function $f(A)$, being a product of $n!$ linear functions,  tends to be equal to zero for many matrices.   For example $f(A)=0$ for all the diagonal matrices. 
This follows from the fact that there exists permutations $\sigma$ without fixed points and for such a permutation  we have $\sum_jA_{j\sigma(j)}=0$.
Consider now  a symmetric $n\times n$ matrix $A$ with positive entries. Clearly, in this case $f(A)>0$.  If $f(A)$ were  independent of coordinates    we should have $f(A)=0$  because $A$ can be diagonalized by an orthonormal change in coordinates. 
Remark. In view of the updated question, here is another related question. 

Suppose  that the matrix $A$ is an $n\times n$ random matrix, where
  the entries are independent  Bernoulli random variables; flip a  fair
  coin once for every entry of the matrix: Heads the entry is $1$,
  Tails, the entry is $0$.   Denote by $p_n$ the probability that the
  resulting matrix   has a trivial permuted diagonal, i.e., there exists
  a permutation $\sigma$ such that
$$A_{j\sigma(j)}=0,\;\;\forall j=1,2,\dotsc, n. $$
Find the asymptotics of $p_n$ as $n\to \infty$.

Update.   My colleague David Galvin  informed me  that  the above question  is a special case of a problem in random graph theory that has been answered by  Erdos-Renyi and Bollobas.   
For any $n$ set $z_n:=\frac{\log n}{n}$. Suppose  that entries   of an $n\times n$ matrix $A_n$ are (independently)  $0$ with probability $z_n$ and $1$ with probability $1-z_n$. Then the probability $p_n:=\mathbb{P}[f(A)=0]$ goes to $1$ really fast as $n\to\infty$. (The quantity $z_n$ is the threshold for the appearance of a perfect matching in a random bipartite graph on $2n$ vertices.)
