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:
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