wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> POSITIVE MATRIX SUMS
        
(Message started by: jonderry on Aug 11^th, 2004, 1:01pm)

Title: POSITIVE MATRIX SUMS
Post by jonderry on Aug 11^th, 2004, 1:01pm

I couldn't find a thread on this problem. Can anyone give me a hint on it?

Title: Re: POSITIVE MATRIX SUMS
Post by Aryabhatta on Aug 11^th, 2004, 10:47pm

Hint:
[hide]
Consider the sum of all entries.
[/hide]

Title: Re: POSITIVE MATRIX SUMS
Post by Eigenray on Aug 12^th, 2004, 10:03am

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.

Title: Re: POSITIVE MATRIX SUMS
Post by Aryabhatta on Aug 12^th, 2004, 11:09am

on 08/12/04 at 10:03:04, Eigenray wrote:

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)

Title: Re: POSITIVE MATRIX SUMS
Post by jonderry on Aug 12^th, 2004, 11:21am

Doesn't [1, 1][-1, 1] work? Any toggling just passes the negative sign around to exactly one other entry.

Title: Re: POSITIVE MATRIX SUMS
Post by Aryabhatta on Aug 12^th, 2004, 12:06pm

on 08/12/04 at 11:21:24, 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)?

Title: Re: POSITIVE MATRIX SUMS
Post by jonderry on Aug 12^th, 2004, 1:59pm

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.

Title: Re: POSITIVE MATRIX SUMS
Post by Aryabhatta on Aug 12^th, 2004, 3:37pm

on 08/12/04 at 13:59:17, 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?

Title: Re: POSITIVE MATRIX SUMS
Post by jonderry on Aug 12^th, 2004, 4:06pm

Yes it was, thanks. I assume it leads directly to the solution:
[hide]
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.
[/hide]

Title: Re: POSITIVE MATRIX SUMS
Post by Aryabhatta on Aug 12^th, 2004, 6:26pm

on 08/12/04 at 16:06:59, 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.

Title: Re: POSITIVE MATRIX SUMS
Post by william wu on Aug 19^th, 2004, 8:25pm

on 08/12/04 at 10:03:04, Eigenray wrote:

Surely the statement should read:

... column, can all be made nonnegative simultaneously.

Being corrected ... thanks for the fix.

Title: Re: POSITIVE MATRIX SUMS
Post by yoyoy on Oct 13^th, 2013, 2:51am

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!

Title: Re: POSITIVE MATRIX SUMS
Post by rmsgrey on Oct 14^th, 2013, 11:07am

on 10/13/13 at 02:51:15, yoyoy wrote:

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.