# Cut norm versus $l_1$ norm

Let $$K$$ be the set of $$n\times n$$ matrices with zero diagonal entries and such that the sum of all entries is zero.

The cut norm of a $$n\times n$$ matrix $$M$$ is:

$$cut(M) = \sup_{S, T, S\cap T = \emptyset} \left \vert \sum_{i\in S, j\in T} M_{ij}\right \vert$$

How large can $$\sum_{ij}\vert M_{ij}\vert$$ be for a matrix $$M$$ in $$K$$ with cut norm $$1$$?

Is it possible to build explicit matrices attaining a high value?

• Have you tried to find the extreme points of the set of matrices in $K$ with cut norm $1$? Then you can maximize $\sum_{ij}|M_{ij}|$ "just" over such extreme matrices. Dec 11, 2019 at 2:53
• I had tried that but very little is known about the extreme points, there are papers on very specific families but that's all. Meanwhile I found that Hadamard matrices are close to being examples of what I want although they don't exactly match the conditions Dec 11, 2019 at 2:57
• Also I came across Grothendieck inequality and the related SDP relaxation of the cut polytope ("elliptope"), which could help as well Dec 11, 2019 at 3:01
• What bounds provide Hadamard matrices, if you change diagonal elements to zeroes? (There should be many pluses and minuses on the diagonal.) May 3, 2020 at 17:27
• @IlyaBogdanov You'd need to fix the zero sum row constraint as well, but I think this would give $\Theta(\sqrt n)$. It sounds plausible that this behavior is optimal, but I'm not sure. May 3, 2020 at 17:36

• the definition of cut norm that I use is different, $S$ and $T$ are assumed disjoint May 3, 2020 at 17:16