Lösbarkeit der Matrixfüllung

11

Die Matrix hat die Dimension n × n ( n - 1 ) . Wir wollen A mit ganzen Zahlen zwischen 1 und n einschließlich füllen .An×n(n1)A1n

Bedarf:

  1. Jede Spalte von ist eine Permutation von 1 , , n .A1,,n
  2. Eine durch zwei Zeilen von gebildete Submatrix kann keine identischen Spalten haben.A

Frage:

Ist es möglich, die Matrix entsprechend den Anforderungen zu füllen?

Beziehung zur Kryptographie:

Jede Zeilennummer entspricht einem Klartext. Jede Spalte entspricht einem Schlüssel. Da ein Schlüssel eine Injektion definiert, muss jede Spalte eine Permutation sein. Die zweite Voraussetzung ist die perfekte Geheimhaltung von zwei Nachrichten.

Cyker
quelle
1
Angesichts der Tatsache, dass Sie dies mit cr.crypto-security markiert haben, würde sich die Frage verbessern, ob Sie angeben könnten, wie es sich auf Krypto / Sicherheit bezieht.
Dave Clarke
1
Einfache Beobachtungen: Eine solche Matrix existiert für n ≤ 4. Nehmen Sie für n ≤ 3 alle Permutationen. Für n = 4 nehmen die einzigen Lösungen alle geraden oder alle ungeraden Permutationen.
Tsuyoshi Ito
Danke, Ito. Eigentlich habe ich die Antwort gefunden, wenn von Hand ist. Aber die Dinge werden viel schwieriger, wenn n 5 ist . Es tritt eine exponentielle Explosion auf. n4n5
Cyker
3
(1) Ich denke, dass das Problem mit der Codierungstheorie zusammenhängt und fügte es als Tag hinzu. (2) Eine weitere Beobachtung: Das Problem kann auch wie folgt angegeben werden. Finden Sie eine Matrix B der Größe n × (n ^ 2), so dass jede der ersten n Spalten von B die n Wiederholungen derselben Zahl ist und dass B die Bedingung 2 in der Frage erfüllt. Wenn ein solches B existiert, muss jede der letzten n (n - 1) Spalten von B eine Permutation sein. Umgekehrt kann jede Matrix A, die die Bedingungen 1 und 2 erfüllt, in eine Matrix B umgewandelt werden, indem die n angegebenen Spalten links von A angebracht werden.
Tsuyoshi Ito

Antworten:

11

Tsuyoshi, tolle Beobachtung in deinem Kommentar! Ich denke, das löst das Problem fast.

Betrachten Sie die folgenden zwei Fragen

  1. Gibt es Zeilen mit der Länge n ( n - 1 ), so dass in keiner Spalte zweimal eine Zahl erscheint und für jedes Zeilenpaar alle durch die Spalten angegebenen geordneten Paare unterschiedlich sind?kn(n1)
  2. Gibt es Zeilen mit der Länge n 2, so dass für jedes Zeilenpaar alle durch die Spalten angegebenen geordneten Paare unterschiedlich sind?kn2

Tsuyoshis Beobachtung in seinem Kommentar zeigt, dass Sie, wenn Sie einen Wert für Frage (1) erreichen können, denselben Wert k für Frage (2) erreichen können. Wir zeigen nun, dass wir, wenn wir einen Wert k für Frage (2) erreichen können, den Wert k - 1 für Frage (1) erreichen können. Somit ist die Antwort auf diese beiden Fragen nahezu gleich.kkkk1

Die Konstruktion geht folgt als: Ignorieren der ersten Reihe, mit Ausnahme all der PUT ‚s in den ersten n Positionen. Sie können jetzt eine Permutation der Werte { 1 , 2 , , n } auf jede der verbleibenden k - 1 Zeilen anwenden, sodass bis auf den ersten Eintrag jede der ersten n Spalten identische Werte enthält, und dies nach Tsuyoshis Beobachtung Im Kommentar erhalten Sie einen Satz von k - 1 Zeilen, die Ihre Bedingung erfüllen.1n{1,2,,n}k1nk1

