# Filling an NxN table with N numbers

I have been confronted with the following homework question:

Let $M$ be a table of size $N \times N$. A legal filling of $M$ with the numbers $\{1,\dots,N\}$ is one such that each cell of the table has exactly one number and each line and each row contains each number exactly once.

Prove that for any partial filling of $M$, of the first $0 < k < n$ rows, it is possible to completely fill $M$ in a legal way.

Hint: Use bipartite matching

• Are you allowed to assume Hall's condition for a perfect matching? – almagest Jun 11 '16 at 10:01
• @almagest I would suppose so because the hint given is to use bipartite matching. – Ashwin Ganesan Jun 11 '16 at 15:57
• @almagest yes, I am allowed to assume Hall's condition – Nivolas Jun 12 '16 at 14:06

Given a table of size $k \times N$, construct a bipartite graph whose left vertices $c_1,\ldots,c_N$ correspond to the $N$ columns of the table and whose right vertices are $1,\ldots,N$. For each $i$, join $c_i$ to $j$ whenever $j$ does not occur as an entry in column $i$. In other words, the neighbors of $c_i$ are the numbers which do not appear in column $i$ of the given table.
Since the given table contains $k$ entries in each column (and so has $N-k$ entries missing in each column), each left vertex $c_i$ has valency $N-k$. In the given table, each entry has appeared $k$ times and so is missing from exactly $N-k$ columns. Thus, each right vertex $j$ in the bipartite graph has valency $N-k$. Hence, the bipartite graph is regular of valency $N-k$.
The bipartite graph which we constructed satisfies Hall's condition: any subset $S$ in the left vertex set has at least $|S|$ neighbors in the right vertex set. This is because $S$ is incident to $(N-k)|S|$ edges, and each right vertex is incident to exactly $(N-k)$ edges, whence the number of right vertices needed to cover $(N-k)|S|$ edges is at least $|S|$.
By Hall's theorem, the bipartite graph has a perfect matching. A perfect matching is a set of $N$ edges which gives the entries for the next row of the table. This process can be repeated to complete the table. We have shown that any $k \times N$ Latin rectangle can be completed to a Latin square.
• yes. When the valency is $N-k$, there exists a perfect matching. Remove this perfect matching from the graph. The resulting graph is again regular, of valency $N-k-1$. So it too has a perfect matching. Repeat this process until we end up with a 1-regular graph, which is a perfect matching. – Ashwin Ganesan Jun 14 '16 at 1:33