Algorithm for finding maximal "reduction" of an integer matrix

Question

Given a $m\times n$ matrix of non-negative integers. A "reduction" of this matrix can be done on one row/column of this matrix, by subtracting the minimum of the row/column from all other numbers of that row/column. For example,

$$ \begin{bmatrix} 29 & 19 & 17 & 12 \\ 32 & 30 & 26 & 28 \\ 3 & 21 & 7 & 9 \\ 18 & 13 & 10 & 15 \end{bmatrix} $$

can be "reduced" on the second row by subtracting 26 from all four numbers, resulting in

$$ \begin{bmatrix} 29 & 19 & 17 & 12 \\ 6 & 4 & 0 & 2 \\ 3 & 21 & 7 & 9 \\ 18 & 13 & 10 & 15 \end{bmatrix} $$

Such reduction can be repeatedly done on every row/column, and the result is always still a non-negative integer matrix. On the other hand, each row/column can be effectively reduced only once, because subsequent reductions end up subtracting 0 and do not change the matrix.

Hence, reduce each row and column once in any order, and the matrix is completely reduced. The question is: consider the sum of numbers in the final matrix, what is the minimum of this sum, among all possible completely reduced matrices? Further, how do we find out an ordering of reductions that achieves the minimum?

The order of reduction does affect the sum of numbers in the final matrix. For the matrix above, reducing [row 1, row 2, row 3, row 4, col 2] gives a sum of 73, while reducing [col 1, col 2, col 3, col 4, row 1, row 2] gives a sum of 81.

---

I am interested in an (efficient) algorithm that solves this problem (or better still, if there exists a closed form of the minimum). One can always brute-force through all $(m+n)!$ ordering of reductions and find the minimum, but that would be quite uninteresting.

Answer 1

Lets first assume that we are allowed to reduce a row or column by a chosen amount, and not necessarily doing a full reduction.

Let $A =(a_{i,j})_{1\leq i \leq m, 1\leq j \leq n}$ be the matrix. Let $x_i$ be the amount reduced in on the line $i$ and $y_i$ be the amount reduced in on the column $i$. We want to minimize $\sum_{i,j} a_{i,j} - x_i - y_j$, under the constraints $x, y \geq 0$, $x_i + x_j \leq a_{i,j}$. This is a linear program, so it can be solved efficiently. Moreover, the underlying matrix is totally unimodular, so we have strongly polynomial algorithm, and if $A$ is an integer matrix, we will get an integer optimal solution.

Let $G$ be the complete bipartite graph formed with $m$ vertices $X_i$ in one part and $n$ vertices $Y_i$ in the other part, and let $a_{i,j}$ be the weight of the edge $(X_i,Y_j)$. Then the problem becomes equivalent to find a vertex-weight function $x, y \geq 0$ (with $x_i$ the weight of vertex $X_i$, and $y_i$ the weight of vertex $Y_i$) such that $a_{i,j} \geq x_i + x_j$. Shrijver[1] refers to it as the w-stable set problem.

Now, lets show that we can find on ordering of the rows and columns such that at each step, the reduction is maximal. Assume that $\forall i,j$, $a_{i,j} > x_i$, $a_{i,j} > y_j$. Then it is possible to increase any $x$ or $y$ and get a better solution. So lets choose an $a_{i,j}$ such $a_{i,j} = x_i$ (or $a_{i,j} = y_i)$, and lets reduce the corresponding row (or column). Let set $x_i = 0$, the coefficients must still form an optimal solution, so we can keep going until we reduced everything.

[1]: Schrijver, Alexander, Combinatorial optimization. Polyhedra and efficiency (3 volumes), Algorithms and Combinatorics 24. Berlin: Springer (ISBN 3-540-44389-4/hbk). xxxvii, 1881 p. (2003). ZBL1041.90001.