For an $n \times n$ matrix $M$, the $\infty\to 1$ and [cut](https://en.wikipedia.org/wiki/Matrix_norm#Cut_norms) norms are given by


$$\|M\|\_{\infty \to 1} := \max\limits\_{x, y \in \{\pm 1\}^n} \sum\limits\_{i, j} m\_{i, j} x\_i y\_j, \qquad \|M\|\_{\square} := \max\limits\_{A, B} \left|\sum\limits\_{i \in A, j \in B} m\_{ij}\right|.$$


By expanding to a matrix so that the row and column sums are $0,$ both norms become essentially the same, i.e.,


$$\|M\|\_{\infty \to 1} = 4 \|M\|\_{\square}.$$


The idea is that due to the zero sums, the $1$'s in $x, y$ will represent $A, B$ respectively. This observation and usage of integer programming allows us to approximate the cut norm within a constant factor in polynomial time.


For finite sets $X, Y,$ we say $X < Y$ if $\max X < \min Y.$ I am interested in the following measurement: $$f(M) = \max\limits\_{A < B < C \\ |A|=|B|=|C|} \left(\sum\limits\_{i \in A, j \in C} m\_{ij} - \sum\limits\_{i \in B, j \in C} m\_{ij} \right).$$ Motivation: It's a measure of how much $M$ fails to increase as we move towards the diagonal from above, the useful property being that $f(M) \ge 0$ and $f(M) = 0$ if and only if $M$ increases towards the diagonal. The function $f$ also behaves well with the cut norm.


I can replace $C$ with $y \in \{-1,1\}^n$ and do the same row sum trick. It may be possible to replace $A$ and $B$ with $x \in \{-1, 0, 1\}^n$ and then use the column sum trick. However, there is a major problem: we are only considering $x$ with the same number of $1$s as $-1$s and where all the $-1$'s come after the $1$s.


Each such $x$ corresponds bijectively to a size $2m$ subset of $\{1, 2, \dots, n\}$ by making the first $m$ elements $1,$ the last $m$ elements $-1,$ and the rest $0.$ Thus, ignoring the constraint from $|C|,$ there are $\binom{n}{0} + \binom{n}{2} + \dots = 2^{n-1}$ ways to choose $A, B.$ To choose all of $A, B, C,$ there are of course $\binom{n}{0}+\binom{n}{3}+\dots = \frac{2^n + 2 \cos(n\pi/3)}{3}$ ways.


The cut norm was nicely reduced due to the natural correspondence between the $2^n$ subsets of $\{1, 2, \dots, n\}$ and the elements of $\{-1,1\}^n.$ Since we have neither $2^n$ nor $3^n$ choices for $A, B, C,$ plus the choices are not as clean, I am unable to turn computing $f$ into an integer programming problem. Is it possible in the case $M \ge 0$? It may be possible for all $M$ but I only care about non-negative matrices anyways.



How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?
Given $n \times n$ matrix $M$, you want to find $A,B,C \subset \{1,\dots,n\}$ to maximize
$$\sum\limits\_{i \in A, j \in C} m\_{ij} - \sum\limits\_{i \in B, j \in C} m\_{ij}$$
subject to $A < B < C$ and $|A|=|B|=|C|$.


Introduce binary decision variables $a\_i, b\_i, c\_i \in \{0,1\}$ to indicate whether $i\in A, i\in B, i\in C$, respectively. Introduce decision variable $d$ to represent the common cardinality. The problem is to maximize
$$\sum\_{i=1}^n \sum\_{j=1}^n m\_{ij} (a\_i c\_j - b\_i c\_j)$$
subject to linear constraints
\begin{align}
a\_i + b\_j &\le 1 &&\text{for $i \ge j$} \\
b\_i + c\_j &\le 1 &&\text{for $i \ge j$} \\
\sum\_i a\_i &= d \\
\sum\_i b\_i &= d \\
\sum\_i c\_i &= d \\
\end{align}
This is an integer quadratic programming (IQP) problem, but you can linearize by introducing binary variables $u\_{ij}$ and $v\_{ij}$ to replace the products $a\_i c\_j$ and $b\_i c\_j$, respectively. The resulting integer linear programming (ILP) problem is to maximize
$$\sum\_{i=1}^n \sum\_{j=1}^n m\_{ij} (u\_{ij} - v\_{ij})$$
subject to linear constraints
\begin{align}
a\_i + b\_j &\le 1 &&\text{for $i \ge j$} \\
b\_i + c\_j &\le 1 &&\text{for $i \ge j$} \\
\sum\_i a\_i &= d \\
\sum\_i b\_i &= d \\
\sum\_i c\_i &= d \\
a\_i &\ge u\_{ij} &&\text{for all $i$ and $j$} \tag1\label1 \\
c\_j &\ge u\_{ij} &&\text{for all $i$ and $j$} \tag2\label2 \\
a\_i + c\_j - 1 &\le u\_{ij} &&\text{for all $i$ and $j$}\\
b\_i &\ge v\_{ij} &&\text{for all $i$ and $j$}\\
c\_j &\ge v\_{ij} &&\text{for all $i$ and $j$}\\
b\_i + c\_j - 1 &\le v\_{ij} &&\text{for all $i$ and $j$} \tag3\label3
\end{align}
For nonnegative $m\_{ij}$, you can omit constraints \eqref{1}, \eqref{2}, and \eqref{3}.


