Author |
Topic: POSITIVE MATRIX SUMS (Read 2511 times) |
|
jonderry
Newbie
Posts: 18
|
 |
POSITIVE MATRIX SUMS
« on: Aug 11th, 2004, 1:01pm » |
 Quote  Modify
|
I couldn't find a thread on this problem. Can anyone give me a hint on it?
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
|
Re: POSITIVE MATRIX SUMS
« Reply #1 on: Aug 11th, 2004, 10:47pm » |
Quote Modify
|
Hint:
Consider the sum of all entries.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: POSITIVE MATRIX SUMS
« Reply #2 on: Aug 12th, 2004, 10:03am » |
Quote Modify
|
Surely the statement should read:
You have an m x n grid with some real numbers in each cell. You can multiply any row by -1, or any column by -1. Show that by making multiplications of this kind, the sum of the numbers in every row, and the sum of the numbers in every column, can all be made nonnegative simultaneously.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: POSITIVE MATRIX SUMS
« Reply #3 on: Aug 12th, 2004, 11:09am » |
Quote Modify
|
on Aug 12th, 2004, 10:03am, Eigenray wrote:Surely the statement should read:
You have an m x n grid with some real numbers in each cell. You can multiply any row by -1, or any column by -1. Show that by making multiplications of this kind, the sum of the numbers in every row, and the sum of the numbers in every column, can all be made nonnegative simultaneously. |
|
Yes. I think Wu needs to change that. The all zero matrix is a trivial counterexample. Can we come up with a non-trivial counterexample, i.e. each row and column has a non-zero element, yet it is not possible to make all the row and column sums positive? (Though it is always possible to make the sums non-negative as the problem should probably have been stated)
|
|
IP Logged |
|
|
|
jonderry
Newbie
Posts: 18
|
|
Re: POSITIVE MATRIX SUMS
« Reply #4 on: Aug 12th, 2004, 11:21am » |
Quote Modify
|
Doesn't [[1, 1][-1, 1]] work? Any toggling just passes the negative sign around to exactly one other entry.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: POSITIVE MATRIX SUMS
« Reply #5 on: Aug 12th, 2004, 12:06pm » |
Quote Modify
|
on Aug 12th, 2004, 11:21am, jonderry wrote:| Doesn't [[1, 1][-1, 1]] work? Any toggling just passes the negative sign around to exactly one other entry. |
|
What I meant was, for each (m,n) can we come up with one counterexample...
for m=2 and n=2.
[1 1]
[-1 1]
will work. Any toggling you do, there will be an *odd* number of -1s, (there can be 3 and not just 1)
For any m > 2 , n > 2 taking copies of this matrix near a diagonal and filling the rest with zeroes should give a counterexample for that (m,n).
What if each entry was non-zero? Can we come up with a counterexample for each (m,n) (or prove otherwise)?
|
|
IP Logged |
|
|
|
jonderry
Newbie
Posts: 18
|
|
Re: POSITIVE MATRIX SUMS
« Reply #6 on: Aug 12th, 2004, 1:59pm » |
Quote Modify
|
For m, n > 1 I think there is a general solution as follows
[(m - 1) (m - 1) (m - 1) ... (m - 1)]
[ 1 -1 1 ... -1]
[ 1 -1 1 ... -1]
.
.
.
[ 1 -1 1 ... -1]
Assume #cols is even.
Without loss of generality, assume row 0 is not toggled.
Then a column must be toggled.
Contradiction (a toggled column cannot be made positive).
If #cols is odd, split a column in half and divide the entries by 2. I think an analogous proof works for this case.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: POSITIVE MATRIX SUMS
« Reply #7 on: Aug 12th, 2004, 3:37pm » |
Quote Modify
|
on Aug 12th, 2004, 1:59pm, jonderry wrote:For m, n > 1 I think there is a general solution as follows
[(m - 1) (m - 1) (m - 1) ... (m - 1)]
[ 1 -1 1 ... -1]
[ 1 -1 1 ... -1]
.
.
.
[ 1 -1 1 ... -1]
|
|
I haven't looked at your proof, but this seems to work.
So i think, Wu must change the riddle, postive to nonnegative on the page.
Was the hint helpful?
|
|
IP Logged |
|
|
|
jonderry
Newbie
Posts: 18
|
|
Re: POSITIVE MATRIX SUMS
« Reply #8 on: Aug 12th, 2004, 4:06pm » |
Quote Modify
|
Yes it was, thanks. I assume it leads directly to the solution:
Consider the setting in which the sum of entries is maximized.
Suppose there were a negative column or row sum.
Then the sum of entries could be increased by inverting
that column or row. Contradiction.
|
| « Last Edit: Aug 12th, 2004, 4:11pm by jonderry » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: POSITIVE MATRIX SUMS
« Reply #9 on: Aug 12th, 2004, 6:26pm » |
Quote Modify
|
on Aug 12th, 2004, 4:06pm, jonderry wrote:Yes it was, thanks. I assume it leads directly to the solution:
|
|
Sorry, I could not think of a better hint.
For an example of a good hint look at Hint 3 of Glass Half Full in the easy riddles section.
|
|
IP Logged |
|
|
|
titan
Newbie
Posts: 33
|
|
Re: POSITIVE MATRIX SUMS
« Reply #11 on: Oct 13th, 2013, 2:51am » |
Quote Modify
|
We consider sum of enteries of each row and column. If sum is negative, we multiply that row/column with a -ve sign.
Now shud one make sure that in this process, some row/column' enteries' sum has been made -ve?
Solution:
"
Consider the setting in which the sum of entries is maximized.
Suppose there were a negative column or row sum.
Then the sum of entries could be increased by inverting
that column or row. Contradiction. "
I think this proof is correct. Someone please verify. Thanks!
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: POSITIVE MATRIX SUMS
« Reply #12 on: Oct 14th, 2013, 11:07am » |
Quote Modify
|
on Oct 13th, 2013, 2:51am, yoyoy wrote:We consider sum of enteries of each row and column. If sum is negative, we multiply that row/column with a -ve sign.
Now shud one make sure that in this process, some row/column' enteries' sum has been made -ve?
Solution:
"
Consider the setting in which the sum of entries is maximized.
Suppose there were a negative column or row sum.
Then the sum of entries could be increased by inverting
that column or row. Contradiction. "
I think this proof is correct. Someone please verify. Thanks! |
|
Looks good.
Strictly, what your proof shows is that if there is a configuration which maximises the sum of entries, then it must have no negative row/column totals, but it's trivial to observe that there are only a finite number of possible configurations, so at least one of them must take the maximal value.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
