Question

combinatorics: parts a and b

5) (a) Determine whether or not the two Latin squares are orthogonal. Show your work 3 41 1 2 3 4 3 4 1 2 3 4 1 2 2 3 4 1 3] L4123 2 3 4 1 4 1 (b) How many 4x4 Latin squares can be in a family of orthogonal order 4 Latin squares? Explain.

Answer 1

a) Recall that two Latin Squares are orthogonal if, when superimposed, no pair of numbers (a_ij, b_ij) repeats. However, this is not the case here - the pair of numbers (1, 1) appears twice, the same happens with (2, 2), (3,3) and (4,4) so these are not orthogonal.

b) The following takes the ideas given in a proof from J. Denes and A.D. Keedwell's 1974 book Latin Squares and their Applications where they state that no more than n-1 Latin Squares can exist in a family of pairwise orthogonal squares:

Say we have a set of pairwise 4 x 4 orthogonal latin squares. Then we can rename the symbols of one of the squares without affecting orthgonality. For example, take into account the following 3 x 3 orthgonal latin squares 1 2 3 1 2 3 2 3 13 1 2 3 1 2 2 3 1 Now if we exchange all the 2s and 3s from the second square we are left with another orthogonal pair: 2 3 1 2 1 3 3 1 2 3 2 1 We can conclude that renaming the symbols (or numbers) on any one of the squares in the set will have no effect on the orthogonality. We can then rename all the squares so that they all have the first row in the natural order (ie 1,2,3, 4) Now the first entry on the second row of all the squares must be different, if they were a, say for example 3 then the pair (3,3) will appear on the 3rd column of the 1st row and also on the 1st column of the 2nd row and the pairs of squares would not be orthogonal any more. Also this entry (2nd row, 1st column) cannot be the number 1 as we have already placed a 1 on that column So we must conclude that the squares must have either a 2,3 or 4 on the 1st column of the 2nd row, and cannot be repeated so there can only be 3 latin squares in the set