For $A\in \{0,1\}^{n\times n}$ we define:
$A_{i\bullet} = \sum_{j=1}^{n}a_{ij}$,
$A_{\bullet j} = \sum_{i=1}^{n}a_{ij},$
$f(A)=\sum_{i,j=1}^{n}|A_{i \bullet} - A_{\bullet j}|^{3}.$
How to maximize this expression over all possible $A$ matrices ($n$ is fixed)?
Computer simulations for small $n$ suggests that there exists Argmax matrix of rank one.
All Armgmax $A$ also seems to be symmetric.
How can this hypothesis be verified? Can You suggest any reasonable way of attacking this problem or any insight?
Let $({\tt1},J)$ denote the all-ones vector and matrix, respectively.
Write the vectors formed from the row/col sums in terms of these. $$\eqalign{ c &\doteq A_{i*} = A{\tt1}\\ r &\doteq A_{*j} = {\tt1}^TA \\ B_{ij} &\doteq |c_i-r_j| = \big|c_i{\tt1}_j-{\tt1}_ir_j\big| \\ B &\doteq \big|A{\tt11}^T-{\tt11}^TA\big| = \big|AJ-JA\big| \\ G &\doteq AJ-JA \\ }$$ An element-wise sign function yields further relationships. $$\eqalign{ S &\doteq {\rm sign}(G) &\implies B=S\odot G,\;G=S\odot B \\ B^{\odot 2} &\doteq B\odot B \\ &= G\odot G \;&\implies G\odot dG = B\odot dB \\ X &= B\odot G \\ &= S\odot G^{\odot 2} \;&\implies S = {\rm sign}(X) \\ }$$ The objective function is the sum of the cube of the (non-negative) elements of $B$. $$\eqalign{ f &\doteq J:(B\odot B\odot B) \\ df &= J:3(B\odot B\odot dB) \\ &= 3(B\odot G):dG \\ &= 3X:(dA\,J-J\,dA) \\ &= 3(XJ - JX):dA \\ \frac{\partial f}{\partial A} &= 3(XJ - JX) \\ }$$ Setting the gradient to zero yields $$\eqalign{ XJ - JX &= 0 \\ }$$ which is a Sylvester equation for $X$.
After solving for $X$, one can calculate $S = {\rm sign}(X)$
And then take the element-wise root to obtain $G=(S\odot X)^{\odot 1/2}$
The definition of $G$ yields another Sylvester equation to be solved for $A$ in terms of $(G,J)$.
The symbol $(\odot)$ denotes the element-wise product and $(:)$ denotes the trace product, i.e. $$A:B = {\rm Tr}(A^TB)\\$$ NB: There will be multiple solutions to the first Sylvester equation, corresponding to local minima and maxima of the objective function.
In particular, the trivial solution $X=0$ yields $\big(G=0,\,A=\alpha I+\beta J+\gamma K,\,f=0\big)\,$
where $(I,K)$ are the identity and counter-identity, respectively.
This solution is the global minimum and should not be selected.
In fact, the objective function can be written in terms of $X$ $$f = J:\big|X\big|^{\odot 3/2}$$ So whichever Sylvester solution maximizes this value is the that should be selected.
More solutions occur at $\,X=\alpha I+\beta J+\gamma K$