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;
}