Question

Problem 5. (20 pts) Let r,n N be two natural numbers with r < n. An r x n matrix M consisting of r rows and n columns is said to be a Latin rectangle of size (r, n), if all the entries My belong to the set {1,2,3,..., n), for 1Si<T, 1Sj<T, and the same number does not appear twice in any row or in any column. By defini- tion, a Latin square is a Latin rectangle of size (n, n), ie. a Latin rectangle with r = n For instance, with r 3, n 5, the following two matrices are Latin rectangles 1 2 3 5 4 2 3 5 4 1, 4 5 1 2 3 4 1 5 2 3 2 413 5 whereas the following two matrices are not Latin rectangles 1 3 4 5 1 2 3 5 41, 4 5 1 2 3 (a) (5 pts) Show that two different Latin squares of size 3 × 3 exist. In addition, construct a Latin square of size 4 × 4. (b) (10 pts) Let M be a Latin rectangle of size (r, n) with r < n. Show that it is possible to add a row to M such that the resulting (r +1, n) rectangle is also a Latin rectangle. Hint: Build a bipartite graph G(M) = (AU B. E) from the Latin rectangle M according to the possible numbers (vertices in A) which can go into each column entry (vertices in B) of the new row. Then use Hall's Theorem to prove that G(M) admits a perfect matching (c) (5 pts) Show that any Latin rectangle of size (r, n) can be completed, by adding rows, to a Latin square of size (n, n)

Answer 1

part b and c are not solved sorry for that

a) two different latin square of 3 times 3 exist l_1 = [1 2 3 2 3 1 3 2 1] l_2 = [3 2 1 2 1 3 1 2 3] l_3 = [3 2 1 1 2 3 2 1 3] for 4 times 4 order l_1 = [1 2 3 4 2 3 4 1 3 4 1 2 4 3 2 3] l_2 = [3 4 2 1 4 3 1 2 1 2 3 4 2 1 4 3]