Find a matrix which satisfies certain constraints

Question

Another description of the problem: Compute a matrix which satisfies certain constraints

Given a function whose only argument is a 4x4 matrix (int[4][4] matrix), determine the maximal possible output (return value) of that function.

The 4x4 matrix must satisfy the following constraints:

1. All entries are integers between -10 and 10 (inclusively).
2. It must be symmetrix, entry(x,y) = entry(y,x).
3. Diagonal entries must be positive, entry(x,x) > 0.
4. The sum of all 16 entries must be 0.

The function must only sum up values of the matrix, nothing fancy.

My question:

Given such a function which sums up certain values of a matrix (matrix satisfies above constraints), how do I find the maximal possible output/return value of that function?

For example:

/* The function sums up certain values of the matrix, 
   a value can be summed up multiple or 0 times. */

// for this example I arbitrarily chose values at (0,0), (1,2), (0,3), (1,1).
int exampleFunction(int[][] matrix) {
    int a = matrix[0][0];
    int b = matrix[1][2];
    int c = matrix[0][3];
    int d = matrix[1][1];

    return a+b+c+d;
}

/* The result (max output of the above function) is 40, 
   it can be achieved by the following matrix: */
    0.   1.   2.   3.
0.  10  -10  -10   10
1. -10   10   10  -10
2. -10   10    1   -1
3.  10  -10   -1    1


// Another example:

// for this example I arbitrarily chose values at (0,3), (0,1), (0,1), (0,4), ...
int exampleFunction2(int[][] matrix) {
    int a = matrix[0][3] + matrix[0][1] + matrix[0][1];
    int b = matrix[0][3] + matrix[0][3] + matrix[0][2];
    int c = matrix[1][2] + matrix[2][1] + matrix[3][1];
    int d = matrix[1][3] + matrix[2][3] + matrix[3][2];

    return a+b+c+d;
}

/* The result (max output of the above function) is -4, it can be achieved by 
   the following matrix:  */
    0.   1.   2.   3.
0.   1   10   10  -10
1.  10    1   -1  -10
2.  10   -1    1   -1
3. -10  -10   -1    1

I don't know where to start. Currently I'm trying to estimate the number of 4x4 matrices which satisfy the constraints, if the number is small enough the problem could be solved by brute force.

Is there a more general approach? Can the solution to this problem be generalized such that it can be easily adapted to arbitrary functions on the given matrix and arbitrary constraints for the matrix?

Answer 1

You can try to solve this using linear programming techniques.

The idea is to express the problem as some inequalities, some equalities, and a linear objective function and then call a library to optimize the result.

Python code:

import scipy.optimize as opt
c = [0]*16
def use(y,x):
    c[y*4+x] -= 1

if 0:
    use(0,0)
    use(1,2)
    use(0,3)
    use(1,1)
else:
    use(0,3)
    use(0,1)
    use(0,1)
    use(0,3)
    use(0,3)
    use(0,2)
    use(1,2)
    use(2,1)
    use(3,1)
    use(1,3)
    use(2,3)
    use(3,2)
bounds=[ [-10,10] for i in range(4*4) ]
for i in range(4):
    bounds[i*4+i] = [1,10]
A_eq = [[1] * 16]
b_eq = [0]
for x in range(4):
    for y in range(x+1,4):
        D = [0]*16
        D[x*4+y] = 1
        D[y*4+x] = -1
        A_eq.append(D)
        b_eq.append(0)

r = opt.linprog(c,A_eq=A_eq,b_eq=b_eq,bounds=bounds)
for y in range(4):
    print r.x[4*y:4*y+4]
print -r.fun

This prints:

[  1.  10. -10.  10.]
[ 10.   1.   8. -10.]
[-10.   8.   1. -10.]
[ 10. -10. -10.   1.]
16.0

saying that the best value for your second case is 16, with the given matrix.

Strictly speaking you are wanting integer solutions. Linear programming solves this type of problem when the inputs can be any real values, while integer programming solves this type when the inputs must be integers.

In your case you may well find that the linear programming method already provides integer solutions (it does for the two given examples). When this happens, it is certain that this is the optimal answer.

However, if the variables are not integral you may need to find an integer programming library instead.

Answer 2

Sort the elements in the matrix in descending order and store in an array.Iterate through the elements in the array one by one and add it to a variable.Stop iterating at the point when adding an element to variable decrease its value.The value stored in the variable gives maximum value.

maxfunction(matrix[][])
{
array(n)=sortDescending(matrix[][]);
max=n[0];
i=1;
    for i to n do
     temp=max;
     max=max+n[i];
     if(max<temp)
       break;

return max;
}

Answer 3

You need to first consider what matrices will satisfy the rules. The 4 numbers on the diagonal must be positive, with the minimal sum of the diagonal being 4 (four 1 values), and the maximum being 40 (four 10 values).

The total sum of all 16 items is 0 - or to put it another way, sum(diagnoal)+sum(rest-of-matrix)=0.

Since you know that sum(diagonal) is positive, that means that sum(rest-of-matrix) must be negative and equal - basically sum(diagonal)*(-1).

We also know that the rest of the matrix is symmetrical - so you're guaranteed the sum(rest-of-matrix) is an even number. That means that the diagonal must also be an even number, and the sum of the top half of the matrix is exactly half the diagonal*(-1).

For any given function, you take a handful of cells and sum them. Now you can consider the functions as fitting into categories. For functions that take all 4 cells from the diagonal only, the maximum will be 40. If the function takes all 12 cells which are not the diagonal, the maximum is -4 (negative minimal diagonal).

Other categories of functions that have an easy answer:

1) one from the diagonal and an entire half of the matrix above/below the diagonal - the max is 3. The diagonal cell will be 10, the rest will be 1, 1, 2 (minimal to get to an even number) and the half-matrix will sum at -7.

2) two cells of the diagonal and half a matrix - the max is 9. the two diagonal cells are maximised to two tens, the remaining cells are 1,1 - and so the half matrix sums at -11.

3) three cells from the diagonal and half a matrix - the max is 14.

4) the entire diagonal and half the matrix - the max is 20.

You can continue with the categories of selecting functions (using some from the diagonal and some from the rest), and easily calculating the maximum for each category of selecting function. I believe they can all be mapped.

Then the only step is to put your new selecting function in the correct category and you know the maximum.