TAOCP 7.2.2.1 Exercise 48
Let the data of chart (33) be a function $f$ assigning to each ordered pair $(r,c)$ a unique value $v$ from a finite set $V$, so that each position $(r,c)$ carries exactly one value.
Section 7.2.2.1: Dancing Links
Exercise 48. ▶ [24] [24] Chart (33) essentially plots rows versus columns. Show that the same data could be plotted as either (a) rows versus values, or (b) values versus columns.
Verified: no
Solve time: 54s
Solution
Let the data of chart (33) be a function $f$ assigning to each ordered pair $(r,c)$ a unique value $v$ from a finite set $V$, so that each position $(r,c)$ carries exactly one value. Equivalently, the data is the set
$$ D={(r,c,v)\mid f(r,c)=v}. $$
Assume also the usual Latin-square consistency that each value appears exactly once in each row and once in each column; that is, for each fixed $r$ and $v$ there is exactly one $c$ with $(r,c,v)\in D$, and for each fixed $c$ and $v$ there is exactly one $r$ with $(r,c,v)\in D$. These conditions make the three coordinate projections of $D$ mutually bijective in the appropriate sense.
(a) Rows versus values
Define a new representation by projecting $D$ onto the first and third coordinates:
$$ D_{RV}={(r,v)\mid \exists c; (r,c,v)\in D}. $$
For each pair $(r,v)$, the Latin-square condition guarantees a unique column $c$ such that $(r,c,v)\in D$, so the correspondence
$$ (r,c,v)\longmapsto (r,v) $$
is injective on $D$, and every admissible $(r,v)$ arises from exactly one triple in $D$. The original column $c$ is recoverable as the unique element satisfying $(r,c,v)\in D$, so no information is lost.
Thus the same dataset can be plotted with rows indexed against values, where each point $(r,v)$ records the unique column position at which value $v$ occurs in row $r$.
(b) Values versus columns
Define instead the projection onto the third and second coordinates:
$$ D_{VC}={(v,c)\mid \exists r; (r,c,v)\in D}. $$
For each pair $(v,c)$, the Latin-square condition ensures a unique row $r$ such that $(r,c,v)\in D$, so the mapping
$$ (r,c,v)\longmapsto (v,c) $$
is again injective on $D$, and every admissible $(v,c)$ corresponds to exactly one triple. The original row $r$ is uniquely determined as the element satisfying $(r,c,v)\in D$.
Hence the same dataset can be plotted with values indexed against columns, where each point $(v,c)$ records the unique row position at which value $v$ appears in column $c$.
Equivalence of the representations
Both constructions arise from the same underlying set $D$ by permuting coordinates of the triples in $D\subseteq R\times C\times V$. Each permutation yields a bijection on $D$, and each resulting projection determines the remaining coordinate uniquely by the defining property of $D$. Therefore the representations
$$ (R,C)\to V,\qquad (R,V)\to C,\qquad (V,C)\to R $$
are mutually equivalent encodings of the same information, obtained by reindexing the same set of triples.
This completes the proof. ∎