From Missing Entries to a Matching
A Latin rectangle has rows with no repeated symbols and columns with no repeated symbols. If it has fewer rows than symbols, each column still has vacant positions. To add a row, we must place every symbol once and avoid repeating any symbol in its column. This is a selection problem: match each symbol to a column in which it is absent. Hall’s theorem provides the guarantee that these choices can be made all at once.
We consider \(n\ge 1\) and \(0\le r<n\). Label the columns \(1,\ldots,n\), and use a separate copy of these labels for the symbols, so the two sides of the graph below are distinct even if they use the same numbers.
A matching in this graph assigns different columns to different symbols, using only available symbol–column pairs. A perfect matching assigns every symbol to a column and every column to a symbol. Thus a perfect matching gives exactly the choices needed for a new row. The main question is why such a matching must exist.
Why the Availability Graph Is Regular
Put \(d=n-r\), which is positive because \(r<n\). Every symbol appears once in each of the \(r\) existing rows. Its \(r\) occurrences lie in distinct columns: if two were in the same column, that column would repeat the symbol. So the symbol is present in exactly \(r\) columns and absent from the other \(n-r=d\) columns.
Each column contains one entry from each existing row, and those entries are distinct. It therefore contains \(r\) symbols and is missing \(n-r=d\) symbols. These two counts give the degrees on the two sides of the availability graph.
Proof. A symbol appears exactly once in each of the \(r\) rows. Its appearances are in distinct columns, so exactly \(r\) columns contain it. Since there are \(n\) columns, exactly \(n-r\) do not contain it, giving its degree in the availability graph. Each column contains \(r\) distinct symbols, one from each row, so it is missing exactly \(n-r\) of the \(n\) symbols. Its degree is also \(n-r\). These arguments include \(r=0\): every symbol is absent from all \(n\) columns, and every column is missing all \(n\) symbols. \(\square\)
We now use Hall’s theorem in its standard form, established in the earlier material on Hall’s theorem: a bipartite graph with sides \(X,Y\) has a matching saturating \(X\) if and only if every subset \(S\subseteq X\) satisfies \(|N(S)|\ge |S|\), where \(N(S)\) is the set of vertices adjacent to at least one vertex of \(S\). In our graph, both sides have size \(n\), so a matching saturating the symbol side is perfect.
Hall’s Condition from Regularity
Let \(S\) be any subset of the symbol side, and let \(N(S)\) be the columns available to at least one symbol of \(S\). If \(S\) is empty, then \(|N(S)|=0=|S|\), so Hall’s condition holds. Suppose \(S\) is nonempty. Each symbol in \(S\) has degree \(d=n-r\), so there are exactly \(d|S|\) edges from \(S\) to columns in \(N(S)\). Each column in \(N(S)\) has total degree \(d\), so at most \(d\) of those edges can meet that column. Consequently, there are at most \(d|N(S)|\) edges from \(S\) to \(N(S)\). Comparing the counts gives \(d|S|\le d|N(S)|\). Since \(d>0\), division by \(d\) gives \(|S|\le |N(S)|\), as required.
Proof. Form the symbol–column availability graph. By the Lemma, it is regular of degree \(d=n-r>0\). For every subset \(S\) of its symbol side, the edge count above gives \(|N(S)|\ge |S|\); this includes the empty subset. Hall’s theorem therefore gives a matching saturating all \(n\) symbols. Because the column side also has \(n\) vertices, this matching uses every column and is perfect. In each column, place the symbol matched to that column. Every placed symbol was absent from its column, so the new row creates no repetition within any column. The matching uses each symbol once, so the new row contains every symbol exactly once. The old rows and their entries have not changed; therefore the enlarged array is a Latin rectangle. \(\square\)
Proof. Given a perfect matching, place in each column the symbol matched to it. Every matched pair is an edge of the availability graph, so the symbol is absent from that column; and because the matching is perfect, each symbol is placed once. This produces an extension. Conversely, in any extension, each column’s new entry is absent from that column in the original rectangle, so it defines an edge of the availability graph. The new row uses each symbol exactly once, and fills each column exactly once, so these edges form a perfect matching. The two constructions undo one another: the edge for a symbol records precisely the column in which that symbol was placed. \(\square\)
Worked Extensions
Worked Example: Adding a Row to a One-Row Rectangle
Take the Latin rectangle on \(\Sigma=\{1,2,3,4\}\) with one row \((1,2,3,4)\). The symbol–column availability graph is defined by the following adjacency table; a symbol is adjacent to each column where it is absent.
| Symbol | Available columns |
|---|---|
| 1 | 2, 3, 4 |
| 2 | 1, 3, 4 |
| 3 | 1, 2, 4 |
| 4 | 1, 2, 3 |
Each symbol has degree \(3=4-1\), and each column is missing three symbols. Choose the matching \(\{(1,2),(2,3),(3,4),(4,1)\}\). Every pair is available: symbol 1 is absent from column 2, symbol 2 from column 3, symbol 3 from column 4, and symbol 4 from column 1. The resulting new row, read in column order, is \((4,1,2,3)\).
Check: The matching uses the four symbols and the four columns exactly once. In columns 1 through 4, respectively, the old and new entries are \((1,4),(2,1),(3,2),(4,3)\); each pair has distinct entries. The new row contains \(4,1,2,3\), so it contains each symbol once.
Worked Example: A Rectangle with Two Existing Rows
Let \(\Sigma=\{1,2,3,4,5\}\), and take the two rows \((1,2,3,4,5)\) and \((2,3,4,5,1)\). Each row contains all five symbols, and in each column the two entries differ. The availability graph has the following adjacency table.
| Symbol | Available columns |
|---|---|
| 1 | 2, 3, 4 |
| 2 | 3, 4, 5 |
| 3 | 1, 4, 5 |
| 4 | 1, 2, 5 |
| 5 | 1, 2, 3 |
For example, symbol 1 appears in columns 1 and 5, so it is available in columns 2, 3, and 4. Every symbol and every column has degree \(3=5-2\). Choose the matching \(\{(1,2),(2,3),(3,4),(4,5),(5,1)\}\). The table confirms that all five pairs are edges. It places the symbols in column order as the new row \((5,1,2,3,4)\).
Check: The new row uses all five symbols once. The columns’ old entries are \((1,2),(2,3),(3,4),(4,5),(5,1)\); the new entries \(5,1,2,3,4\) differ, respectively, from the second entries \(2,3,4,5,1\) in those columns. Thus no column repeats a symbol.
Worked Example: The Last Row Is Forced
Consider the rectangle on \(\Sigma=\{1,2,3,4\}\) with rows \((1,2,3,4)\), \((2,3,4,1)\), and \((3,4,1,2)\). The entries in each column are distinct. Here \(r=3\) and \(n=4\), so the availability degree is \(n-r=1\). Directly checking the missing symbol in each column gives the availability graph.
| Symbol | Available columns |
|---|---|
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
| 4 | 1 |
Each symbol has exactly one available column, so the only possible matching is \(\{(1,2),(2,3),(3,4),(4,1)\}\). It is perfect because it uses each column once. The new row is \((4,1,2,3)\).
Check: The column entries after adding the row are \((1,2,3,4)\), \((2,3,4,1)\), \((3,4,1,2)\), and \((4,1,2,3)\), each with four distinct symbols. The new row also contains each symbol once. Since each column had exactly one missing symbol, any extension must use these same entries.
Why the Counting Argument Matters
The proof does more than certify one example. It explains why every rectangle with fewer than \(n\) rows works, regardless of the pattern of its entries. The available pairs need not be arranged in any special cyclic order. Regularity alone provides enough edges: a set of \(k\) symbols has \(dk\) available pairs, while its neighboring columns can receive at most \(d\) of those pairs each. Thus those symbols must collectively have at least \(k\) neighboring columns. Hall’s theorem turns that count into a simultaneous assignment.
Common mistake: counting appearances as availability. In the two-row, five-symbol example, symbol 1 appears twice, so it has three available columns, not two. Its appearances are in columns 1 and 5; it is absent from columns 2, 3, and 4. In general, each symbol appears in \(r\) distinct columns, leaving \(n-r\) available columns. The same distinction applies to a column: it contains \(r\) distinct symbols and is missing \(n-r\), not \(r\). Confusing these counts can lead to a false degree calculation and an invalid Hall argument.
Another important condition is \(r<n\). It ensures \(d=n-r>0\), which is needed when the edge-count inequality \(d|S|\le d|N(S)|\) is divided by \(d\). When \(r=n\), there are no vacant cells, and an additional row is not part of an \(n\)-column Latin rectangle on the same \(n\) symbols. At the opposite endpoint \(r=0\), the graph has degree \(n\), and any permutation of the symbols supplies the first row.
Check Your Understanding
Use the availability graph and its degrees to justify each answer.
- A Latin rectangle has \(n=7\) symbols and \(r=4\) rows. What is the degree of every vertex in its availability graph, and why?
- For a set \(S\) of symbols in the availability graph, explain why the number of edges from \(S\) to \(N(S)\) is both \(d|S|\) and at most \(d|N(S)|\).
- Why does a matching saturating the symbol side also saturate the column side in this setting?
- In a rectangle with \(n=5\) and \(r=4\), what does degree one in the availability graph imply about the possible new row?
- Explain why \(r<n\) is needed in the edge-count proof of Hall’s condition.