Wenn Sie nun eine Menge von Zeilen mit der Länge n 2 haben, wobei jedes Zeilenpaar alle geordneten Paare in jeder Spalte enthält, entspricht dies einer Menge von k - 2 orthogonalen lateinischen Quadraten . Jede der Zeilen 3 , 4 , , k ergibt ein lateinisches Quadrat. Um das mit Zeile j verknüpfte lateinische Quadrat zu erhalten , geben Sie den Wert in die i -te Spalte der Zeile j in der Zelle ein, deren Koordinaten durch das geordnete Paar in der i -ten Spalte in den ersten beiden Zeilen angegeben sind.kn2k2 34kjiji

Wenn keine Primzahl ist, ist es ein berühmtes offenes Problem , wie viele zueinander orthogonale lateinische Quadrate der Ordnung n existieren, und ich glaube nicht, dass eine Menge von n - 2 orthogonalen lateinischen Quadraten für n keine Primzahl bekannt ist; Der allgemeine Konsens ist, dass solche Mengen nicht existieren. Das einzige bisher nachgewiesene Ergebnis ist, dass eine solche Menge für n = 6 nicht existiert . Es ist bekannt, dass die Anzahl k möglicher Zeilen für einige c mindestens als k = Ω ( n c ) wächstnnn2nn=6kk=Ω(nc)c. Ich glaube, ob es 8 orthogonale lateinische Quadrate der Ordnung 10 gibt, ist noch offen. (Es ist bekannt, dass es keine 9 gibt, aber aufgrund des möglichen Unterschieds von in der Antwort auf die beiden Fragen sagt dies nichts über das ursprüngliche Problem aus.)1

n=6k6×6n=10k=4

Peter Shor
quelle
n2nn1nnn1n=6
Dies ist eine sehr schöne Verbindung. Danke für die Antwort! Ein kleiner Punkt: Laut Wikipedia ist bekannt, dass n - 1 orthogonale lateinische Quadrate für n Primzahlen existieren, nicht nur für n Primzahlen.
Tsuyoshi Ito
@ Tsuyoshi - Ups. Ich wusste, dass; Ich habe es nur falsch gesagt. Die Konstruktion stammt aus endlichen Feldern. Danke für die Korrektur. Jetzt reparieren.
Peter Shor
Das dachte ich mir. :)
Tsuyoshi Ito
11

Dies ist eine Teillösung. Eine solche Matrix existiert, wenn n eine Primzahl ist.

Sei F das endliche Feld der Ordnung n . Wir konstruieren eine n × n ( n −1) Matrix, deren Zeilen mit F gekennzeichnet sind , deren Spalten mit ( F ∖ {0}) × F gekennzeichnet sind und deren Einträge in F wie folgt sind: die i- te Zeile der Die mit ( a , b ) bezeichnete Spalte ist durch ai + b gegeben . In Worten, jede Spalte entspricht ein Grad-ein Polynom in F . Dann enthält jede Spalte jedes Element von F. genau einmal, und keine zwei Spalten haben gleiche Einträge in mehr als einer Zeile, da die Werte von zwei unterschiedlichen Polynomen vom Grad eins höchstens an einem Punkt zusammenfallen können.

(Wenn Sie eine Matrix wünschen, deren Einträge in {1,…, n } statt in F stehen , ersetzen Sie die Elemente von F willkürlich durch {1,…, n }.)

Tsuyoshi Ito
quelle
n+1
@Artem: Es kann sein, dass Peter diese Frage mit orthogonalen lateinischen Quadraten verbindet. (Haftungsausschluss: Meiner Meinung nach sind orthogonale lateinische Quadrate, MUBs, kombinatorische Designs, einheitliche Designs und SIC-POVMs kaum zu unterscheiden.)
Tsuyoshi Ito
Vielen Dank, Ito! Dieser Entwurf sieht wirklich schön aus!
Cyker