Make the sum of integers in a matrix maximal by multiplying rows and columns by -1

Question

Having a Matrix M of size m, n over integers, what would be a good algorithm to transform it such that the sum of all elements is maximal?

The only operations allowed are multiplying by -1 column-wise or row-wise. There can be executed as many such operations as required.

Rough, overall idea: What I have thought about is to move each minus sign from one such negative number to the positive number whose value is smallest, such that the minus would have the least influence on the sum.

Let's take for instance:

import numpy as np

M = np.matrix([
        [2,2,2,2],
        [2,2,-2,2],
        [2,2,2,2],
        [2,2,2,1],
    ])

def invert_at(M, n, m):
    M[n,:] *= -1
    M[:,m] *= -1

I've tried this by building one of the shortest paths from the negative element to the smallest number and invert_at each cell on the way there.

First by including the start and end cells:

invert_at(M, 1, 2)  # start
invert_at(M, 2, 2)
invert_at(M, 3, 2)
invert_at(M, 3, 3)  # end

I end up with:

[[ 2  2 -2 -2]
 [-2 -2 -2  2]
 [-2 -2  2  2]
 [ 2  2 -2 -1]]

which kind of looks interesting. It pushes the minus to the -1 in the bottom right corner, but also to some other areas. Now if I would invert again at the start and the end position (that is, -1 * -1 = 1), so leaving out the start and end cells in the first place, I end up with:

[[ 2  2  2  2]
 [ 2  2 -2  2]
 [-2 -2 -2 -2]
 [-2 -2 -2 -1]]

which looks better, considering I want to get at

[[ 2  2  2  2]
 [ 2  2  2  2]
 [ 2  2  2  2]
 [ 2  2  2 -1]]

by "pushing" the minus towards the right "half" of the matrix.

Talking about "halves", I've also played (a lot) with the idea of using partitions of the matrix, but I couldn't observe any usable patterns.

Most of the things I've tried have led me back to the original matrix and this "avalanche effect" we can observe drives me crazy.

What would be a good approach to solve this problem?

Answer 1

The problem is most likely NP-hard as an instance of pseudo-Boolean function (PB) optimization.

You can denote with Boolean variable x_i the fact "i-th row was negated", and with Boolean variable y_j the fact "j-th column was negated".

Then, the "flip sign" of each matrix element can be described as

 c(i, j) = 1 - 2*x_i - 2*y_j + 4*x_i*y_j .

So, given your matrix M, your problem asks to maximize the PB function

 f = sum A[i,j]*c(i, j) .

Optimization of PB functions is known to be NP-hard, so unless this particular class of functions admits a clever solution, smart brute-forcing (Andrew's solutions) seems the way to go.

There is a nice write-up for a very similar problem in this blog post.

Answer 2

Any of n rows or m columns can be either flipped (-1) or unflipped (1).

This means that the total number of possibilities is 2^(n+m). This means that there is a solution that can be found in exponential time. For small matrices you can use brute force, searching for all possible combinations of flipped and unflipped columns and rows.

You do however need to wait until everything is applied, or you're going to get stuck in local minima.

In this specific case, M is already the maximal sum (27)

import numpy as np

def bit_iter(n):
    for i in xrange(2**(n)):
        bits = []
        for j in xrange(n):
            if i & (2**j) != 0:
                bits.append(1)
            else:
                bits.append(0)
        yield bits

def maximal_sum(M):
    Morig = M.copy()
    n, m = M.shape
    best = None
    for bits in bit_iter(n + m):
        nvec = bits[:n]
        mvec = bits[n:]
        assert(len(nvec) + len(mvec) == len(bits))
        M = Morig.copy()
        for i, v in enumerate(nvec):
            if v == 0:
                M[i, :] *= -1
        for i, v in enumerate(mvec):
            if v == 0:
                M[:, i] *= -1
        if best == None or np.sum(M) > np.sum(best):
            best = M
    return best

M = np.matrix([
    [2,2,2,2],
    [2,2,-2,2],
    [2,2,2,2],
    [2,2,2,1],
])
print maximal_sum(M)
M = np.matrix([
        [1,2],[3,-4]
    ])
print maximal_sum(M)
M = np.matrix([
        [2,-2,2,2],
        [2,2,2,2],
        [2,2,-2,2],
        [2,2,2,2],
        [2,2,2,1],
    ])
print maximal_sum(M)

Gives:

[[ 2  2  2  2]
 [ 2  2 -2  2]
 [ 2  2  2  2]
 [ 2  2  2  1]]
[[-1  2]
 [ 3  4]]
[[ 2 -2  2  2]
 [ 2  2  2  2]
 [ 2  2 -2  2]
 [ 2  2  2  2]
 [ 2  2  2  1]]