2
$\begingroup$

If two $n×m$ binary matrices have the same row weights, column weights, upper-diagonal weights and lower-diagonal weights, are they necessarily identical?

The weight of a given row, column, or diagonal is the number of entries with $1$ in that row, column, or diagonal.

The following matrix:$$ \begin{pmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 1 & 1 & 0 \end{pmatrix} $$ has the row, column, and diagonal weights:

Row: $2, 2, 2$

Col: $2, 2, 2$

Upper diagonal: $1, 0, 3, 2, 0$

Lower diagonal: $1, 1, 2, 1, 1$

At first I considered only when the row and column weights are the same. I found a counter example. Then I considered only when the upper and lower diagonals weights. Yet again, I found a counter example.

How can one going about proving it? Or does anyone have a counter example? I have no been able to find one thus far.

$\endgroup$
  • $\begingroup$ What do these weights even mean? $\endgroup$ – darij grinberg Mar 16 '18 at 0:43
  • 1
    $\begingroup$ Pigeonhole proof: there are $2^{n^2}$ such matrices, but at most $(n+1)^{6n}$ such configurations of weights ($n+n+2n+2n$ different weights, each of which takes a value in $\{0,\dots,n\}.$ The $2^{n^2}$ is bigger for sufficiently large $n.$ $\endgroup$ – Dap Mar 16 '18 at 9:01
2
+50
$\begingroup$

Take$$ A = \begin{pmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 \end{pmatrix}, \quad B = \begin{pmatrix} 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 \end{pmatrix}. $$

$\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.