View source for Room square

A Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r1101401.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r1101402.png" />, is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r1101403.png" />-array <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r1101404.png" /> defined on an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r1101405.png" />-set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r1101406.png" /> with the following properties:

1) each cell of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r1101407.png" /> is either empty or contains an unordered pair of distinct elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r1101408.png" />;

2) each element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r1101409.png" /> occurs precisely once in each row and column of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014010.png" />;

3) every unordered pair of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014011.png" /> is in precisely one cell of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014012.png" />. A necessary condition for a Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014013.png" /> to exist is that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014014.png" /> be odd. An example of a Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014015.png" /> is listed below.
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014016.png" /> 0</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1">1 5</td> <td colname="5" style="background-color:white;" colspan="1"></td> <td colname="6" style="background-color:white;" colspan="1">4 6</td> <td colname="7" style="background-color:white;" colspan="1">2 3</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="7" style="background-color:white;" colspan="1"></td> <td colname="6" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">3 4</td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014017.png" /> 1</td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1">2 6</td> <td colname="6" style="background-color:white;" colspan="1"></td> <td colname="7" style="background-color:white;" colspan="1">5 0</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="7" style="background-color:white;" colspan="1"></td> <td colname="6" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">6 1</td> <td colname="2" style="background-color:white;" colspan="1">4 5</td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014018.png" /> 2</td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> <td colname="6" style="background-color:white;" colspan="1">3 0</td> <td colname="7" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="7" style="background-color:white;" colspan="1"></td> <td colname="6" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1">0 2</td> <td colname="3" style="background-color:white;" colspan="1">5 6</td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014019.png" /> 3</td> <td colname="5" style="background-color:white;" colspan="1"></td> <td colname="6" style="background-color:white;" colspan="1"></td> <td colname="7" style="background-color:white;" colspan="1">4 1</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="7" style="background-color:white;" colspan="1"></td> <td colname="6" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">5 2</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1">1 3</td> <td colname="4" style="background-color:white;" colspan="1">6 0</td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014020.png" /> 4</td> <td colname="6" style="background-color:white;" colspan="1"></td> <td colname="7" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="7" style="background-color:white;" colspan="1"></td> <td colname="6" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1">6 3</td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1">2 4</td> <td colname="5" style="background-color:white;" colspan="1">0 1</td> <td colname="6" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014021.png" /> 5</td> <td colname="7" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="7" style="background-color:white;" colspan="1"></td> <td colname="6" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1">0 4</td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1">3 5</td> <td colname="6" style="background-color:white;" colspan="1">1 2</td> <td colname="7" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014022.png" /> 6</td> </tr> </tbody> </table>

</td></tr> </table>

Room squares were named after T.G. Room, who published a paper in 1955 in which he constructed a Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014023.png" /> and proved that Room squares of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014025.png" /> do not exist. However, Room squares were actually constructed much earlier. In 1850, T.M. Kirkman used a Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014026.png" /> to solve the Kirkman schoolgirl problem for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014027.png" /> girls, and the first infinite classes of Room squares were constructed by R.R. Anstice in 1852– 1853 [[#References|[a1]]]. Several small Room squares were also constructed by E.C. Howell for use as schedules for duplicate bridge tournaments at the end of the nineteenth century. The existence of Room squares was finally completed in the early 1970s by R.C. Mullin and W.D. Wallis [[#References|[a4]]]: A Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014028.png" /> exists if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014029.png" /> is odd and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014030.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014031.png" />. The proof uses a number of direct and recursive constructions. An extensive literature on Room squares is available, see [[#References|[a3]]].

One application of Room squares is in the construction of round robin tournaments. A Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014032.png" /> can be used to construct a round robin tournament with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014033.png" /> teams which has the following properties: every team plays every other team exactly once during the tournament; every team plays in exactly one game in each round; and every team plays at every location exactly once.

A Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014034.png" /> is standardized with respect to the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014035.png" /> if cell <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014036.png" /> contains the pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014037.png" />. A standardized Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014038.png" /> is skew if for every pair of cells <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014039.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014040.png" /> (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014041.png" />) exactly one is filled. The existence of skew Room squares has been established [[#References|[a5]]]: There exists a skew Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014042.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014043.png" /> is odd and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014044.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014045.png" />. Skew Room squares have been quite useful in constructions for several other types of combinatorial designs, see [[#References|[a3]]].

Room squares with additional properties have also been studied; these include Room squares with sub-Room squares (incomplete Room squares), maximum empty subarray Room squares, perfect Room squares, and balanced Room squares (complete balanced Howell rotations), see [[#References|[a3]]] for references. For generalizations of Room squares to larger block size and higher dimension, see [[Design with mutually orthogonal resolutions|Design with mutually orthogonal resolutions]].

Room squares are equivalent to several other combinatorial configurations, [[#References|[a2]]]. In particular, the existence of the following designs are equivalent:

a) a Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014046.png" />;

b) a Room frame of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014047.png" />;

c) two pairwise orthogonal symmetric Latin squares of order n (see [[Latin square|Latin square]]);

d) a [[Howell design|Howell design]], <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014048.png" />;

e) two pairwise orthogonal one-factorizations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014049.png" /> (cf. also [[One-factorization|One-factorization]]);

f) two orthogonal resolutions of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110140/r11014050.png" />-BIBD (see [[Design with mutually orthogonal resolutions|Design with mutually orthogonal resolutions]]).

In some of the earlier literature, Room squares are also called Room designs.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  I. Anderson,   "Cyclic designs in the 1850s; the work of Rev. R.R. Anstice"  ''Bull. ICA'' , '''15'''  (1995)  pp. 41–46</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.H. Dinitz,   "Room squares"  C.J. Colbourn (ed.)  J.H. Dinitz (ed.) , ''CRC Handbook of Combinatorial Designs'' , CRC  (1996)  pp. 437–442</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.H. Dinitz,   D.R. Stinson,   "Room squares and related designs"  J.H. Dinitz (ed.)  D.R. Stinson (ed.) , ''Contemporary Design Theory: A Collection of Surveys'' , Wiley  (1992)  pp. 137–204</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.C. Mullin,   W.D. Wallis,   "The existence of Room squares"  ''Aequat. Math.'' , '''13'''  (1975)  pp. 1–7</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D.R. Stinson,   "The spectrum of skew Room squares"  ''J. Austral. Math. Soc. A'' , '''31'''  (1981)  pp. 475–480</TD></TR></table>