Skip to main content
edited body
Source Link
alesia
  • 2.8k
  • 9
  • 21

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\subset \{1\ldots n\}} \left \vert \sum_{i\in S, j\notin S} M_{ij}\right \vert $$$$ 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?

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\subset \{1\ldots n\}} \left \vert \sum_{i\in S, j\notin S} 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?

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?

Source Link
alesia
  • 2.8k
  • 9
  • 21

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\subset \{1\ldots n\}} \left \vert \sum_{i\in S, j\notin S} 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?