Suppose I have a $n\times n$ matrix $X$ such that all its entries sum up to 1 and all entries are non-negative. Then, I have to maximize this quantity: $$\sum_{i=1}^n\sum_{j=1}^n \left|x_{ij}-\left(\sum_{k=1}^{n}x_{ik}\right)\cdot\left(\sum_{k=1}^{n}x_{kj}\right)\right|$$.
So, I think this should be achieved when $X$ is diagonal, but I don't have a concrete argument. I don't really know how to start with this. This is a homework problem and might be related to quadratic mutual information. I am thankful for any hints or solutions.
A partial solution: Write $p_i:=\sum_kx_{ik}$, and $q_j:=\sum_kx_{kj}$ for the marginal sums.
Using the identity $|u|=2uI(u>0)-u$, where $I(\cdot)$ denotes the indicator function, the objective function can be written $$Q:=2\sum_i\sum_j\left( x_{ij}-p_iq_j\right) I\left(x_{ij}>p_iq_j\right).$$
Intuition suggests that the objective function is maximized when the $p_i$'s and $q_j$'s are all equal, but I can't find a watertight argument for this. (Can somebody help out? An appeal to symmetry doesn't seem convincing.)
If we assume that the max occurs when $p_i=q_j=1/n$, then the objective function $Q$ is straightforward to maximize. For each $i$, the inner sum over $j$ is largest when its terms are nonzero for just one $j$, with $x_{ij}$ taking the maximum mass of $1/n$ for that $j$. (Indeed, each additional nonzero term contributes another $-1/n^2$ but the total of the $x_{ij}$ cannot exceed $1/n$.) Summing over $i$ gives $$Q\le 2\left(1-\frac1n\right).$$ This bound is achieved for a diagonal matrix with $1/n$ along the diagonal. Since the objective function is invariant under permutations of the row indices and column indices of $X$, this bound is also achieved for $1/n$ times any $n\times n$ permutation matrix.
Probabilistically, the matrix $X$ can be identified with the joint distribution of a pair of random variables $(A,B)$, with marginal distributions $\{p_i=P(A=a_i)\}$ and $\{q_j=P(B=b_j)\}$. The assertion is that the objective function is maximized for variables that are perfectly aligned under some relabeling of the $\{a_i\}$ and $\{b_j\}$.