7
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ If you are more interested in the result than a general formula (or just want to verify your hypothesis) it would be an easy task to compute all possibilties. Have you thought about that? $\endgroup$ – user127.0.0.1 Jan 25 '14 at 6:48
  • 1
    $\begingroup$ Is your question "what is the maximum number of diagonals for any given matrix?" or "What is the maximum number of diagonals among all such matrices?" $\endgroup$ – Zackkenyon Jan 25 '14 at 7:06
  • $\begingroup$ Thanks Zackkenyon, my question is the latter: "What is the maximum number of diagonals among all such matrices?" $\endgroup$ – yoyostein Jan 25 '14 at 7:44
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.