Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & \vdots & \ddots &  \vdots \\
p_{J-1,0} & p_{J-1, 1} & \ldots & p_{J-1,J-1} \\
\end{array} \right)
\quad
(0 \le p_{kl} \le 1, \;\; \sum_{k=0}^{J-1}\sum_{l=0}^{J-1}p_{kl} = 1)
\end{equation*}
with fixed row and column sums
\begin{equation*}
p_{k+} = \sum_{l^\prime=0}^{J-1}p_{kl^\prime},
\quad
p_{+l} = \sum_{k^\prime =0}^{J-1}p_{k^\prime l}
\quad
(k, l = 0, 1, \ldots, J-1),
\end{equation*}
Calculate the closed-form expressions for the minimum and maximum values of
\begin{equation*}
\Delta = \mathop{\sum\sum}_{ k > l}p_{kl}  - \mathop{\sum\sum}_{ k < l}p_{kl}.
\end{equation*}


Some background:

This is an **interesting and challenging** question, in fact, an **active research** problem I am currently pursuing. I can't prove that it indeed has a closed form solution, but I tend to believe so. I have tried very hard and therefore want to solicit any hints or point of directions. On a related note,  I have obtained closed form solutions of the sharp bounds of the following very similar objective functions, namely
\begin{equation*}
\tau = \mathop{\sum\sum}_{ k \ge l}p_{kl},
\quad
\eta = \mathop{\sum\sum}_{ k > l}p_{kl},
\quad
\xi = \mathop{\sum\sum}_{ k = l}p_{kl},
\end{equation*}
which another reason why I believe the solution exists for $\Delta$ as well. For more details see my Ph.D. dissertation at:

dash.harvard.edu/handle/1/23845443





(Update March 31) Let me provide a bit more context. Because of the symmetrical structure of $\Delta,$ we only need to figure out the upper bound. When $J=2$, we have
\begin{equation*}
\Delta = p_{+0} - p_{0+} = p_{1+} - p_{+1} = \min \left( p_{+0} - p_{0+}, p_{1+} - p_{+1}\right),
\end{equation*}
therefore we can identify $\Delta$ from the marginals. When $J=3$, simulations suggest that the sharp upper bound of $\Delta$ is:
\begin{equation*}
\Delta_U = \min \left\{ p_{+0} - p_{0+} + \min\left( p_{2+}, p_{+1}\right),
p_{2+} - p_{+2} + \min\left( p_{1+}, p_{+0}\right) \right\}.
\end{equation*}
However, unfortunately, when $J>3,$ I am no longer able to "guess" the closed-form solutions and therefore I need your help. :)