7
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Iosif Pinelis
    Commented Dec 11, 2019 at 2:53
  • $\begingroup$ 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 $\endgroup$
    – alesia
    Commented Dec 11, 2019 at 2:57
  • $\begingroup$ Also I came across Grothendieck inequality and the related SDP relaxation of the cut polytope ("elliptope"), which could help as well $\endgroup$
    – alesia
    Commented Dec 11, 2019 at 3:01
  • $\begingroup$ What bounds provide Hadamard matrices, if you change diagonal elements to zeroes? (There should be many pluses and minuses on the diagonal.) $\endgroup$
    – Ilya Bogdanov
    Commented May 3, 2020 at 17:27
  • $\begingroup$ @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. $\endgroup$
    – alesia
    Commented May 3, 2020 at 17:36

2 Answers 2

Reset to default
1
$\begingroup$

Here I provide further details. There are 3 related quantities: the cut norm of any rectangular matrix cut(M), the taxicab matrix operator norm tmon(M), and Frobenius 1 norm F1n(M). The inequalities among these 3 terms are: cut(M) less than or equal to tmon(M) less than or equal to F1n(M). These can be refined based on different ways of centering the matrix M. a) Two way centering, where the sum of rows are zeros and the sum of columns are zeros. This case is discussed in detail in the following published paper also available on the arxiv, see Choulakian and Abou-Samra (2020) : Mean absolute deviations about the mean, the cut norm, and taxicab correspondence analysis. In this case we have: 4 cut(M) = tmon(M) less than or equal to F1n(M). b) one-way centered, say only column centered, then similar to arguments in Choulakian paper cited above we have: 2 cut(M) less than or equal to tmon(M) less than or equal to F1n(M). c) The sum of all entries is zero, then we'll have: cut(M) less than tmon(M) less than or equal to F1n(M). So a necessary and sufficient condition to have equalities in the 3 quantities are the following 2 conditions that I stated : Given that you are partitioning the square matrix in 4 parts, suppose : 1) in each submatrix the sign of its elements are the same; 2) in each submatrix the absolute value of the sum of the elements are equal, then 4 cut(M) = tmon(M) = F1n(M).

Improve this answer
$\endgroup$
1
  • $\begingroup$ the definition of cut norm that I use is different, $S$ and $T$ are assumed disjoint $\endgroup$
    – alesia
    Commented May 3, 2020 at 17:16
0
$\begingroup$

The attainable upper bound is 4. A sufficient condition is the following: Given that you are partitioning the square matrix in 4 parts, suppose the following two conditions: 1) in each submatrix the sign of its elements are the same; 2) in each submatrix the absolute value of the sum of the elements are equal, then the l1norm is 4 times the cutnorm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ you didn't prove the upper bound though $\endgroup$
    – alesia
    Commented Apr 28, 2020 at 18:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .