Latin Rectangles as Representative Systems

From a Latin Rectangle to a Selection Problem

A Latin rectangle records a set of rows in which each row uses every symbol once and no column repeats a symbol. To add another row, each column must receive a symbol that is not already in that column. At the same time, a new row must use each symbol exactly once. These two requirements make the task a representative-selection problem: each column has a set of available symbols, and we must choose one representative from each set without choosing any symbol twice.

Throughout, let \(n\ge 1\), let the symbols be \(1,\dots,n\), and let \(0\le r\le n\). A row is an ordered list of \(n\) symbols, one in each column.

Definition: An \(r\times n\) Latin rectangle on the symbol set \(S=\{1,\dots,n\}\) is an array with \(r\) rows and \(n\) columns such that every row contains each symbol of \(S\) exactly once, and no column contains a symbol more than once. A symbol is missing from column \(j\) if it does not occur in that column. A proposed added row is valid if, after it is appended, the resulting array is an \((r+1)\times n\) Latin rectangle.

When \(r<n\), every column has at least one missing symbol, so there are choices to represent by sets. We make these choices into a bipartite graph. Its left side consists of symbol vertices, its right side consists of column vertices, and an edge records that the symbol may be placed in that column. The graph is simple: there is at most one edge between any symbol and any column, and no loops.

Definition: Given an \(r\times n\) Latin rectangle \(R\), its missing-symbol graph \(B_R\) is the bipartite graph with vertex parts \(S\) and \(C=\{c_1,\dots,c_n\}\), where \(s\in S\) is joined to \(c_j\) exactly when \(s\) is missing from column \(j\). For \(J\subseteq C\), the neighborhood \(N(J)\) is the set of symbols joined to at least one column in \(J\).

Thus \(N(J)\) is the collection of symbols that could serve as a representative for at least one column in \(J\). The graph does not say that every symbol in \(N(J)\) can be assigned to every column in \(J\); an edge specifies each permitted pair.

Rows and Matchings

Proposition: If \(r<n\), a valid added row for \(R\) exists exactly when \(B_R\) has a matching covering all \(n\) column vertices. Such a matching also covers all \(n\) symbol vertices.

Proof. Assume first that a valid row has been added. For each column \(j\), let \(s_j\) be the symbol placed in it. Since the new entry does not repeat a symbol already in column \(j\), \(s_j\) is missing from that column. Therefore \(s_jc_j\) is an edge of \(B_R\). The new row uses every symbol exactly once, so the \(n\) chosen symbol vertices are distinct. The edges \(s_jc_j\), one for each column, consequently share no endpoints and form a matching covering all columns.

Conversely, suppose \(B_R\) has a matching covering every column. Each of the \(n\) columns is matched to a symbol adjacent to it, so that symbol is missing from the column and can be placed there. The matched symbols are distinct because the edges form a matching. There are \(n\) symbols in total and \(n\) distinct matched symbols, so every symbol is used exactly once. The resulting row repeats no symbol in a column and contains every symbol once; appending it gives a valid Latin rectangle. \(\square\)

A matching is a set of edges no two of which share an endpoint. It is perfect when it covers every vertex on both sides. Here the two sides both have \(n\) vertices, so a matching covering all columns uses \(n\) distinct symbols and is perfect.

Hall's theorem, established in the earlier material on representative systems, gives a condition that can be checked using neighborhoods: a bipartite graph with column part \(C\) has a matching covering \(C\) if and only if \(|N(J)|\ge |J|\) for every subset \(J\subseteq C\). For a missing-symbol graph, this says that every collection of columns must collectively have at least as many available symbols as columns. This is a condition on all subsets, not merely a check that each individual column has a missing symbol.

How Many Choices Does Each Vertex Have?

Proposition: In the missing-symbol graph of an \(r\times n\) Latin rectangle, every symbol vertex and every column vertex has degree \(n-r\).

Proof. Fix a column. Its \(r\) entries are distinct, by the definition of a Latin rectangle, so exactly \(r\) of the \(n\) symbols occur there. Thus \(n-r\) symbols are missing, and the column vertex has degree \(n-r\). Now fix a symbol. Each of the \(r\) rows contains that symbol exactly once, giving \(r\) occurrences. These occurrences lie in distinct columns: if two were in the same column, that column would repeat the symbol. Hence the symbol is present in \(r\) different columns and missing from the other \(n-r\). Its degree is also \(n-r\). This includes \(r=n\), when every degree is \(0\), and \(r=0\), when every degree is \(n\). \(\square\)

This degree count describes the shape of the choice graph. It does not itself specify which symbol should be assigned to which column: a valid assignment still needs distinct symbols across all columns. When \(r=n\), every column is already full, the missing-symbol graph has no edges, and no further row can be added using this symbol set.

Worked Example: A Two-Row Rectangle on Four Symbols

Consider the rectangle with symbol set \(S=\{1,2,3,4\}\) and rows \((1,2,3,4)\) and \((2,3,4,1)\). The columns contain, respectively, \(\{1,2\}\), \(\{2,3\}\), \(\{3,4\}\), and \(\{4,1\}\). The missing sets are therefore \(M_1=\{3,4\}\), \(M_2=\{1,4\}\), \(M_3=\{1,2\}\), and \(M_4=\{2,3\}\).

Write the symbol vertices as \(s_1,s_2,s_3,s_4\), and the column vertices as \(c_1,c_2,c_3,c_4\). The missing-symbol graph is \(B_R=(V,E)\), where \(V=\{s_1,s_2,s_3,s_4,c_1,c_2,c_3,c_4\}\) and \(E=\{s_3c_1,s_4c_1,s_1c_2,s_4c_2,s_1c_3,s_2c_3,s_2c_4,s_3c_4\}\). For instance, \(s_3c_1\) is present because symbol \(3\) is missing from column \(1\); \(s_1c_1\) is absent because column \(1\) already contains \(1\).

Choose the edges \(s_3c_1,s_4c_2,s_1c_3,s_2c_4\). No two share an endpoint, so they form a matching covering all four columns and all four symbols. Reading the matched symbols in column order gives the row \((3,4,1,2)\).

Check: The proposed row contains \(3,4,1,2\), each once. Its entries are missing from their respective columns: \(3\notin\{1,2\}\), \(4\notin\{2,3\}\), \(1\notin\{3,4\}\), and \(2\notin\{4,1\}\). Also, \(n-r=4-2=2\), and each listed vertex has degree \(2\), as the degree proposition predicts.

Neighborhoods Express Hall's Condition

To use the representative-system viewpoint, take a set \(J\) of columns and gather the symbols adjacent to at least one of them. Hall's condition compares the number of these available symbols with the number of columns in \(J\). A tight set has exactly enough symbols for its columns; a set with fewer available symbols than columns cannot be fully represented by distinct choices.

Worked Example: Neighborhoods in a Three-Column Rectangle

Let \(S=\{1,2,3\}\), and take the one-row rectangle \((1,2,3)\). Its columns contain \(1\), \(2\), and \(3\), respectively, so the missing sets are \(M_1=\{2,3\}\), \(M_2=\{1,3\}\), and \(M_3=\{1,2\}\). The graph is \(B_R=(V,E)\), with \(V=\{s_1,s_2,s_3,c_1,c_2,c_3\}\) and \(E=\{s_2c_1,s_3c_1,s_1c_2,s_3c_2,s_1c_3,s_2c_3\}\).

For \(J=\{c_1,c_2\}\), the neighbors of \(c_1\) are \(s_2,s_3\), and the neighbors of \(c_2\) are \(s_1,s_3\). Their union is \(N(J)=\{s_1,s_2,s_3\}\), so \(|N(J)|=3\ge2=|J|\). For \(J=\{c_1,c_2,c_3\}\), all three symbols occur as neighbors, so \(|N(J)|=3=|J|\). These computations illustrate the subset comparison in Hall's condition; checking only the three individual columns would not make the comparison for larger sets.

For an actual assignment, choose \(s_2c_1,s_3c_2,s_1c_3\). The edges share no endpoints, and the row they specify is \((2,3,1)\). Its entries are missing from the corresponding columns, and it contains each of \(1,2,3\) once.

Check: The missing-symbol graph has degree \(3-1=2\) at each vertex: for example, \(s_1\) is adjacent to \(c_2,c_3\), and \(c_1\) is adjacent to \(s_2,s_3\). The selected three edges form a matching because their column endpoints are all different and their symbol endpoints are all different.

Why the Matching Requirement Matters

It is not enough to select a missing symbol separately for every column. The selections must be compatible: the same symbol cannot be used in two columns of the new row. In graph language, selecting an allowed edge at every column gives a matching only if no symbol endpoint is used more than once. This distinction separates independent per-column choices from a representative system.

Worked Example: Correcting Repeated Choices

Use again the one-row rectangle \((1,2,3)\) on \(S=\{1,2,3\}\). Its missing-symbol graph has \(V=\{s_1,s_2,s_3,c_1,c_2,c_3\}\) and \(E=\{s_2c_1,s_3c_1,s_1c_2,s_3c_2,s_1c_3,s_2c_3\}\). A tempting choice is to put symbol \(2\) in both columns \(1\) and \(3\), since \(s_2c_1\) and \(s_2c_3\) are both edges. This would leave the third column needing a choice, but symbol \(2\) cannot be used there a second time: the two chosen edges already share endpoint \(s_2\). The partial choice is not a matching and cannot define a Latin row.

Instead choose \(s_2c_1,s_3c_2,s_1c_3\). The row is \((2,3,1)\). The first entry is missing from column \(1\), since that column contains \(1\); the second is missing from column \(2\), since that column contains \(2\); and the third is missing from column \(3\), since that column contains \(3\). The three entries are distinct and exhaust the symbol set.

Check: The corrected edges have column endpoints \(c_1,c_2,c_3\), each once, and symbol endpoints \(s_2,s_3,s_1\), each once. Thus they are a matching covering both parts, whereas the repeated choice shared endpoint \(s_2\).

Reading the Model Carefully

The missing-symbol graph is a translation device: it turns the Latin-rectangle rules into a standard bipartite selection problem. Each edge represents a locally legal placement, while a matching enforces global distinctness of the symbols. Hall's condition then asks whether every group of columns collectively has enough neighboring symbols to represent them.

Keep the two sides of the graph distinct even when their labels use the same symbols. The vertex \(s_2\) is a symbol; \(c_2\) is a column. An edge \(s_2c_2\) means symbol \(2\) is missing from column \(2\), not that the two vertices are the same object.

There are also two different checks to make in any proposed row. First, each selected symbol must be missing from the column where it is placed; this checks that each selected edge exists. Second, all selected symbols must be distinct; this checks that the edges form a matching. Together, these conditions give exactly the Latin-rectangle requirements for the added row.

Check Your Understanding

Use the definitions and matching interpretation to answer the following.

For a two-row rectangle on five symbols, what is the degree of every vertex in its missing-symbol graph? Explain from the column and symbol counts.
In a missing-symbol graph, what does a symbol vertex in \(N(J)\) mean when \(J\) is a set of columns?
Explain why choosing an edge incident to every column is not enough unless the chosen edges form a matching.
State Hall's condition using a set of columns \(J\) and the neighborhood \(N(J)\).
Prove directly that a matching covering all columns in the missing-symbol graph gives a row containing every symbol exactly once.