A Worked Latin Rectangle Completion

Completing a Latin Rectangle by Matchings

A Latin rectangle is an array in which each row uses every symbol exactly once and no column repeats a symbol. To add a row, each column must receive a symbol not already above it, and the new row must use each symbol exactly once. These requirements are coupled: choosing an available symbol for one column may prevent its use in another. A bipartite matching records a set of choices that satisfy both requirements at once.

For each step, make one vertex for each column and one for each symbol. Join column \(c\) to symbol \(s\) exactly when \(s\) does not yet appear in column \(c\). A matching is a set of edges no two of which share a vertex. Thus, if a matching uses every column, its edges specify a choice for every column with no symbol chosen twice.

In a graph with \(n\) column vertices and \(n\) symbol vertices, a matching covering all columns also covers all symbols: it has \(n\) edges, and those edges have distinct symbol endpoints among \(n\) symbols. It therefore assigns one available, distinct symbol to each column, exactly what a new row requires.

Why a Matching Can Always Be Found

We use Hall’s theorem, established in the earlier material on Hall’s Marriage Theorem. In the form needed here, it says that a finite bipartite graph with left vertex set \(C\) has a matching covering \(C\) if and only if every subset \(X\subseteq C\) satisfies \(|N(X)|\ge |X|\), where \(N(X)\) is the set of vertices adjacent to at least one vertex of \(X\).

Proof. Let \(C\) be the set of \(n\) columns and \(S\) the set of \(n\) symbols, and form the available-pair graph. Fix a column. Its \(k\) entries are distinct, so exactly \(n-k\) symbols are absent from it; the column vertex therefore has degree \(n-k\). Fix a symbol \(s\). Since each of the \(k\) existing rows uses \(s\) exactly once, \(s\) appears in exactly \(k\) columns and is absent from exactly \(n-k\) columns. Thus every symbol vertex also has degree \(n-k\).

Take any subset \(X\subseteq C\). The number of edges from \(X\) is \((n-k)|X|\), since each column in \(X\) has degree \(n-k\). All these edges end in \(N(X)\), and each vertex in \(N(X)\) has total degree \(n-k\), so there are at most \((n-k)|N(X)|\) such edges. Consequently, \((n-k)|X|\le (n-k)|N(X)|\). Since \(k<n\), \(n-k>0\), and division gives \(|X|\le |N(X)|\). This holds for every \(X\subseteq C\), including \(X=\varnothing\), for which both sides are zero. Hall’s theorem gives a matching covering all columns. Use its symbol endpoints as the new row. Every entry is absent from its column, so no column repetition is introduced; and the matching uses each symbol at most once, so the new row has distinct entries. It has \(n\) entries chosen from \(n\) symbols, hence uses every symbol exactly once. The enlarged array is a Latin rectangle. \(\square\)

Proof. At any stage with \(k<n\) rows, the theorem applies to the current Latin rectangle and supplies a valid next row. Inductively, after \(j\) additions, for \(0\le j\le n-r\), the array has \(r+j\) rows and is a Latin rectangle: the case \(j=0\) is the assumed starting array, and each subsequent step preserves the defining properties by the theorem. At \(j=n-r\), it has \(n\) rows and \(n\) columns, so it is a Latin square. If \(r=n\), no additions are needed and the starting Latin rectangle is already a Latin square. \(\square\)

Worked Completions

Reading and Checking the Choices

The available-pair graph should be recomputed from the current array at every stage. Once a row has been added, some edges disappear: a symbol selected for one column is no longer available there, and each column’s list must be updated using all entries above it. A matching for an earlier stage is not automatically a matching for a later one; it is a new assignment problem.

The proof of the extension theorem gives a useful existence check. With \(k\) rows, every column and every symbol has exactly \(n-k\) available partners. For a nonempty subset \(X\) of columns, counting edges leaving \(X\) gives \((n-k)|X|\); since each neighboring symbol has at most \(n-k\) incident edges in total, this forces \(|N(X)|\ge |X|\). Hall’s theorem then guarantees a full matching. This argument proves that completion is possible, but an actual completion still requires displaying a particular matching, as in the examples.

Common pitfall: choosing independently. In the first four-symbol example, both \(c_1\) and \(c_4\) can individually use symbol \(3\): \(c_1s_3\) and \(c_4s_3\) are edges. Choosing \(3\) for both columns is not a matching, because those two edges share the symbol vertex \(s_3\); it would repeat \(3\) in the new row. The correction is to choose distinct symbol endpoints, for example the matching \(c_1s_3,c_2s_4,c_3s_1,c_4s_2\), which yields \((3,4,1,2)\). Availability for each column separately is not enough; the choices must form one matching.