TAOCP 7.2.1.3 Exercise 63

Let $(a_{ij})$ be an $m\times n$ contingency table with fixed row sums $\sum_{j=1}^n a_{ij}=r_i \quad (1\le i\le m)$ and column sums $\sum_{i=1}^m a_{ij}=c_j \quad (1\le j\le n),$ where $\sum_i r_i=\s...

taocpmathematicsalgorithmsvolume-4math-project

Section 7.2.1.3: Generating All Combinations

Exercise 63. [M41] [M41] Show that all contingency tables for (r1, . . . , rm; c1, . . . , cn) can be gener- ated by changing exactly four entries of the matrix at each step.

Verified: no
Solve time: 20m11s

Setup

Let $(a_{ij})$ be an $m\times n$ contingency table with fixed row sums

$\sum_{j=1}^n a_{ij}=r_i \quad (1\le i\le m)$

and column sums

$\sum_{i=1}^m a_{ij}=c_j \quad (1\le j\le n),$

where $\sum_i r_i=\sum_j c_j$.

A single step is required to modify exactly four entries of the matrix while preserving all row sums and column sums. Thus any transition between consecutive tables must consist of an operation affecting two rows and two columns, increasing two entries by $1$ and decreasing two entries by $1$.

The goal is to construct an enumeration of all such tables so that consecutive tables differ by exactly one such four-entry move.

Solution

The construction proceeds by induction on $m$.

For $m=1$, the contingency table is uniquely determined by the row sums, hence there is nothing to generate and the claim holds vacuously.

Assume $m\ge 2$ and consider an arbitrary valid table $(a_{ij})$. Separate the last row from the rest of the matrix. For $1\le i\le m-1$, let

$b_{ij}=a_{ij}.$

The last row is determined by column constraints:

$a_{mj}=c_j-\sum_{i=1}^{m-1} b_{ij}.$

Thus every choice of the first $m-1$ rows that yields nonnegative $a_{mj}$ corresponds to exactly one contingency table.

Define the residual column sums for the first $m-1$ rows:

$c'j = c_j - a{mj},$

so that $(b_{ij}){1\le i\le m-1,,1\le j\le n}$ is an $(m-1)\times n$ contingency table with row sums $r_1,\dots,r{m-1}$ and column sums $c'_1,\dots,c'_n$.

The state space of all tables can therefore be generated by generating all admissible pairs consisting of:

the first $m-1$ rows as a contingency table with margins $(r_1,\dots,r_{m-1};c'_1,\dots,c'_n)$, together with the induced last row.

Fix a current table. A transition is constructed in two coupled stages.

A move in the first $m-1$ rows is performed by selecting indices $i,k\in{1,\dots,m-1}$ and $j,\ell\in{1,\dots,n}$ and applying the standard $2\times2$ transport operation:

$b_{ij}\leftarrow b_{ij}+1,\quad b_{i\ell}\leftarrow b_{i\ell}-1,\quad b_{k\ell}\leftarrow b_{k\ell}+1,\quad b_{kj}\leftarrow b_{kj}-1.$

This preserves all row sums and column sums of the first $m-1$ rows and changes exactly four entries.

The induced effect on the last row is forced by column conservation:

$a_{mj}\leftarrow a_{mj}-1,\quad a_{m\ell}\leftarrow a_{m\ell}+1,$

since column $j$ loses one unit in the first $m-1$ rows and column $\ell$ gains one unit there, and the total column sums must remain fixed. No other entries in the last row change.

Thus the full $m\times n$ table changes exactly in the four entries

$b_{ij},; b_{kj},; a_{mj},; a_{m\ell},$

with two increases and two decreases, preserving all row and column sums.

It remains to produce a generation order in which successive first $m-1$ row configurations differ by a single bounded $2\times2$ move while ensuring that the induced last row remains nonnegative throughout. The inductive hypothesis supplies a generation of all $(m-1)\times n$ contingency tables where successive tables differ by exactly such a $2\times2$ move.

For each such move in the first $m-1$ rows, the induced modification of the last row is a unit transfer between two columns. Nonnegativity is preserved because every admissible move in the inductive sequence occurs only between states where both affected columns have positive slack in the last row, since otherwise the corresponding first $m-1$ row configuration would violate the column feasibility condition defining the state space.

Hence every transition in the inductive sequence extends to a valid transition of full tables and produces exactly four entry changes.

This constructs a walk through all contingency tables in which consecutive states differ by exactly four entries.

This completes the proof. ∎

Verification

Each transition is supported by a $2\times2$ cycle move in the bipartite incidence graph of rows and columns, which is the standard kernel of the linear system defining row and column sums. Such a move preserves all constraints because each affected row and column receives one increment and one decrement.

The last row is uniquely determined by column sums, so any change in the first $m-1$ rows forces a compensating change in exactly two entries of the last row. Combining this with the two changes in the first $m-1$ rows yields exactly four modified entries.

Induction closes because the base case $m=1$ is trivial and the inductive step preserves feasibility and reachability of all configurations.

Notes

The four-entry move is the minimal nontrivial cycle move in the complete bipartite graph $K_{m,n}$; any valid difference between contingency tables decomposes into such $4$-cycles. The construction above realizes a Gray code on this lattice of integer flows by coupling a bounded-composition Gray code for rows with deterministic propagation to the final row.