3
$\begingroup$

We have a matrix $S$. Every $S_{ij}$ is equal to $1$ or $-1$. How many matrices we can have so that product of all entries in every row and column is $1$?

This means number of $-1$ must be even in all rows and columns. And size of $S$ is $m\times n$.

My idea was that we can divide a matrix of $(m-1)\times (n-1)$, then count all the possible ways this matrix can have $1$ and $-1$ which is $2^{(m-1)(n-1)}$. Then add other part of matrix and set those values in a way that number of $-1$ become even. But this way doesn't work.

Sorry if I didn't explain my way very clearly, it's because English is not my native language.

$\endgroup$
1
  • 3
    $\begingroup$ Two hints : How many $-1$ required in any row or column? You have almost solved the problem. $\endgroup$
    – cosmo5
    Oct 7, 2020 at 18:30

1 Answer 1

3
$\begingroup$

Consider an example : $$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline 1 & -1 & -1 & -1 & 1 & 1 & -1 & \color{blue}{1}\\ \hline 1 & -1 & 1 & -1 & 1 & -1 & 1 & \color{blue}{-1}\\ \hline -1 & 1 & 1 & 1 & 1 & -1 & -1 & \color{blue}{-1}\\ \hline -1 & 1 & -1 & -1 & 1 & -1 & 1 & \color{blue}{1}\\ \hline 1 & 1 & -1 & -1 & -1 & 1 & 1 & \color{blue}{-1}\\ \hline \color{blue}{1} & \color{blue}{1} & \color{blue}{-1} & \color{blue}{1} & \color{blue}{-1} & \color{blue}{-1} & \color{blue}{1} & \color{red}{-1}\\ \hline \end{array} $$

The table is a valid $m\times n$ matrix. Black entries denote $(m-1)\times (n-1)$ matrix.

Key observation :

  • Last entry (in any row/column) = Product of all other entries (in respective row/column)

So all the last entries (colored) are uniquely determined, once entries of $(m-1)\times (n-1)$ matrix are arbitrarily chosen. Hence answer is $$2^{(m-1)(n-1)}$$

Note the peculiarity about corner entry. Product of last column blue entries = Product of all black entries = Product of last row blue entries = Red entry

$\endgroup$
2
  • $\begingroup$ but how can we be sure the last row and column are valid? maybe the last row has even -1s and last column has odd, what will be the last number? $\endgroup$ Oct 8, 2020 at 18:27
  • 1
    $\begingroup$ Added explanation. See answer. $\endgroup$
    – cosmo5
    Oct 8, 2020 at 19:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .