Find a matrix satisfying some constraints

Question

Another description of the problem: Calculate a matrix that satisfies certain constraints.

For a function whose only argument is the 4x4 matrix ( int[4][4] matrix), determine the maximum possible output (return value) of this function.

A 4x4 matrix must satisfy the following restrictions:

• All entries are integers from -10 to 10 (inclusive).
• It must be symmetry, entry (x, y) = entry (y, x).
• Diagonal entries must be positive, entry (x, x)> 0.
• The sum of all 16 entries must be 0.

A function should only summarize the values ​​of the matrix, nothing unusual.

My question is:

Given such a function that summarizes certain values ​​of the matrix (the matrix satisfies the above restrictions), how can I find the maximum possible value of the output / return of this function?

For instance:

/* 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. I am currently trying to estimate the number of 4x4 matrices that satisfy the constraints, if the number is small enough, the problem can be solved by brute force.

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

Answer 1

.

, , , .

Python:

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

:

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

, 16, .

, . , , , .

, ( ). , , .

, , .

Answer 2

, . 4 , 4 ( 1), 40 ( ).

16 0 - , () + ( ) = 0.

, () , , ( ) - () * (- 1).

, , , ( ) . , , * (- 1).

. . , 4 , 40. 12 , , -4 ( ).

, :

1) / - 3. 10, 1, 1, 2 (, ), -7.

2) - - 9. , - 1,1 - , , -11.

3) - 14.

4) - 20.

( ) . , .

- , .

Answer 3

Sorting elements in a matrix in descending order and saving in an array. Browse the elements in the array one by one and add it to the variable. Stop iterating at the point when adding an element to a variable decreases its value. The value stored in the variable gives the 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;
}