Maximum number of different diagonals obtained by column permutations Consider a n x n matrix with entries being only '0' and '1'.
For example:
$\left( \begin{array}{ccc} 1 & 0 & 1\\1 & 1 & 0\\0&0&1\end{array}\right)$
We then consider all column permutations of the matrix, and count the different types of diagonals starting from bottom left to upper right:
Number 1) $\left( \begin{array}{ccc} 1 & 0 & 1\\1 & 1 & 0\\0&0&1\end{array}\right)$
Diagonal: 011
Number 2)$\left( \begin{array}{ccc} 1 & 1 & 0\\1 & 0 & 1\\0&1&0\end{array}\right)$
Diagonal: 000
Number 3)$\left( \begin{array}{ccc} 0 & 1 & 1\\1 & 1 & 0\\0&0&1\end{array}\right)$
Diagonal: 011
Number 4)$\left( \begin{array}{ccc} 0 & 1 & 1\\1 & 0 & 1\\0&1&0\end{array}\right)$Diagonal: 001
Number 5)$\left( \begin{array}{ccc} 1 & 1 & 0\\0 & 1 & 1\\1&0&0\end{array}\right)$ Diagonal: 110
Number 6)$\left( \begin{array}{ccc} 1 & 0 & 1\\0 & 1 & 1\\1&0&0\end{array}\right)$ Diagonal: 111
There are a total number of 5 different possible diagonals: 011, 000, 001, 110, 111.
The question is, given any such matrix with entries being '0' and '1', what is the maximum number of possible diagonals?
I have tried some conjectures and seems that the formula of maximum diagonals seem to be $2^n-n$. For instance $2^3-3=5$. 
Thanks for any help in finding the general formula for the maximum number of diagonals, among all n x n matrices (for a fixed n, among all matrices)!


*

*The matrix can be any n x n matrix, as long as it yields the maximum number of different diagonals with respect to column permutations.

 A: 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.
