Maximum number of different diagonals obtained by column permutations

Question

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.

Answer 1

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.