For an $n \times n$ matrix $A$, the $\infty\to 1$ and cut norms are given by

$$\|A\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} a_{i, j} x_i y_j, \qquad \|A\|_{\square} := \max\limits_{A, B} \left|\sum\limits_{i \in A, j \in B} a_{ij}\right|.$$

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

$$\|A\|_{\infty \to 1} = 4 \|A\|_{\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.

For an $n \times n$ matrix $M$, the $\infty\to 1$ and cut 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.

For an $n \times n$ matrix $A,$ the $\infty\to 1$ norm is given by $||A||_{\infty \to 1} = \max\limits_{x, y \in \{-1,1\}^n} \sum\limits_{i, j} a_{i, j} x_i y_j$ and the cut norm is given by $||A||_{\square} := \max\limits_{A, B} \left|\sum\limits_{i \in A, j \in B} a_{ij}\right|.$ By expanding to a matrix so that the row and column sums are $0,$ both norms become essentially the same: $||A||_{\infty \to 1} = 4 ||A||_{\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.

For an $n \times n$ matrix $A$, the $\infty\to 1$ and cut norms are given by

$$\|A\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} a_{i, j} x_i y_j, \qquad \|A\|_{\square} := \max\limits_{A, B} \left|\sum\limits_{i \in A, j \in B} a_{ij}\right|.$$

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

$$\|A\|_{\infty \to 1} = 4 \|A\|_{\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.