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. :)