Binary submodular matrix

50 Views Asked by At

An $m \times n$ matrix $X = (x_{i,j})$ is defined submodular if

$$ x_{i_1,j_1} + x_{i_2,j_2} \le x_{i_1,j_2} + x_{i_2,j_1}$$

for all $1 \le i_1 < i_2 \le m$ and $1 \le j_1 <j_2 \le n$. Is it possible to permute every $\{0,1\}$-matrix $X$ in order to make it submodular?