1

Given $m$, $n$. Are there any methods for generating an $m\times n$ matrix whose entries are $0$ and $1$ such that all its submatrices are not equal?

For example, all submatrices of the following $4\times 4$ matrix are not equal ( e.g. $\begin{bmatrix}1&0\\0&1\end{bmatrix} \neq \begin{bmatrix}1&0\\1&1\end{bmatrix} \neq \begin{bmatrix}1&1\\0&0\end{bmatrix}$ and so on). enter image description here

Any information or references are appreciated. Thank you.

1 Answers1

3

There are only $2^4=16$ different $2\times 2$ matrices, so your matrix cannot contain more then $16$ matrices of size $2\times 2$. In general the matrix does not exist for any $m\times n$.

More over, you can see that there are $(m-1)(n-1)$ matrices of size $2\times 2$ hence $(m-1)(n-1)\leq 16$ is a necessary condition for the existence of such a matrix, turns out this is also sufficient if you don't also consider matrices of size $1\times k$ or $k\times 1$.

P. Quinton
  • 6,031