aus Spektrum der Wissenschaft 1/1996

Mathematische Unterhaltungen

Manche magischen Quadrate haben eine innere Struktur,

die es erlaubt, aus einem einzelnen magischen Quadrat viele andere

zu machen.

 

Von Christoph Pöppe

 

Kann man ein Brett aus 5 x 5 quadratischen Feldern rnit fünf Farben so kolorieren, daß jede pro Zeile und Spalte nur einmal vorkommt?

Das ist nicht schwer Man verteilt die fünf Farben beliebig auf die Felder der ersten Zeile. Diese Anordnung kopien man um ein Feld nach rechts versetzt in die nächste Zeile; das nach rechts überstehende Feld fügt man links in die Leerstelle dieser Zeile ein. In derselben Weise entsteht aus der zweiten Zeile die dritte, und so weiter. Diese Methode funktioniert für Quadrate jeder Größe.

Eine Anordnung, welche die genannte Bedingung erfüllt, heißt lateinisches Quadrat. Der Name rührt daher, daß der Baseler Mathematiker Leonhard Euler (1707 bis 1783), der seit seinem 20. Lebensjahr in Sankt Petersburg, dann in Berlin und schließlich wieder in Sankt Petersburg wirkte und außer vielen anderen Dingen auch solche Quadrate systematisch untersuchte, lateinische Buchstaben anstelle der Farben verwendete.

Die Anzahl der Felder je Zeile beziehungsweise Spalte heißt Ordnung des Quadrats. Ein Quadrat der Ordnung n hat also Felder.

Wird zusätzlich gefordert, daß auch in den Diagonalen jede Farbe nur einmal veitreten ist, muß man das geschilderte Verfahren etwas abwandeln, denn es färbt alle Felder der Hauptdiagonale (von links oben nach rechts unten) gleich. Für Quadrate ungerader Ordnung versetze man die Felder beim Übergang von einer Zeile zur nächsten nicht um eins nach nechts sondern um zwei; für gerade Ordnung ist die Situation komplizierter.

Interessanter wird das Problem. wenn jedes Feld zwei Kennzeichen trägt, etwa eine Innen- und eine Außenfarbe oder -wie bei Euler - einen lateinischen und einen griechischen Buchstaben. Dabei ist nicht nur verboten. ein Kennzeichen mehr als einmal in eine Zeile oder Spalte zu setzen; zusätzlich ist vorgesschrieben, daß jede Kombination von Kennzeichen nur etnmal vorkommen darf. Ein griechisch-lateinisches Quadrat entspicht also einem Paar lateinischer Quadrate, die in gewissem Sinne so verschieden voneinander sind wie nur möglich: Beispielsweise müssen die Randflächen der Felder, deren Innenfarbe Rot ist, sämtliche vorkommenden Farben tragen; sonst wäre eine Kombination doppelt vertreten. Ein solches Paar von Quadraten (eines besteht aus den Innenfarben, das andere aus den Außenfarben) heißt orthogonal - eine etwas weit hergeholte Metapher aus der Geometrie, wo zwei gleich lange Vektoren voneinander maximal verschieden sind, wenn sie aufeinander senkrecht (orthogonal) stehen.

Ein Paar orthogonaler lateinischer Quadrate der Ordnung 5 ist noch mit mäßiger Mühe zu finden: Man nehme das Quadrat mit der Versetzung 2 und sein Spiegclbild, wobei die Hauptdiagonale Spiegelachse ist (Bild 2 links) Für andere Ordnungen kann die entsprechendeAufgabe extrem schwierig werden. So glaubte Euler, es gebe keine griechisch-lateinischen Quadrate der Oidnungen 6, 10, 14 und so weiter (ungerade Vielfache von 2), weil er trotz intensiver Suche keine gefunden hatte. Bezüglich der Ordnung 6 hatte er recht; für die anderen Fälle hat es immerhin fast 200 Jahre gedauert, bis 1959 E. T, Parker von der Computerfirma Univac sowie R. C. Bose und S. S. Shrikande von der Universität von North Carolina (genannt "Euler's spoilers", weil sie damit das ansonsten strahlende Bild ihres genialen Vorgängers ein wenig befleckt hatten) ein Gegenbeispiel fanden. Das Magnetlegespiel

