If we consider the main diagonal, that maximum number will not change, and we can translate the problem (by considering main diagonal) as follows:
Let $A=[A_{ij}]$ be an $n\times n$ $(0,1)$-matrix. Let $S_n$ be symmetric group of order $n$ (set of all permutations of $\{1,2,\dots,n\}$). If $\mathcal{P}(A)=\{(A_{1\alpha(1)}, A_{2\alpha(2)},\dots,A_{n\alpha(n)})\ |\ \ \ \ \alpha\in S_n\}$, show that $$|\mathcal{P}(A)|\le 2^n-n.$$
I'm not sure how to prove it for any $(0,1)$-matrix, but it's not so hard to show that $|\mathcal{P}(I_n)|= 2^n-n.$ . Here's how:
First of all notice that any element of $\mathcal{P}(A)$ is a binary of length $n$, because $A$ is a $(0,1)$-matrix. So $|\mathcal{P}(A)|\le 2^n$ for any $(0,1)$-matrix $A$. But for identity matrix a binary with exactly one $0$ could not be in $\mathcal{P}(I_n)$, otherwise we have a zero row that is not possible. Since number of binaries with exactly one $0$ is $n$ so we have $|\mathcal{P}(I_n)|\le 2^n-n$. But any other binary is happen to be in $\mathcal{P}(I_n)$ because for example if $(x_1,x_2,\dots,x_n)$ is a binary with $x_{i_1}=x_{i_2}=\cdots=x_{i_m}=0$, $2\le m$, and other places $1$ then by using the permutation $\alpha=(i_1 i_2\dots i_t)$ we see that $(x_1,x_2,\dots,x_n)=(\delta_{1\alpha(1)}, \delta_{2\alpha(2)},\dots,\delta_{n\alpha(n)})\in\mathcal{P}(I_n)$, so as we claim $|\mathcal{P}(I_n)|= 2^n-n.$
If there is any problem with this solution please write a comment and let me know.