Consider a 3x3n 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.