,,Gewonnen, Herr Euler", das Spektrum der Wissenschaft vertreibt, ersatzweise das entsprechende Diskettenprograrnrn, gibt Ihnen Gelegenheit, ein griechisch-lateinisches Quadrat der Ordnung 10 selbst zu suchen

 

 

Magische Quadrate

 

Wenn man aber erst ein orthogonales Paar ateinischer Quadrate bat, in dem außerdem jede Diagonale bei wenigstens einem Partner die Verschiedeuheitsbedingung erfüllt, ist daraus mit leichter Mühe ein magisches Quadrat zu machen

(Bild 2): Man ersetze die Kennzeichen (Farben beziehungsweise Buchstaben) durch die Ziffern von 0 bis n - 1 und schreibe in jedes Feld die beiden zugehörigen Ziffern nebeneinander Die entstehenden zweistelligen Zahlen sind im Zahlensystem zur Basis n zu verstehen:

In einem 5 x 5-Quadrat bezeichnet 32 die Zahl 3 x 5 + 2, also 17 in der üblichen Dezimalschreibweise.

Warum ist das so konstruierte Quadrat magisch? Warum ist die Summe der Zahlen in jeder Zeile, Spalte und Diagonale die gleiche? Nun, in den Feldern jeder Zeile kommen in der rechten (Eincr-)Stelle die Ziffern von 0 bis n - 1

jeweils genau einmal vor, desgleichen in der linken Stelle; also ist (für n = 5) die Zeilensumme jedesmal (0+1+2+3+4) + 5 x (0+1 + 2 + 3 + 4) = 60)  Für die Spalten- und Diagonalensummen gilt Entsprechendes. Außerdem - zweite Bedingung für magische Quadrate - ist jede Ziffernkombination und damit jede Zahl zwischen 0 und   - 1 genau einmal vcrtreten.

Üblicherweise schreibt man in ein magisches Quadrat der Ordnung n nicht die Zahlen von 0 bis - I, sondern von l bis . Aber ob man zum Wert jedes Feldes 1 addiert oder nicht, ist für die Eigenschaft ,,magisch" unwesentlich; und für das Folgende ist es geschickter. bei 0 anzufangen  Die magische Konstante (der gemeinsame Wert aller Zeilen-, Spalten- nnd Diagonalensummen) eines Quadrates der Ordnung n ist dementsprechend nicht, wie üblich, n(n2 + 1)/2, sondein n(n2 - 1)/2.

Magische Quadrate haben eine uralte Geschichte. Aus der Zeit des chinesischen Kaisers Lu-Shu (um 2200 vor Christus) ist ein magisches Quadrat dritter Ordnung überliefert. Die europäische Tradition hat jahrhundertelang von einem Manuskript eines Gelehrten namens Manuel Moschopoulus gezehrt, der Anfang des  15. Jahrhunderts in Konstantinopel lebte In diesem Manuskript sind bereits Konstruktionsregeln für magische Quadrate jeder Ordnung aufgeführt. Cornelius Agrippa von Nettesheim (1486 bis 1535) konstruierte magische Quadrate der Ordnungen 3 bis 9, anscheinend nach den Methoden des Moschopoulos, setzte sie mit den Planeten (im damaligen Verständnis) Saturn, Jupiten Mars, Sonne, Venus, Merkur und Mond - in dieser Reihenfolge - in Beziehung und leitete daraus im Wortsinne magische Eigenschaften der Planeten und der Quadrate her. Berühmt geworden ist das magische Quadrat vierter Ordnung aus dem Bild ,,Melencolia' von Albrecht Dürer (1471 bis 1528); es ist so arrangiert, daß das Entstehungsjahr 1514 in der Mitte der untersten Zeile erscheint.

