Maximum value of Chi squared while keeping marginal frequencies

Let's say we have a RxC contingency table, with R=C. How could one best repopulate the table such that:

1. all counts reside in the off-diagonal cells (zero's on the diagonal);
2. marginal frequencies remain the same;
3. the value of Chi square is maximal.

I can imagine a very 'exhaustive' approach by calculating the Chi square for each possible repopulation and taking the table that produces the highest Chi square value, but there has to be an elegant much better way to solve this! A formal proof may be difficult, but a smart algorithm should exist.

• Out of curiosity, what is the statistical application? After all, the maximal chi-square value is going to be huge; it doesn't seem to correspond to anything statistically meaningful. BTW, what exactly does "repopulate" mean? Is it supposed to involve a permutation of the existing cell counts or could it be any choice of (integral) counts meeting the constraints? – whuber Mar 15 '12 at 18:29
• I am trying to determine the maximum possible systematic disagreement two raters/annotators could possible have achieved. In a contingency matrix, disagreement is represented by the off-diagonal cells. With 'repopulate' I mean the permutation of the existing cell counts such that those three conditions are met. I can then relate the Chi square of the contingency table with observed counts to the maximal Chi square, and get an idea of how much of the disagreement isn't random disagreement. – Jero Gee Mar 16 '12 at 12:29
• I'm struggling to understand the underlying rating model. For instance, why not allow permutations within the full contingency table, rather than fixing the diagonal elements? It's difficult to see how permuting only the off-diagonal entries constitutes a valid model of "random disagreement." – whuber Mar 16 '12 at 13:51

This is a quadratic programming problem. To see this, first rearrange the $R \times C$ matrix of expected values $E_{ij}$ and counts $X_{ij}$ into vectors, which we will label $\bf{E}$ and $\bf{X}$, and which have length $N = R \times C$ (although you could just remove the diagonal elements from both vectors before continuing, since they are constrained to equal zero.) Then maximizing the $\chi^2$ statistic is the same as:
$\max_{\bf{X}} \sum_{i=1}^N \frac{(X_i-E_i)^2}{E_i} = \sum_{i=1}^NX_i^2/E_i -2 \sum_{i=1}^NX_i$
which pretty obviously can be rewritten in the canonical quadratic programming objective function form $\frac{1}{2}x^TQx +c^Tx$, $Q$ a diagonal matrix with $Q_{ii} = 2/E_i$ and $c_i = -2, i=1, \dots, N$.
The constraints on the marginal totals are just equality constraints on the sums of various of the elements of $\bf{X}$, with of course equality constraints for the constrained-to-equal-zero elements of $\bf{X}$, and fit into the standard QP formulation $Dx = d$ in the obvious manner.