Let $A \in M_{n,n}(\mathbb{R})$ be a $0-1$ square matrix. I.e., every entry of $A$ can only be $0$ or $1$. We wanna know if ($\forall \sigma \in S_n$, $\prod_{i=1}^n A_{i,\sigma(i)}=0) \implies$ ($A$ contains a zero submatrix of size $r \times s$ with $r+s \geq n+1$). Also, is the converse true?
What we know: any matrix of size $n\times n$ with a zero submatrix of size $r\times s$ with $r+s \geq n+1$ is singular.
It seems to me that both the $\implies $ and $\impliedby$ directions are true. However, I cannot deal with either. I tried to prove the converse part first by using the Leibniz expansion on $A$, since $\forall \sigma \in S_n,$ the element-product $A_{1,\sigma(1)}...A_{n,\sigma(n)}\geq 0$. But I do not know how to deal with the $\text{sgn}(\sigma)$. Can anyone help me?