Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
It's very easy i don't know why i didn't solve it!any way thank you for answering:) –  Ali Amiri Jan 20 '12 at 17:09

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

share|improve this answer
    
Tanks, but i really didn't need detail for answer i just needs main idea. some thing like Brian's answer. –  Ali Amiri Jan 20 '12 at 17:11
1  
@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". –  Arturo Magidin Jan 20 '12 at 17:12
    
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. –  Ali Amiri Jan 20 '12 at 17:17
1  
@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. –  Arturo Magidin Jan 20 '12 at 17:21
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. –  Henry Jan 20 '12 at 18:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.