Das Konstruktionsverfahren über die griechisch-lateinischen  Quadrate  ist nicht unbedingt das einfachste. Es liefert jedoch ein instruktives Beispiel für eine bisher kaum beachtete Eigenschaft mancher magischen Quadrate: ihre Zerlegbarkeit

Ich nenne ein magisches Quadrat edel, wenn es nach Art eines griechisch-lateinischen Quadrats zusammengesetzt ist, genauer: wenn es in eine Summe zweier (oder mehrerer) trivial-magischer Quadrate zerlegbar ist. Dabei soll ein Quadrat trivial-magisch heißen, wenn es gleiche Zeilen-, Spalten- und Diagonalsummen hat; es muß aber nicht aus lauter verschiedenen Zahlen bestehen, noch nicht einmal lateinisch sein. Zum Beispiel ist auch ein Quadrat, das in jedem Feld dieselbe Zahl trägt, trivial-magisch. Ein lateinisches Quadrat ist nicht immer trivial-magisch, sondern nur dann, wenn auch entlang. seiner Diagonalen keine zwei Felder gleich sind.

Für die Konstruktion eines edlen Quadrats muß man, wie gesagt, nicht unbedingt griechisch-lateinische zu  Hilfe nehmen. So produziert die einfachste Konstruktionsregel für magische Quadrate ungerader Ordnung stets edle Quadrate (Kasten auf dieser Seite).

 

Das Austauschverfahren

 

Zerlegungen anderer magischer Quadrate ergeben Komponenten, die nicht lateinisch sind, dafür aber andere, um so interessantere Eigenschaften haben. Eine Konstruktionsregel für magische Quadrate, deren Ordnung ein Vielfaches von 4 ist, liefeert Beispiele. Das Dürer-Quadrat sowie das Jupiter- und das Merkur-Quadrat des Agrippa von Nettesheim sind - bis auf Drehungen, Spiegelungen und das Addieren der obligatorischen Eins - nach diesem Muster gebaut.

Wesentlicher Bestandteil des Verfahrens ist ein (gedachter) Stempel, der die acht Diagonalenfelder eines 4 x 4-Quadrats einfärbt und die restlichen acht unverändert läßt (Bild 3). Man schreibt zunächst in ein Qnadrat der Seitenlänge n -wobei n ein beliebiges Vielfaches von 4 ist - die Zahlen von 0 bis n2 - 1 zeilenweise der Reihe nach ein und bestempelt es dann lückenlos und überlappungsfrei (Bild 3 links). Jede durch den Stempel gefärbte Zahl vertauscht man nun mit der ebenfalls gefärbten, die ihr in bezug auf den Mittelpunkt des Quadrats genau gegenüberliegt (Bild 3 rechts). Beide Zahlen ergänzen sich stets zu -1; man nennt solche Paare komplementär.

Ohne Zweifel enthält das Endprodukt dieser Prozedur nach wie vor alle Zahlen von 0 bis -1; es hat ja nur die Hälfte von ihnen die Plätze getauscht. Es bleibt auch symmetrisch in dem Sinne, daß Paare komplementärer Zahlen einander bezüglich des Mittelpunktes genau ge genüberstehen.

Aber wie kommt es, daß alle Zeilen-, Spalten- und Diagonalsummen den richtigen Wert haben? Man kann nachrechnen, daß das bei dcn Diagonalen schon vorher der Fall war; und das Verfahren stellt beide Diagonalen lediglich auf den Kopf, denn alle Diagonalenfelder werden vom Stempel getroffen. Dagegen sind in der ursprünglichen Anordnung die Summen der oberen Zeilen zu klein und die der unteren zu groß; Entsprechendes. wenn auch weniger kraß, gilt für die Summen der Spalten links beziehungsweise rechts von der Mitte. Die Vertauschungsaktion gleicht diese Abweichungen gerade aus.

Wie das genau funktioniert, sieht man am besten an Quadraten, deren Ordnung eine Potenz von 2 ist: 4, 8, 16, 32 und so

Weiter. In diesem Falle ist nämlich auch eine Zweierpotenz, und es liegt nahe,

