§ Latin Square

• A latin square of order $N$ is an $N \times N$ array in which each row and column is a permutation of $\{ a_1, a_2, \dots, a_n \}$.
• Example latin square (to show that these exist):

[1 2 3 4]
[2 3 4 1]
[3 4 1 2]
[4 1 2 3]

• A $k \times n$ ( $k < n$) latin rectangle is a $k \times n$ matrix with elements $\{ a_1, a_2, \dots, a_n \}$ such that in each row and column, no element is repeated.
• Can we always complete a Latin rectangle into a Latin square? (YES!)

§ Lemma

• Let $A$ be a $k \times n$ latin rectangle with $k \leq n - 1$.
• We can always augment $A$ into a $(k + 1) \times n$ latin rectangle.
• If we thnk of it as a set system, then we can think of each column as telling us the missing sets. Example:

[1   2   3   4]
[4   1   2   3]
{2} {3} {1} {1}
{3} {4} {4} {2}

• Let's think of the subsets as a 0/1 matrix, encoded as:

[0 1 1 0] {2, 3}
[0 0 1 1] {3, 4}
[1 0 0 1] {1, 4}
[1 1 0 0] {1, 2}

• It's clear that each row will have sum $2$, since each set has 2 elements.
• We claim that each column also has sum $2$.
• For example, the first column has column sum $2$. This is because in the original matrix, $1$ is missing in two columns.
• We can computea perfect matching on the permutation matrix, that tells us how to extend the latin square with no overlaps.