Page 65 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 65
iusz Meszka: Combinatorial Designs 53
Thus each row and each column of R contain n −1 empty cells.
2
Example 23. A room square of side 9:
S = {0, 1, . . . , 9},
01 49 37 28 56
89 02 57 34 16
58 03 69 24 17
36 78 04 19 25
79 12 05 38 46
45 06 18 39 27
26 59 13 07 48
67 14 29 08 35
23 15 68 47 09
Theorem 32. A room square of side n exists if and only if n is odd and n ∈ {3, 5}.
For odd n , two 1-factorizations of the complete graph Kn+1, = {F1, F2, . . . , Fn } and
= {G1,G2, . . . ,Gn } are orthogonal if |Fi ∩ Gi | ≤ 1 for all 1 ≤ i , j ≤ n . The existence of a
Room square of side n is equivalent to the existence of two orthogonal 1-factorizations
of Kn+1.
Exercise 26.
Show that a Room square of side 5 does not exist.
Exercise 27.
Construct a Room square of side 7.
2.6.6 Hadamard matrices and designs
In 1893, Hadamard addressed the problem of the maximum absolute value of the deter-
minant of an n × n complex matrix H with all its entries on a unit circle. That maximum
value is n n . Among real matrices, this value is attained if and only if H has every entry
either 1 or −1, and satisfies H H T = n I . This condition means that any two distinct rows
of H (n) are orthogonal.
Definition 21. An n × n (±1)-matrix H (n ) is a Hadamard matrix of side n if H H T = n I .
Notice that we may multiply all entries in any row (and column) by -1 and the result
is again a Hadamard matrix. By a sequence of such multiplications, a Hadamard matrix
may be transformed into another Hadamard matrix, in which every entry in the first row
or in the first column is 1. Such a Hadamard matrix is called standardized.
Thus each row and each column of R contain n −1 empty cells.
2
Example 23. A room square of side 9:
S = {0, 1, . . . , 9},
01 49 37 28 56
89 02 57 34 16
58 03 69 24 17
36 78 04 19 25
79 12 05 38 46
45 06 18 39 27
26 59 13 07 48
67 14 29 08 35
23 15 68 47 09
Theorem 32. A room square of side n exists if and only if n is odd and n ∈ {3, 5}.
For odd n , two 1-factorizations of the complete graph Kn+1, = {F1, F2, . . . , Fn } and
= {G1,G2, . . . ,Gn } are orthogonal if |Fi ∩ Gi | ≤ 1 for all 1 ≤ i , j ≤ n . The existence of a
Room square of side n is equivalent to the existence of two orthogonal 1-factorizations
of Kn+1.
Exercise 26.
Show that a Room square of side 5 does not exist.
Exercise 27.
Construct a Room square of side 7.
2.6.6 Hadamard matrices and designs
In 1893, Hadamard addressed the problem of the maximum absolute value of the deter-
minant of an n × n complex matrix H with all its entries on a unit circle. That maximum
value is n n . Among real matrices, this value is attained if and only if H has every entry
either 1 or −1, and satisfies H H T = n I . This condition means that any two distinct rows
of H (n) are orthogonal.
Definition 21. An n × n (±1)-matrix H (n ) is a Hadamard matrix of side n if H H T = n I .
Notice that we may multiply all entries in any row (and column) by -1 and the result
is again a Hadamard matrix. By a sequence of such multiplications, a Hadamard matrix
may be transformed into another Hadamard matrix, in which every entry in the first row
or in the first column is 1. Such a Hadamard matrix is called standardized.