zur Zahldarstellung die Basis 2 zu verwenden. Das läuft auf die cornputerübliche Binärschreibweise hinaus, deren einzige Ziffern 0 und 1 sind. Ein magisches Quadrat der Ordnung 16 enthält dic Zahlen von 0 bis 16² - 1 = 255; das sind gerade alle achtstelligen Binärzahlen (führende Nullen mitgeschrieben).  Und ebenso, wie man das eingangs beschriebene 5 x 5-Quadrat, zur Basis 5 geschrieben, in zwei trivial-magische Quadrate zerlegen kann, deren jedes einer Stelle in der Zahldarstellung zugeordnet ist, so zerfällt das 16 x 16-Quadrat in acht trivial-magische Quadrate, deren jedes zu einer Binärstelle gehört (Bild 4): Es ist edel zur Basis 2.

Alle  diese  Komponenten-Quadrate enthalten nur Nullen und Einsen; weil aber die Eins je nach Komponente eine, zwei oder mehr Stellen links vom (gedachten) Binär-Komma steht, hat sie den Wert 1, 2, 4, 8, 16, 32, 64 oder 128. Die Komponenten-Quadrate zeigen ein auffälliges, regelmäßiges. aber nicht ganz symmetrisches Muster; daran ist zu erkennen, daß das ursprüngliche magische Quadrat eine globale Ordnug aufweist. Die Symmetrie ist aber gerade nicht so umfassend, daß ein und dieselbe Kombination schwarzer und weißer Felder an mehr als einer Position aufträte. Denn

dann hätten diese beiden Felder den gleichen Zahlenwert. was nicht sein darf.

Wie kommt diese Ordnung zustande? Es ist sehr einfach, die zu einer Binärzahl komplementäre Zahl zu finden. Für n =24  = 16 beispielsweise ist n² = 28 256, und n² - 1 = 255 hat die Binärdarstellung 11111111. Zwei achtstellige Binärzahlen sind genau dann komplementär bezüglich 28 - 1, wenn die eine da eine Null hat, wo in der anderen eine Eins steht, und umgekehrt. Die Wirkung des Stempels - die Bildung der Komplementärzahl - besteht also darin, daß jede Null in der Binärdastellung durch eine Eins ersetzt wird und umgekehrt. Insbesondere wirkt der Stempel auf jede Binärstelle - und damit auf jedes Komponenten-Quadrat - unabhängig von den anderen: Wo er trifft, vertauscht er Schwarz und Weiß. Somit genügt es, sich zu vergewissern, daß der Stempel aus jeder Zerlegungs-Komponente des Quadrats, mit dem alles begann (mit den Zahlen in der natürlichen Reihenfolge). ein trivial-magisches Quadrat macht (Kasten links).

 

 

Umformungen

 

Hat man erst einmal ein magisches Quadrat, so kann man daraus durch einfache Umformungen viele neue machen. Eine zwei oder drei Vierteldrehungen sowie Spiegelungen an einer Diagonalen oder Mittelsenkrechten lassen die magischen Eigenschaften unverändert. Das gleiche gilt für kompliziertere Operationen wie die gleichzeitige Vertauschung zweier komplementärer Spalten und der beiden zugehörigen Zeilen oder eine weitere, bei der ganze Viertel eines Quadrats in die diagonal gegenüberliegende Ecke geschoben werden (Bild 5).

Das Sortiment der Umformungsmöglielkeiten wird durch Zerlegungen erheblich erweitert, weil die Komponenten einer Zerlegung bis zu einem gewissen Grade voneinander unabhängig sind. Wenn die Komponenten lateinische Quadrate sind, die auch in den Diagonalen keine zwei gleichen Elemente enthalten, darf man in jeder Komponente die Numerierung beliebig ändern. Jede Ziffer darf durch eine andere, nur dürfen nicht zwei verschiedene Ziffern durch dieselbe ersetzt werden: eine Permutation. Im zusanrnengcsetzten Quadrat tauschen dadurch zwar gewisse Zahlen ihre Plätze, aber es stehen dieselben Zahlen im Quadrat wie zuvor, und die Summenkriterien sind immer noch erfüllt, weil das für die Komponenten gilt. Wenn, wie beim Standardverfahren für Quadrate ungernader Ordnung. eine Diagonale n-mal die Zahl (n - 1 )/2 enthält, muß man diese Zahl unverändert lassen, darf aber die übrigen unbekümmert permutieren.

