Lösbarkeit der Matrixfüllung

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

Bedarf:

1. Jede Spalte von ist eine Permutation von 1 , … , n .$A$$1, \dots, 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.

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?$k$$n(n-1)$
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?$k$$n^2$

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.$k$$k$$k$$k-1$

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.$1$$n$$\lbrace 1, 2, \ldots, n \rbrace$$k-1$$n$$k-1$

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.$k$$n^2$$k-2$ $3$$4$$\ldots$$k$$j$$i$$j$$i$

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ächst$n$$n$$n-2$$n$$n=6$$k$$k=\Omega(n^c)$$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=6$$k$$6\times 6$$n=10$$k=4$

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 }.)