## fatemeh8989 3 years ago Help please...!!!! How many matrixes (m*n) there are with 0 & 1 entries such that the number of 1s in every row and every column be an odd number.

• This Question is Open
1. fatemeh8989

I find out the solution I think... Ummm... as an Idea we can think this way... let have A[aij] (m-1 * n-1 ) any matrix with entries with o and 1. how many matrixes there are so..? any entry can be 1 or 0... so we have 2^(m-1)(n-1) such matrixes. now we add last row and column... but... if the number of 1s in m-1 entries in a row be odd we put last entry 0, else put it 1. so last row and column will fill this way that will fulfill the situation... but this adding dont add any new case to our previous existing matrixes... it is almost done... but there was some important points... adding 1 or 0 will not disturb the situation of rows and columns that have been made before.. IF : if m be odd then n be odd... or if m be even then n be even too. the point I was doubting before i submit this,,.. was that is there any other matrixes that : m be odd and n be even or n be odd and m be even... i dont have any proof for this but can say that such a matrix can't be found in these conditions.. ( rows and columns with odd number of 1 ) so the number of such a matrixes is 2^(m-1)(n-1)... I will be approciated for any better idea. thanks :)

2. Neemo

you're question seems interesting ! I'll share with you this quick and simple idea ! ( I wish you'll accept it ). m and n have symmetric roles...so we can suppose that m is odd and n is even ! if we suppose that such matrix A (as described) exist $A= \left[ a_ij \right].............1 \le i \le m .......1\le j \le n$ with $a_{ij} \in \left\{ 0,1 \right\}$ we have $\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}=\sum_{j=1}^{n}\sum_{i=1}^{m}a_{ij}$ now we just have to notice that $\sum_{i=1}^{m}a_{ij}$ is the number of 1s in the column j so we can say that $\sum_{i=1}^{m}a_{ij}=2p_j+1....p_j \in \left\{ 0,1,2.....idc \right\}$ same for the row i $\sum_{j=1}^{n}a_{ij}=2q_i+1........q_i \in \left\{ 0,1,2......idc \right\}$ then $\sum_{i=1}^{m}(2q_i+1)=\sum_{j=1}^{n}(2p_j+1)$ $2(\sum_{i=1}^{m}q_i)+m=2(\sum_{j=1}^{n}p_j)+n$ It's absurd an odd number cann't be even !! I didn't check your answer btw ! so I'll do it next time !Srry ! I'm really busy I don't have too much time ! WISH me Luck ! ( I really need it )

3. fatemeh8989

thanks , i have to think in ur answer as soon as i get enough time. thank you soooo much :) and I hope u overcome ur works perfectly.

4. Neemo

yw....It wasn't a full answer ! I just "proved" what you've said before:"but can say that such a matrix can't be found in these conditions"... What you said about "adding 1 or 0 will not disturb the situation of rows and columns that have been made before" is correct (not bad idea btw ) ! because the map you choosed the matrixes matrixes (m-1*n-1) that satisfies those conditions-----> matrixes (m*n) (that satifies those conditions ) is one-to-one (but not onto map...)...But what I didn't understand is how did you deduce the formula 2^(m-1)(n-1)....if that "adding 0 or 1" was you're only argument ! then ! also adding (0,1) or (1,0) if the number of 1s is even ...else adding (1,1) or (0,0) (just -like- what you did but twice ) this wouldn't disturb the sitiuation too...but...you can conclude nothing ! I spent more than an hour thinking about a solution ! I made no progress at all(I'm really interested if you did) ! even if you specify an exact value of the number of the 1s...It won't be easy too ! maybe @mukushla and others could help !

5. fatemeh8989

about the questions u asked of my answer: first, the number is: 2^(m-1)(n-1) , look, the idea is that we ignore last row and last column, for remained matrix we have NO condition to fill, how many entries we have? (m-1)(n-1) . any entry can be 1 or 0 . so according the counting theory,there is 2^(m-1)(n-1) possibilities. I said thats the whole answer because If i back to the last row and column i have no choice for putting, but I just only can look to that 2^(m-1)(n-1) matrices, one by one) and see if the column has odd number of 1 i have to put 0 , else put 1, so new matrices will not be created. so the whole answer is 2^(m-1)(n-1). second, about adding 1 two times, it is not possible in this method, because we just ignored 1 row so in every row we can add only one more element, in column same as row.

6. Neemo

Sorry! if I didn't understand what you did ! (and doubt it a lot ) ! you're answer is very intuitive ! Yes ! You were right ! while attaching a solution....I just noticed that I did the same !(just with a lot of boring notations !) I'm just wondering how did you find the last {0or1}"[m][n]" ? (explain it to me again !please ! if you clarified that before ) because this one should satisfy two conditions ! Ps: What you did can be done using any row and any column ! (I choosed the first ones ) Thank you for your answer ! I'm the one who was helped here !