3
$\begingroup$

How many $m\times n$ tables are there if they are subject to the following two conditions?

  1. In each cell of the table we have $1$ or $-1$.

  2. The product of all the cells in any given row and the product of all cells in any given column equals $-1$.

I already know if Parity of $m$ and $n$ are different there is no such a table. what is the answer in general?

2 Answers 2

8

So you have an odd number of $-1$ entries in each row and each column. Assume that $m$ and $n$ have the same parity. You can put any odd number of $-1$’s in each of the first $n-1$ columns, and then you can complete the array by filling in the last column to get the row parities right. Since $m\equiv n\pmod 2$, the last column will automatically have an odd number of $-1$’s.

There are $m$ positions in each column, and we have to choose a subset of them of odd cardinality. Exactly half of the subsets of an $n$-element set have odd cardinality, so there are $2^{n-1}$ possible sets of positions for the $-1$’s in a column. The total number of arrays is therefore $(2^{n-1})^{m-1}=2^{(n-1)(m-1)}$, if $m\equiv n\pmod 2$, and $0$ otherwise.

  • 0
    It's very easy i don't know why i didn't solve it!any way thank you for answering:)2012-01-20
3

Fill in the upper left $(m-1)\times(n-1)$ table any which way. The first $n-1$ entries of the $i$th row ($1\leq i\leq m-1$) force the $n$th entry; the entries first $m-1$ entries in the $j$th column ($1\leq j\leq n-1$) force the $m$th entry. The only question is whether the $(m,n)$ entry can be filled in.

Let $a_{ij}$ be the $(i,j)$th entry, $1\leq i\leq m-1$, $1\leq j\leq n-1$. Then $a_{i,n} = -\prod\limits_{j=1}^{n-1}a_{i,j}$, and $a_{m,j} = -\prod\limits_{i=1}^{n-1}a_{i,j}$.

For the last column to satisfy condition $2$, you need $a_{m,n}$ to satisfy $a_{m,n} = -\prod\limits_{i=1}^{n-1}a_{i,n} = -\prod\limits_{i=1}^{n-1}\left(-\prod_{j=1}^{m-1}a_{i,j}\right) = -(-1)^{n-1}\prod_{i=1}^{n-1}\prod_{j=1}^{m-1}a_{i,j} = (-1)^n\prod_{\stackrel{\scriptstyle1\leq i\leq n-1}{1\leq j\leq m-1}}a_{ij},$ and for the last row to satisfy condition $2$ you need $a_{m,n}$ to satisfy $a_{m,n} = -\prod\limits_{j=1}^{m-1}a_{m,j} = -\prod\limits_{j=1}^{m-1}\left(-\prod_{i=1}^{n-1}a_{i,j}\right) = -(-1)^{m-1}\prod_{j=1}^{m-1}\prod_{i=1}^{n-1}a_{i,j} = (-1)^m\prod_{\stackrel{\scriptstyle1\leq i\leq n-1}{1\leq j\leq m-1}}a_{ij}.$ This gives the necessary condition that $m\equiv n\pmod{2}$; conversely, if $m\equiv n\pmod{2}$, then you can do it.

So the answer is that there are $2^{(n-1)(m-1)}$ possible tables when $m\equiv n\pmod{2}$, and $0$ if $m\not\equiv n\pmod{2}$.

  • 1
    I think the first and last paragraphs are what was needed: the middle part looks more complicated than necessary since the project of all the entries in the matrix must be both $(-1)^m$ and $(-1)^n$, so $m$ and $n$ must have the same parity, and if they are the same then the $(m,n)$ entry can be adjusted so $\prod_{i=1}^{n}\prod_{j=1}^{m}a_{i,j}$ is also equal to those two.2012-01-20