Vierkant van Room

Een vierkant van Room of Room-vierkant van zijde $t$ is een vierkante tabel met $t$ rijen en $t$ kolommen, waarin de inhoud van elke cel gekozen is uit een verzameling $S$ van $t+1$ symbolen, zodanig dat:

1. elke cel ofwel leeg is ofwel een ongeordend paar van twee verschillende symbolen uit $S$ bevat;
2. elk symbool uit $S$ precies eenmaal voorkomt in elke rij en in elke kolom van de tabel;
3. elk ongeordend paar van twee verschillende symbolen uit $S$ precies eenmaal voorkomt in de tabel.

Gewoonlijk wordt als de verzameling $S$ de getallen van 0 tot en met $t$ gebruikt. Dergelijke vierkanten vinden toepassing in experimenteel ontwerpen.

Geschiedenis

Room-vierkanten zijn genoemd naar de wiskundige Thomas Gerald Room, die ze in 1955 in een kort artikel onder de aandacht bracht. Maar ze waren echter reeds in 1897 ingevoerd door Howell, in het kader van de constructie van bridgetoernooien. Ze worden dan ook Howell-rotaties genoemd. In deze context zijn er $t+1$ teams die elk eenmaal tegen elk ander team spelen. In elke ronde speelt elk team een wedstrijd. Elk team speelt eenmaal op elk speelbord. De kolommen in de tabel stellen de speelborden voor en de rijen de verschillende spelrondes. De getallen in de cellen stellen de teams voor die tegen elkaar uitkomen aan een bepaald speelbord in een bepaalde spelronde.

Voorbeeld

Dit is een voorbeeld van een 7-bij-7-Room-vierkant met als symbolen de cijfers 0 tot en met 7:

0,7			1,5		4,6	2,3
3,4	1,7			2,6		0,5
1,6	4,5	2,7			0,3
	0,2	5,6	3,7			1,4
2,5		1,3	0,6	4,7
	3,6		2,4	0,1	5,7
		0,4		3,5	1,2	6,7

Eigenschappen

• Een Room-vierkant blijft een Room-vierkant onder rij- of kolompermutaties.
• Een Room-vierkant blijft een Room-vierkant onder een permutatie van de symbolen.
• De getransponeerde matrix van een Room-vierkant (beschouwd als een matrix) is ook een Room-vierkant.
• Er bestaan geen Room-vierkanten met een even aantal kolommen of rijen.
• Er bestaan ook geen Room-vierkanten met zijde 3 of 5.
• Als $r$ en $n$ oneven getallen zijn, met $r$ kleiner dan of gelijk aan $n,$ en er bestaat een Room-vierkant met zijde $r,$ dan bestaat er ook een Room-vierkant met zijde $rn.$
• Er bestaat wel een Room-vierkant met zijde $r$ voor elk oneven getal $r$ groter dan 5. Dit werd in 1973 bewezen door W.D. Wallis. Wallis had in 1972 reeds aangetoond dat er een Room-vierkant met zijde $r$ bestaat voor elke oneven $r$ behalve 3,5 en mogelijk 257. Op de 4e Southeastern Conference on Combinatorics in 1973 bracht Wallis dan het bewijs aan dat er wel degelijk een Room-vierkant van zijde 257 bestaat.

Gestandaardiseerd Room-vierkant

Een Room-vierkant met als symboolverzameling $\{0,1,2,\ldots ,v\}$ is gestandaardiseerd met betrekking tot 0 wanneer de cel $(i,i)$ het ongeordende paar $\{0,i\}$ bevat. Men kan elk Room-vierkant in gestandaardiseerde vorm brengen door rijen en kolommen te verwisselen.

Aan een gestandaardiseerd Room-vierkant van zijde $r$ kan men een vierkante matrix $A=(a_{i,j})$ koppelen van dezelfde grootte, waarbij:

$a_{i,j}=1$ als cel $(i,j)$ niet leeg is,

$a_{i,j}=0$ als cel $(i,j)$ leeg is.

Scheef Room-vierkant

Een gestandaardiseerd Room-vierkant is scheef wanneer voor de gekoppelde matrix $A$ geldt:

$A+A^{T}=J+I$

waarin $A^{T}$ de getransponeerde matrix is, $I$ de eenheidsmatrix en $J$ de vierkante matrix gevuld met enen; beied met zijde $r.$

Dit betekent dat een Room-vierkant scheef is wanneer de diagonale cellen in volgorde $\{0,1\},\{0,2\},\ldots ,\{0,r\},$ zijn en, als $i$ verschilt van $j,$ exact een van de cellen $(i,j)$ en $(j,i)$ leeg is.

Het was anno 1974 voor een eindig aantal oneven getallen, waaronder 9 en 39, nog niet bekend of er een scheef Room-vierkant met die zijde bestaat. D.R. Stinson kon uiteindelijk in 1981 bewijzen dat scheve Room-vierkanten bestaan voor elke oneven zijde groter dan 5.

Bronnen, noten en/of referenties