chapter 5:latin squares Flashcards
DEF 1:
latin rectangle
Given nonempty finite sets P, Q and N, a Latin rectangle L is a system of elements Lij ∈ N
for i ∈ P and j ∈ Q such that
(a) For each i ∈ P, all the elements in the row L_i∗ are distinct. In more detail, if i ∈ P and j, j’ ∈ Q with j ≠ j’, then we must have L_ij ≠ L_{ij’} .
(b) For each j ∈ Q, all the elements in the column L_{∗j} are distinct. In more detail, if j ∈ Q and i, i’ ∈ P with i ≠ i’, then we must have Lij ≠ L_{i’j} .
In each row we have p entries from N which must all be different, and in each column we
have q entries from N which must all be different. This can only work if p, q ≤ n. Thus, if we fix N with
|N| = n, then the maximum possible size of a Latin rectangle is n × n.
p and q
We will usually write p = |P| and q = |Q| and n = |N|.
Often (but not always) we will have P = {1, . . . , p}
or P = {0, . . . , p − 1} and similarly for P and Q.
eg latin squares
[1 4 3 2] [2 3 4 1] [4 1 2 3] [3 2 1 4] is a 4 × 4 Latin square.
[1 4 3]
[5 2 1 ]
is a 2 × 3 Latin rectangle.
An n × n Latin square is an n × n matrix in which every one
of the numbers 1, 2, . . . , n appears in each row and each column.
A p × q Latin rectangle with entries in {1, 2, . . . , n} is a p × q matrix whose entries
are from {1, 2, . . . , n} with no repeat in any row or column.
Definition 3. A Latin square
A Latin square of size n is a Latin rectangle with |P| = |Q| = |N| = n.
Note that in a Latin square each row contains n different entries taken from N, but |N| = n, so each row must contain each element of N precisely once. Similarly, each column must contain each element of N precisely once.
example 4:
the matrix
[1 4 3]
[5 2 1]
gives a Latin rectangle with P = {1, 2} and Q = {1, 2, 3} and N = {1, 2, 3, 4, 5} so p = 2 and q = 3 and
n = 5.
Example 5. The matrix
[1 4 3 2]
[2 3 4 1]
[4 1 2 3]
[3 2 1 4]
gives a Latin square with P = Q = N = {1, 2, 3, 4} and p = q = n = 4.
Example 6:
Let G be any finite group, with |G| = n. Take P = Q = N = G and Lg,h = g ∗ h. I claim that
this is a Latin square.
Indeed, if L_{g,h} = L{g,h’} then g ∗ h = g ∗ h’ and we can multiply on the left by g^−1
to see that h = h’.
By the contrapositive, if h ≠ h’ then L_{g,h} ≠ L_{g,h’} . By a similar argument, if g ≠ g’
then
L_{g,h} ≠ L_{g’,h},
as required.
Example 7.
As a special case of the above, we can consider the group Z/n = {0, . . . , n − 1}, with addition
mod n as the group operation. This gives a Latin square with P = Q = N = {0, . . . , n − 1} and Lij = i + j
(mod n). For example, when n = 5 we get
[0 1 2 3 4] [1 2 3 4 0] [2 3 4 0 1] [3 4 0 1 2] [4 0 1 2 3] This example shows that for any n, there is at least one n × n Latin square.
THEOREM 8:
extending rectangle to latin square
Let L be a Latin rectangle with p < q = n (so L has the maximum possible width, but not the maximum possible height). Then L can be extended by adding extra rows to make an n × n Latin square
DEF 9:
multiplicity
excess
Let L be a Latin rectangle with parameters p, q, n. For k ∈ N we let L(k) denote the number
of occurrences of k in L, and we call this the multiplicity of k. We also put
E(k) = L(k) + n − p − q and call this the excess of k.
EXAMPLE 10: For L=
[1 4 3]
[5 3 1]
we have (p, q, n) = (2, 3, 5) so n − p − q = −1 and
L(1) = 2 L(2) = 0 L(3) = 2 L(4) = 1 L(5) = 1
E(1) = 1 E(2) = −1 E(3) = 1 E(4) = 0 E(5) = 0.
extending to latin square remark
Remark 11. The occurrences of k in L must appear in different rows, so L(k) can also be described as the
number of rows that contain k. Similarly, the occurrences of k in L must appear in different columns, so
L(k) can also be described as the number of columns that contain k.
lemma 12:
maximum heights and width
Suppose that q = n, so that L has the maximum possible width. Then we have L(k) = p and
E(k) = 0 for all k. Similarly, if p = n (so that L has the maximum possible height) then L(k) = q and
E(k) = 0 for all k.
Example 13: Consider the following Latin rectangle, with p = 2 and q = n = 5:
L =
[1 2 4 5 3]
[5 1 2 3 4]
Recall that C[j] is the set of possibilities for position j in the next row. For example, in column 2 we already
have a 2 and a 1, so these are not allowed, so C[2] = N \ {2, 1} = {3, 4, 5}. We can display all the sets C[j]
as follows:
[ 1 2 4 5 3 ]
[ 5 1 2 3 4 ]
[234 345 135 124 125]
We have used abbreviated notation, e.g. 234 for {2, 3, 4}.) To make the new row, we must choose one element from the possibilities in each column, making sure that we never choose the same element twice.
Corollary 55 tells us that this is possible, but does not tell us exactly how to do it. However, in this case it
is not difficult: in each column we can just take the first choice that has not already been used. This gives
2, 3, 1, 4, 5 as the new row. We can write in this new row and display the possibilities for row 4 as follows:
[ 1 2 4 5 3]
[ 5 1 2 3 4]
[ 2 3 1 4 5]
[ 34 45 35 12 12]
Again, in each column we can take the first choice that has not already been used. This gives row 4 and
leaves only one possibility for row 5. We end up with the following Latin square:
[1 2 4 5 3] [5 1 2 3 4] [2 3 1 4 5] [3 4 5 1 2] [4 5 3 2 1]
Corollary 14:
maximum possible height, but not the
maximum possible width
Let L be a Latin rectangle with q < p = n (so L has the maximum possible height, but not the
maximum possible width). Then L can be extended by adding extra columns to make an n × n Latin square.
