Given a list of entries entryList, determine a 4x4 matrix of which you sum up the entries specified in entryList such that there is no other matrix for which the sum of entries specified in entryList is greater.

In other words: entryList specifies some entries, now imagine an arbitrary 4x4 matrix m, entryList tells us which entries of m should be summed up. Summing up a matrix with a given entryList means summing up all entries of the matrix which are specified in entryList. (the examples will make this clearer).

The 4x4 matrix must satisfy the following constraints:

  1. All entries are integers between -10 and 10 (inclusively).
  2. It must be symmetric, 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.

My question:

Given such an entryList how do I compute the maximal possible sum (the actual matrix is not necessary) of any 4x4 matrix which satisfies the constraints above?

In other words: determine for which matrix the sum of entries specified in entryList is maximal, output that sum.

For example (Javaish code):

List<MatrixEntry> entryList = new ArrayList<>();

// for this example I arbitrarily chose entries (0,0), (1,2), (0,3), (1,1).
entryList.add(new Entry(0,0));
entryList.add(new Entry(1,2));
entryList.add(new Entry(0,3));
entryList.add(new Entry(1,1));

int result = computeMaxSum(entryList);

/* The result (maximal possible sum for any valid 4x4 matrix) 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:

entryList = new ArrayList<>();

// for this example I arbitrarily chose entries (0,3), (0,1), (0,1), (0,4), ...
entryList.add(new Entry(0,3));
entryList.add(new Entry(0,1));
entryList.add(new Entry(0,1));
entryList.add(new Entry(0,3));
entryList.add(new Entry(0,3));
entryList.add(new Entry(0,2));
entryList.add(new Entry(1,2));
entryList.add(new Entry(2,1));
entryList.add(new Entry(3,1));
entryList.add(new Entry(1,3));
entryList.add(new Entry(2,3));
entryList.add(new Entry(3,2));

int result = computeMaxSum(entryList);

/* The result (maximal possible sum for any valid 4x4 matrix) 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      */

My current unfinished approach:

The only thing that comes to my mind is solving it by brute force.

Some observations:

The equality sumOfTheLowerLeftPart + sumOfTheUpperRightPart + diagonal = 0 holds since the sum of all entries must be 0.

It's also true that sumOfTheLowerLeftPart = -1 * sumOfDiagonal/2 and sumOfTheUpperRightPart = -1 * sumOfDiagonal/2, since the matrix is symmetric and the diagonal entries must be positive.

So I want to maximize the value of entries in the matrix which are specified in entryList, the rest of the entries are irrelevant for the resulting sum and should be set such that the constraints on the matrix are satisfied. I start with the maximum possible assignment of values to entries specified by entryList (set all the entries to 10), then I check if I can fill out the rest of the entries such that my matrix satisfies all of the constraints. If it is possible to do so, we are done, output the sum of the entries, if it is not possible to fill out the rest such that the matrix satisfies the constraints then move onto the next best assignment of values to entries (decrement the value of the entry which appears the least amount of times in entryList). Repeat till a valid assignment is found or all options are exhausted.

The steps are:

  1. Iterate through all possible assignments of values to entries which matter for the sum (are specified by entryList).
  2. Check for the current assignment if the rest of the matrix can be filled out such that all constraints on the matrix are satisfied.
  3. If step 2 is possible (all entries are filled out and satisfy all of the constraints) then output the sum of entries specified by entryList.
  4. Otherwise, if step 2 is not possible, continue with the iteration of step 1.

What do you think of my approach?

Ideally there would be some well studied problem to which my problem can be reduced to, unfortunately none come to my mind.

I want to conceptually solve this problem so that I can implement a solution later (I'm using Java if that's of any relevance).

  • $\begingroup$ Cross-posted on SO and CS.SE: stackoverflow.com/q/44787848/781723, stackoverflow.com/q/44781005/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. Also, you've asked essentially the same question 3 times on Stack Overflow, with no indication in the question that you got suggestions (which is poor form), and one of the techniques suggested the first time you asked can be used to answer the other versions too. $\endgroup$ – D.W. Jun 28 '17 at 23:04
  • $\begingroup$ I'm voting to close this question because it was cross-posted on SO. $\endgroup$ – D.W. Jun 28 '17 at 23:05

You have 10 variables $x_1,\dots,x_{10}$ (representing the entries on and above the diagonal, in the matrix), with constraints that:

  • Each $x_i$ is an integer in the range $-10 \le x_i \le 10$.

  • The first four are non-negative, i.e., $x_1>0$, $x_2>0$, $x_3>0$, $x_4>0$.

  • A certain sum must be equal to zero, namely,

    $$x_1 + x_2 + x_3 + x_4 + 2 x_5 + 2 x_6 + 2 x_7 + 2 x_8 + 2 x_9 + 2 x_{10} = 0.$$

You are given a subset $S$ of the variables, and you want to find an assignment to the variables that maximizes the sum of the variables in that subset, i.e., you want to maximize $\sum_{i \in S} x_i$.

On approach is to formulate this as an integer linear programming problem. The problem is small enough that any off-the-shelf ILP solver should be able to solve it without difficulty. Indeed, even ordinary linear programming might suffice.

A possible greedy algorithm is: pick elements from $S$ one at a time (preferring elements on the diagonal over non-diagonal elements, but otherwise in any arbitrary order), and assign them the value 10. At each step, look for any assignment to the yet-to-be-assigned variables that satisfies the constraints (e.g., make all unselected diagonal elements be 1, except that if there is an odd number of unselected diagonal elements, make one of them be 2; then assign values to the other unselected non-diagonal elements so that things sum to zero). In each step, we set one more element from $S$ to 10, then look for a reasonable way to fill in values for the unassigned variables. This gives you a sequence of candidate matrices, one per step. Choose the best one, i.e., the one where the sum of desired elements is the largest. I'll leave it to you to verify whether or not this is correct.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.