Hadamard

Beschrijving

In verschillende wetenschappelijke disciplines bestaat er een zekere belangstelling voor zogenaamde Hadamard-matrices, kortweg H-matrices. Dit zijn n × n matrices (vierkant dus), gevuld met de getallen 1 en -1, zó dat alle rijen, wanneer gezien als vectoren, loodrecht op elkaar staan, d.w.z. hun inproduct is 0. Laat H zo'n H-matrix zijn en hij het element in de i-de rij en de j-de kolom van H (1 <= i, j <= n). Dan geldt dus dat hij = 1 en \sum_{j=1}^{n} h_{i_1 j} hi_2 j = 0, als i1 <> i2
Enkele voorbeelden van H-matrices zijn:
11
1 -1

1 -1 1 1
1 -1 -1 -1
1 1 1 -1
1 1 -1 1

Het is niet zo ingewikkeld om aan te tonen dat als n groter dan twee is, n deelbaar door vier moet zijn om een H-matrix van die afmetingen mogelijk te maken. Ronduit eenvoudig is het om in te zien dat een H-matrix een H-matrix blijft als je twee of meer rijen verwisselt. Dit laatste geldt natuurlijk ook voor de kolommen.

De Opgave

Met deze wetenschap in het achterhoofd kunnen we twee H-matrices equivalent noemen, als de één uit de ander door rij- en/of kolomverwisselingen ontstaat. Merk daarbij op dat het niet uitmaakt of je eerst een aantal rijverwisselingen uitvoert en dan een aantal kolomverwisselingen, of andersom: in beide gevallen is het resultaat gelijk. Voor kleine H-matrices (d.w.z n klein) is het nog vrij eenvoudig om met de hand vast te stellen of ze equivalent zijn of niet. Voor grotere H-matrices wordt dit al een stuk lastiger. Daarom wordt jou gevraagd een programma te schrijven dat die taak kan uitvoeren.

De Invoer

De invoer begint met een regel met daarop het aantal runs. Daarna volgt per run: een regel met daarop de waarde van n, de afmeting van de H-matrices (n = 2 of 4 <= n <= 1000). De daarop volgende n regels bevatten rij 1 tot en met rij n van de eerste matrix. Zo'n rij bestaat uit n getallen 1 of -1, gescheiden door spaties. Na de eerste matrix volgt een lege regel, waarna de tweede matrix van de run volgt, die op dezelfde manier gerepresenteerd wordt.

De Uitvoer

Voor elke run moet de uitvoer het resultaat van het onderzoek naar equivalentie bevatten. Als de twee H-matrices van één run equivalent met elkaar blijken te zijn, dan dient in de uitvoer een regel met de tekst equivalent te verschijnen; zoniet, dan dient een regel met de tekst niet equivalent te worden afgedrukt.

Voorbeeld

Bij de invoer
2
4
  1 -1  1  1
  1 -1 -1 -1
  1  1  1 -1
  1  1 -1  1

 -1 -1 -1  1
  1 -1  1  1
 -1  1  1  1
 -1 -1  1 -1
8
  1 -1  1  1 -1 -1 -1 -1
  1 -1 -1 -1 -1 -1  1  1
 -1 -1 -1  1  1 -1  1 -1
  1  1 -1  1 -1  1  1 -1
  1 -1  1  1  1  1  1  1
  1 -1 -1 -1  1  1 -1 -1
 -1 -1 -1  1 -1  1 -1  1
  1  1 -1  1  1 -1 -1  1

 -1  1 -1  1 -1 -1 -1  1
  1 -1 -1 -1 -1 -1  1  1
 -1  1 -1 -1  1 -1  1 -1
  1  1 -1 -1 -1  1 -1 -1
  1 -1 -1  1  1 -1 -1 -1
  1  1 -1  1  1  1  1  1
  1  1  1  1 -1 -1  1 -1
  1  1  1 -1  1 -1 -1  1
hoort de uitvoer
niet equivalent
equivalent