## § 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.