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?

$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ It's very easy i don't know why i didn't solve it!any way thank you for answering:) $\endgroup$
    – Lrrr
    Jan 20, 2012 at 17:09
3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Tanks, but i really didn't need detail for answer i just needs main idea. some thing like Brian's answer. $\endgroup$
    – Lrrr
    Jan 20, 2012 at 17:11
  • 1
    $\begingroup$ @AliAmiri: I'll try to read your mind better next time... Or better yet, why not say that in the question to begin with, instead of in a comment after the fact? Something like "I only need a hint" or "please don't post the complete proof, just point me in the right direction". $\endgroup$
    – Arturo Magidin
    Jan 20, 2012 at 17:12
  • $\begingroup$ I voted up your answer! but Brian answer first and I marked his answer.but i think you it is always better to tell the main idea instead of explain the whole answer in such detail.but I'm very thankful for your time. $\endgroup$
    – Lrrr
    Jan 20, 2012 at 17:17
  • 1
    $\begingroup$ @AliAmiri: Different people want different things. If you want to get only the main idea, then say so, clearly and explicitly, in your post. I would have gladly offered only the main idea if I thought that's what you were after, instead of "the answer" (which to me requires not just the final word, but the justification for it). You saved yourself the trouble of writing out that you only wanted "the main idea", but you invited me and others to waste their time by not saying so and waiting until after the fact to complain about it. $\endgroup$
    – Arturo Magidin
    Jan 20, 2012 at 17:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – Henry
    Jan 20, 2012 at 18:33

You must log in to answer this question.

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