Bei den 0-1-Komponenten-Quadraten der Binärdarstellung ist die einzig mögliche Permutation die Vertauschung von Schwarz und Weiß. Immerhin ergibt das für die acht Komponenten des 16 x 16-Quadrats 28 = 256 Kombinationen. Insbesondere kann man durch geeignete Wahl der Vertauschungen erzwingen, daß eine vorgewählte Zahl in die linke obere Ecke (oder in irgendein anderes vorbestimmtes Feld) gerät.


Der Kölner Künstler Paul Heimbach hat dieses Prinzip für Quadrate der Ordnung 8 entdeckt, für seine ästhetischen Ziele genutzt und damit den Anstoß zu diesem Artikel gegeben. Er interpretiert die sechs Komponenten des 8x8-Quadrats als Masken oder Schablonen, Platten, die anstelle der schwarzen Felder quadratische Löcher enthalten. Eine Maske nach der anderen legt er auf ein Blatt Papier und überstreicht sie mit (nicht-deckender) Farbe - jede Maske mit einer anderen. Heimbach verwendet die Grundfarben Rot, Blau und Gelb in jeweils zwei verschiedenen Intensitäten, (So ist das Prinzip; die Ausführung kann völlig anders sein.) Am Ende ergibt sich ein magisches Farbquadrat: Jede Mischung von null bis zu sechs Maskenfarben ist auf genau einem Feld realisiert. Zusätzlich ist das Gesamtbild auch noch ausgewogen in dem Sinne, daß jede Maskenfarbe in jeder Zeile und jeder Spalte in genau der Hälfte der Felder enthalten ist (Bild 1).

Damit sind die Urnformungsmöglichkeiten noch längst nicht erschöpft. Die Zuordnung der Masken (und ihrer Farben) zu den Binärstellen ist nämlich keineswegs zwingend. Was geschieht, wenn man beispielsweise die zweite und die vierte Maske vertauscht?

An den Stellen, wo beide Masken schwarz oder beide weiß sind, ändert sieh gar nichts. Eine Zahl, bei der eine Maske weiß, die andere schwarz ist. tauscht ihren Platz mit derjenigen, die in diesen beiden Masken die umgekehrte Kombination, in allen anderen aber denselben Wert hat. Also sind nach wie vor dieselben Zahlen im Quadrat vertreten, und die Summenkriterien sind ohnehin erfüllt. Für das Merkur-Quadrat (Ordnung 8) vermehren sich die Variationsmöglichkeiten durch die Vertauschbarkeit der Masken um den Faktor 6! = 720. Eine von Heimbach erstellte Compact Disc spielt das ganze Sortiment der so erhältlichen Varianten ab.


Aus einem einzigen edlen Quadrat der Ordnung 16 ergibt sich durch Umkehrung von Schwarz und Weiß sowie durch Vertauschung von Masken ein reichhaltiges Sortiment von insgesamt 256x8! =10321920 Varianten.

 

 

Verallgemeinerungen

 

Bis jetzt. habe ich gezeigt, wie man edle Quadrate konstruiert, deren Ordnung ungerade oder eine Zweierpotenz ist. Was ist mit den übrigen Ordnungen?

Man kann magische Quadrate in einem gewissen Sinne miteinander rnultiplizieren, und das Produkt zweier edler Quadrate ist wieder edel, wenn man die richtige Zerlegung wählt. Wie multipliziert man ein Quadrat der Ordnung p mit einem der Ordnung q (es kommt auf die Reihenfolge der Faktoren an)? Man bläht jedes Feld des p x p-Qualrats zu einem Block der Größe q x q auf. In alle Felder eines Blocks schreibt man dieselbe Zahl, und zwar mal den ursprünglichen Wert des Feldes. Dann addiert. man zu jedem Block - Feld für Feld - das qxq-Quadrat. Das so konstruierte Quadrat hat die Ordnung pq und ist magisch, denn es enthält jede Zahl von 0 bis (pq)² - 1 genau einmal und erfüllt die Summenkriterien.

Um nachzuweisen, daß es auch edel ist, muß man es zerlegen. Dafür gibt es ein Verfahren, das auf magische Quadrate aller Art (auch unedle) anwendbar ist:

die Division mit Rest.

Man zerlege bei einem Quadrat der Ordnung n die Zahl n² irgendwie in Faktoren, bei ungeradem n zum Beispiel in nxn, bei einer Zweierpotenz in 2 x2 x ... x 2. Es muß nicht die Prinfaktorzerlegung sein, und die Reihenfolge der Faktoren ist - zunächst - beliebig. Man dividiere nun das magische Quadrat Feld für Feld durch den ersten Faktor, schreibe die Quotienten in ein weiteres Quadrat und die Reste in ein drittes.

Das  Quotienten-Quadrat  dividiere man in derselben Weise durch den zweiten Faktor; das ergibt wieder ein Quotienten- und ein Restequadrat, und so weiter, bis die Faktoren erschöpft sind. Die mit den jeweils korrekten Faktoren multiplizierten Restequadrate ergeben eine Zerlegung des ursprünglichen Quadrats. Allerdings sind im allgemeinen die Restequadrate nicht trivial-magisch.

Dieses Divisionsverfahren läuft auf eine Darstellung der Zahlen des Quadrats bezüglich einer gemischten Basis hinaus (Spektrum der Wissenschaft, Dczember .1995. Seite 10); die oben besprochenen Zerlegungen zu den reinen Basen 5 und 2 sind Spezialfälle. Auch in einer Zerlegung zu einer gemischten Basis darf man die Reihenfolge der Kornponenten vetauschen, was zugleich ihren Stellenwert ändert; ein edles Quadrat verwandelt sich dadurch in ein anderes, gleichfalls edles.

Warum? Man zerlege das oben definierte Produktquadrat aus edlen Quadraten der Ordnungen p und q bezüglich der Faktoren q, q, p, p (in dieser Reihenfolge). Die ersten beiden Divisionen spalten den Anteil ab, der aus der Addition des q x q-Quadrats zu jedem Block stammt; also bestehen die zugehörigen Restequadrate aus der (p x p)-fachen Wiederholung der Komponentenquadrate des q x q-Quadrats. Die waren nach Voraussetzung trivial-magisch; also gilt das auch für ihre Wiederholung. Was nach den beiden ersten Divisionen übrigbleibt, ist das aufgeblähte p x p-Quadrat. Dessen Zerlegung produziert aufgeblähte Varianten der Komponenten des

p x p-Quadrats. die offensichtlich ebenfalls trivial-magisch sind. Wenn die ursprünglichen Quadrate nicht nur edel bezüglich der Zerlegungen p, p beziehungsweise q , q sind, sondern - wie die Zweierpotenz-Quadrate - noch feinere Zerlegungen zulassen, bleiben diese Feinheiten bei der Multiplikation erhalten.

Mit dem Multiplikationsverfahren erreicht man eine Fülle von Ordnungen, jedoch nicht die ungeraden Vielfachen von 2; denn ein magisches Quadrat der Ordnung 2 gibt es nicht. Es gibt ein Verfahren, aus einem magischen Quadrat eines doppelter Ordnung zu machen; leider enthält es - in seiner Ausgestaltung für ungerade Ordnung - eine Asymmetrie, die eine edle Zerlegung zu vereiteln scheint. Imrnerhin gibt es ein magisches Quadrat der Ordnung 6, das edel bezüglich der Zerlegung 6, 6 ist (nicht aber bezüglich 2,2,3,3 - in irgendeiner Reihenfolge). Allerdings sind seine Komponenten nicht einmal annähernd lateinisch, so daß die Permutationsmöglichkeiten recht beschränkt sind.

Hier bleibt noch viel zu tun